A simple and fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygons (Q809630)

The construction of the ``trapezoidal decomposition'' alias ``horizontal visibility map'' for a planar polygon is a common preprocessing step after which a triangulation may be constructed in linear time. This data structure for a set of noncrossing line segments is also useful for a number of other applications, e.g. motion planning and boolean masking operations for VLSI layout. The paper presents a conceptually simple randomized algorithm which constructs the trapezoidal decomposition for a set S of n noncrossing (i.e. intersecting only at their endpoints) line segments in the plane in the expected time O(n log n\(+k \log n)\) where k is the number of the connected components of S. \textit{B. Chazelle} [Discrete Comput. Geom. 6, 485-524 (1991)] proposed an ultimate linear time algorithm for polygon triangulation. However a practical and simple to implement triangulation algorithm may be based on the trapezoidation from the reviewed paper. Additionally, the algorithm creates a data structure of expected linear size for point location queries in the resulting trapezoidation in logarithmic expected time.