Polygon triangulation in \(O(n\log{}\log{}n)\) time with simple data structures
type: Item
instance of: scholarly article
title: Polygon triangulation in \(O(n\log{}\log{}n)\) time with simple data structures
zbMATH Open document ID: 0753.68092
DOI: 10.1007/BF02187846
author: Maria M. Klawe
author: David Kirkpatrick
author: Robert E. Tarjan
published in: Discrete \& Computational Geometry
publication date: 1992-09-26T00:00:00Z
full work available at URL: https://eudml.org/doc/131199
review text: An \(O(n\log\log n)\) time algorithm for triangulating simple \(n\)-vertex polygons is presented. The rasterized version of the algorithm even consumes \(O(n\log^* n)\) time. Comparing to optimal linear time triangulating algorithms due to \textit{B. Chazelle} [Discrete Comput. Geom 6(5), 485-524 (1991)] the underlying data structures and procedures are quite simple. The algorithm is based on the balanced horizontal visibility partition of a given polygon.
Mathematics Subject Classification ID: 68U05
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 54912
zbMATH Keywords: triangulation
zbMATH Keywords: simple polygon
zbMATH Keywords: horizontal visibility
reviewed by: Mirko Křivánek
MaRDI profile type: Publication
Wikidata QID: Q56389442
cites work: Triangulating a simple polygon in linear time
cites work: Triangulation and shape-complexity
cites work: A fast Las Vegas algorithm for triangulating a simple polygon
cites work: Optimal Point Location in a Monotone Subdivision
cites work: Triangulating Simple Polygons and Equivalent Problems
cites work: Simplified linear-time Jordan sorting and polygon clipping
cites work: Triangulating a simple polygon
cites work: Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
cites work: Q3670558
cites work: Sorting jordan sequences in linear time using level-linked search trees
cites work: Optimal Search in Planar Subdivisions
cites work: An $O(n\log \log n)$-Time Algorithm for Triangulating a Simple Polygon
cites work: Q4040234
DBLP publication ID: journals/dcg/KirkpatrickKT92
description: scientific article; zbMATH DE number 54912