Abstract
We present a randomized algorithm that triangulates a simple polygon onn vertices inO(n log*n) expected time. The averaging in the analysis of running time is over the possible choices made by the algorithm; the bound holds for any input polygon.
Article PDF
Similar content being viewed by others
References
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.
B. Chazelle and J. Incerpi, Triangulation and shape complexity,ACM Transactions on Graphics,3 (1984), 135–152.
K. L. Clarkson, New applications of random sampling in computational geometry,Discrete and Computational Geometry,2 (1987), 195–222.
K. L. Clarkson, Applications of random sampling in computational geometry, II,Proceedings of the Fourth Annual Symposium on Computational Geometry, 1988, pp. 1–11.
K. L. Clarkson, R. Cole, and R. E. Tarjan, private communication.
K. L. Clarkson and P. W. Shor, Applications of random sampling in computational geometry, II,Discrete and Computational Geometry, this issue, 387–421.
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.
P. Erdos and J. Spencer,Probabilistic Methods in Combinatorics, Academic Press, New York, 1974.
A. Fournier and D. Y. Montuno, Triangulating simple polygons and equivalent problems,ACM Transactions on Graphics,3 (1984), 153–174.
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.
M. R. Garey, D. S. Johnson, F. P. Preparata, and R. E. Tarjan, Triangulating a simple polygon,Information Processing Letters,7 (1978), 175–180.
D. Haussler and E. Welzl,ɛ-nets and simplex range queries,Discrete and Computational Geometry,2 (1987), 127–151.
K. Hoffman, K. Mehlhorn, P. Rosenstiehl, and R. Tarjan, Sorting Jordan sequences in linear time using level-linked search trees,Information and Control,68 (1986), 170–184.
F. P. Preparata and M. I. Shamos,Computational Geometry: An Introduction, Springer-Verlag, New York, 1985.
R. E. Tarjan and C. J. Van Wyk, AnO(n log logn)-time algorithm for triangulating a simple polygon,SIAM Journal on Computing,17 (1988), 143–178.
Author information
Authors and Affiliations
Additional information
Research partially supported by the National Science Foundation under Grant No. DCR-8605962.
Rights and permissions
About this article
Cite this article
Clarkson, K.L., Tarjan, R.E. & Van Wyk, C.J. A fast las vegas algorithm for triangulating a simple polygon. Discrete Comput Geom 4, 423–432 (1989). https://doi.org/10.1007/BF02187741
Received:
Revised:
Published:
Issue date:
DOI: https://doi.org/10.1007/BF02187741