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

From MaRDI portal
Importer (talk | contribs)
Created a new Item
 
Added link to MaRDI item.
links / mardi / namelinks / mardi / name
 

Revision as of 11:06, 30 January 2024

scientific article
Language Label Description Also known as
English
A simple and fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygons
scientific article

    Statements

    A simple and fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygons (English)
    0 references
    0 references
    1991
    0 references
    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.
    0 references
    0 references
    polygon
    0 references
    triangulation
    0 references
    visibility map
    0 references
    trapezoidal decomposition
    0 references
    randomized algorithm
    0 references
    point location
    0 references

    Identifiers