Polygon triangulation in \(O(n\log{}\log{}n)\) time with simple data structures (Q1189285): Difference between revisions

From MaRDI portal
Created claim: Wikidata QID (P12): Q56389442, #quickstatements; #temporary_batch_1712272666262
ReferenceBot (talk | contribs)
Changed an Item
 
Property / cites work
 
Property / cites work: Triangulating a simple polygon in linear time / rank
 
Normal rank
Property / cites work
 
Property / cites work: Triangulation and shape-complexity / rank
 
Normal rank
Property / cites work
 
Property / cites work: A fast Las Vegas algorithm for triangulating a simple polygon / rank
 
Normal rank
Property / cites work
 
Property / cites work: Optimal Point Location in a Monotone Subdivision / rank
 
Normal rank
Property / cites work
 
Property / cites work: Triangulating Simple Polygons and Equivalent Problems / rank
 
Normal rank
Property / cites work
 
Property / cites work: Simplified linear-time Jordan sorting and polygon clipping / rank
 
Normal rank
Property / cites work
 
Property / cites work: Triangulating a simple polygon / rank
 
Normal rank
Property / cites work
 
Property / cites work: Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3670558 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Sorting jordan sequences in linear time using level-linked search trees / rank
 
Normal rank
Property / cites work
 
Property / cites work: Optimal Search in Planar Subdivisions / rank
 
Normal rank
Property / cites work
 
Property / cites work: An $O(n\log \log n)$-Time Algorithm for Triangulating a Simple Polygon / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4040234 / rank
 
Normal rank

Latest revision as of 09:33, 16 May 2024

scientific article
Language Label Description Also known as
English
Polygon triangulation in \(O(n\log{}\log{}n)\) time with simple data structures
scientific article

    Statements

    Polygon triangulation in \(O(n\log{}\log{}n)\) time with simple data structures (English)
    0 references
    0 references
    0 references
    0 references
    26 September 1992
    0 references
    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.
    0 references
    triangulation
    0 references
    simple polygon
    0 references
    horizontal visibility
    0 references

    Identifiers