Abstract
Triangulating a simple polygon ofn vertices inO(n) time is one of the main open problems in computational geometry. The fastest algorithm to date, due to Tarjan and van Wyk, runs inO(n log logn), but several classes of simple polygons have been shown to admit linear time traingulation. Famous examples of such classes are: star-shaped, monotone, spiral, edge visible, and weakly externally visible polygons. The notion of geodesic paths is used here to characterize all classes of polygons for which linear time triangulation algorithms are known. First we introduce a new class of polygons,palm polygons, which subsumes many known classes of polygons for which linear time triangulation algorithms exist, and present a linear time algorithm for triangulating polygons in this class. Then a class of polygons,crab polygons, is defined and shown to contain all classes of existing polygons for which linear time triangulation algorithms are known. As a byproduct of this characterization, a new, very simple linear time algorithm for triangulating star-shaped polygons is obtained.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Avis D, Toussaint GT (1981) An optimal algorithm for determining the visibility of a polygon from an edge. IEEE Trans Comput C-30:910–914
Chazelle B, Incerpi J (1984) Triangulation and shape complexity. ACM Trans Graph 3:135–152
ElGindy H (1986) A linear algorithm for triangulating weakly externally visible polygons. Tech Rep No 86-75, Dep Comput Inf Sci Univ Pennsylvania (September 1986)
ElGindy H, Avis D (1981) A linear algorithm for computing the visibility polygon from a point. J Algorithms 2:186–197
ElGindy H, Avis D, Toussaint GT (1983) Applications of a two-dimensional hiddenline algorithm to other geometric problems. Comput 31:191–202
Garey M, Johnson D, Preparata FP, Tarjan R (1978) Triangulating a simple polygon. Inf Proc Lett 7:175–179
Lee DT (1983) Visibility of a simple polygon. Computer Vision, Graphics, Image Processing 22:207–221
lee DT, Preparata FP (1979) An optimal algorithm for finding the kernel of a polygon. J ACM 26:415–421
Lee SH, Chwa KY (1987) A new triangulation linear class of simple polygons. Int J Comput Math 22:135–147
Schoone A, van Leeuwen J (1980) Triangulating a starshaped polygon. Tech Rep No RUV-CS-80-3, Univ Utrecht (April 1980)
Tarjan RE, van Wyk C (1988) AnO(n log logn) time algorithm for triangulating simple polygons. SIAM J Comput 17:143–178
Toussaint GT (1984) A new linear algorithm for triangulating monotone polygons. Pattern Recognition Lett 2:155–158
Toussaint GT (1985) Shortest path solves translation separability of polygons. Tech Rep No SOCS-85-27, School of Comput Sci, McGill Univ (October 1985)
Toussaint GT, Avis D (1982) On a convex hull algorithm for polygons and its application to triangulation problems. Pattern Recognition 15:23–29
Woo TC, Shin SY (1985) A linear time algorithm for triangulating a point-visible polygon. ACM Trans Graph 4:60–70
Author information
Authors and Affiliations
Additional information
Research supported by Faculty of Graduate Studies and Research (McGill University) and NSERC under grant OGP0036737
Research supported by FCAR grant EQ-1678 and NSERC grant A9293
Rights and permissions
About this article
Cite this article
ElGindy, H., Toussaint, G.T. On geodesic properties of polygons relevant to linear time triangulation. The Visual Computer 5, 68–74 (1989). https://doi.org/10.1007/BF01901482
Issue Date:
DOI: https://doi.org/10.1007/BF01901482