Abstract
We present a new algorithm for triangulating simple polygons that has four advantages over previous solutions [GJPT, Ch].
a) It is faster: Whilst previous solutions worked in time O(nlogn), the new algorithm only needs time O(n+rlogr) where r is the number of concave angles of the polygon.
b) It works for a larger class of inputs: Whilst previous solutions worked for simple polygons, the new algorithm handles simple polygons with polygonal holes.
c) It does more: Whilst previous solutions only triangulated the interior of a simple polygon, the new algorithm triangulates both the interior and the exterior region.
d) It is simpler: The algorithm is based on the plane-sweep paradigm and is — at least in its O(nlogn) version — very simple.
In addition to the new triangulation algorithm, we present two new applications of triangulation.
a) We show that one can compute the intersection of a convex m-gon Q and a triangulated simple n-gon P in time O(n+m). This improves a result by Shamos [Sh] stating that the intersection of two convex polygons can be computed in time O(n).
b) Given the triangulation of a simple n-gon P, we show how to compute in time O(n) a convex decomposition of P into at most 4·OPT pieces. Here OPT denotes the minimum number of pieces in any convex decomposition. The best factor known so far was 4.333 (Chazelle[Ch]).
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
A.V.Aho/J.E.Hopcroft/J.D.Ullman: The Design and Analysis of Computer Algorithms, Addison-Wesley Publ. Comp., Reading, Mass., 1974.
J.L. Bentley/T.A. Ottmann: Algorithms for Reporting and Counting Geometric Intersections, IEEE Trans. on Comp., Vol. C-28, No. 9 (1975), pp. 643–647.
B.Chazelle: A Theorem on Polygon Cutting with Applications, Proc. 23rd IEEE FOCS Symp. (1982), pp. 339–349.
M.R. Garey/D.S. Johnson/F.P. Preparata/R.E. Tarjan: Triangulating a Simple Polygon, Info. Proc. Letters, Vol. 7(4), June 1978, pp. 175–179.
D.T. Lee/F.P. Preparata: Location of a Point in a Planar Subdivision and its Applications, SIAM J. Comp., Vol. 6(1977), pp. 594–606.
R.J.Lipton/R.E.Tarjan: Applications of a Planar Separator Theorem, Proc. 18th IEEE FOCS Symp. (1977), pp. 162–170.
J. Nievergelt/F.P. Preparata: Plane-Sweep Algorithms for Intersecting Geometric Figures, CACM 25, 10(Oct. 1982), pp. 739–747.
M.I.Shamos: Geometric Complexity, Proc. 7th ACM STOC (1975), pp. 224–233.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1983 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Hertel, S., Mehlhorn, K. (1983). Fast triangulation of simple polygons. In: Karpinski, M. (eds) Foundations of Computation Theory. FCT 1983. Lecture Notes in Computer Science, vol 158. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-12689-9_105
Download citation
DOI: https://doi.org/10.1007/3-540-12689-9_105
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-12689-8
Online ISBN: 978-3-540-38682-7
eBook Packages: Springer Book Archive