caa a22 4500 469075309 CHVBK 20180323132933.0 cr unu---uuuuu 170328e19920401xx s 000 0 eng 10.1007/BF02187846 doi (NATIONALLICENCE)springer-10.1007/BF02187846 Polygon triangulation in O ( n log log n ) time with simple data structures [Elektronische Daten] [David Kirkpatrick, Maria Klawe, Robert Tarjan] We give a newO(n log logn)-time deterministic algorithm for triangulating simplen-vertex polygons, which avoids the use of complicated data structures. In addition, for polygons whose vertices have integer coordinates of polynomially bounded size, the algorithm can be modified to run inO(n log*n) time. The major new techniques employed are the efficient location of horizontal visibility edges that partition the interior of the polygon into regions of approximately equal size, and a linear-time algorithm for obtaining the horizontal visibility partition of a subchain of a polygonal chain, from the horizontal visibility partition of the entire chain. The latter technique has other interesting applications, including a linear-time algorithm to convert a Steiner triangulation of a polygon into a true triangulation. Springer-Verlag New York Inc., 1992 Kirkpatrick David Department of Computer Science, University of British Columbia, V6T 1Z2, Vancouver, British Columbia, Canada aut Klawe Maria Department of Computer Science, University of British Columbia, V6T 1Z2, Vancouver, British Columbia, Canada aut Tarjan Robert Department of Computer Science, Princeton University, 08540, Princeton, NJ, USA aut Discrete & Computational Geometry Springer New York 7/4(1992-04-01), 329-346 0179-5376 7:4<329 1992 7 454 https://doi.org/10.1007/BF02187846 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/BF02187846 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Kirkpatrick David Department of Computer Science, University of British Columbia, V6T 1Z2, Vancouver, British Columbia, Canada aut NATIONALLICENCE 700 1- Klawe Maria Department of Computer Science, University of British Columbia, V6T 1Z2, Vancouver, British Columbia, Canada aut NATIONALLICENCE 700 1- Tarjan Robert Department of Computer Science, Princeton University, 08540, Princeton, NJ, USA aut NATIONALLICENCE 773 0- Discrete & Computational Geometry Springer New York 7/4(1992-04-01), 329-346 0179-5376 7:4<329 1992 7 454 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer