×

zbMATH — the first resource for mathematics

A fast Las Vegas algorithm for triangulating a simple polygon. (English) Zbl 0681.68061
The authors present in this revised and expanded version of a conference paper their randomized algorithm that triangulates a simple polygon of n vertices in 0(nlog*n) expected time.
Reviewer: H.D.Hecker

MSC:
68Q25 Analysis of algorithms and problem complexity
PDF BibTeX XML Cite
Full Text: DOI EuDML
References:
[1] M. J. Atallah, R. Cole, and M. T. Goodrich, Cascading divide-and-conquer: a technique for designing parallel algorithms,Proceedings of the 28th Annual Symposium on Foundations of Computer Science, 1987, pp. 151-160. · Zbl 0677.68022
[2] Chazelle, B.; Incerpi, J., Triangulation and shape complexity, ACM Transactions on Graphics, 3, 135-152, (1984) · Zbl 0592.68083
[3] Clarkson, K. L., New applications of random sampling in computational geometry, Discrete and Computational Geometry, 2, 195-222, (1987) · Zbl 0615.68037
[4] K. L. Clarkson, Applications of random sampling in computational geometry, II,Proceedings of the Fourth Annual Symposium on Computational Geometry, 1988, pp. 1-11.
[5] K. L. Clarkson, R. Cole, and R. E. Tarjan, private communication.
[6] K. L. Clarkson and P. W. Shor, Applications of random sampling in computational geometry, II,Discrete and Computational Geometry, this issue, 387-421. · Zbl 0681.68060
[7] K. L. Clarkson, R. E. Tarjan, and C. J. Van Wyk, A fast Las Vegas algorithm for triangulating a simple polygon,Proceedings of the Fourth Annual Symposium on Computational Geometry, 1988, pp. 18-22. · Zbl 0681.68061
[8] P. Erdos and J. Spencer,Probabilistic Methods in Combinatorics, Academic Press, New York, 1974. · Zbl 0308.05001
[9] Fournier, A.; Montuno, D. Y., Triangulating simple polygons and equivalent problems, ACM Transactions on Graphics, 3, 153-174, (1984) · Zbl 0592.68084
[10] K. Y. Fung, T. M. Nicholl, R. E. Tarjan, and C. J. Van Wyk, Simplified linear-time Jordan sorting and polygon clipping,ACM Transactions on Graphics, submitted. · Zbl 0697.68036
[11] Garey, M. R.; Johnson, D. S.; Preparata, F. P.; Tarjan, R. E., Triangulating a simple polygon, Information Processing Letters, 7, 175-180, (1978) · Zbl 0384.68040
[12] Haussler, D.; Welzl, E.\(, ɛ\)-nets and simplex range queries, Discrete and Computational Geometry, 2, 127-151, (1987) · Zbl 0619.68056
[13] Hoffman, K.; Mehlhorn, K.; Rosenstiehl, P.; Tarjan, R., Sorting Jordan sequences in linear time using level-linked search trees, Information and Control, 68, 170-184, (1986) · Zbl 0614.68051
[14] F. P. Preparata and M. I. Shamos,Computational Geometry: An Introduction, Springer-Verlag, New York, 1985. · Zbl 0759.68037
[15] Tarjan, R. E.; Wyk, C. J., An \(O(n\) log log \(n)\)-time algorithm for triangulating a simple polygon, SIAM Journal on Computing, 17, 143-178, (1988) · Zbl 0637.68044
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.