A fast Las Vegas algorithm for triangulating a simple polygon

DOI10.1007/BF02187741MaRDI QIDQ1823686zbMATH OpenOpenAlexWikidataFDO

Authors Kenneth L. Clarkson, Christopher J. Van Wyk, Robert E. Tarjan

Publication date 1989

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/131090

zbMATH Keywords

algorithmcomputational geometry triangulationdivide and conquerLas Vegas

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Review text

The authors present in this revised and expanded version of a conference paper their randomized algorithm that triangulates a simple polygon of n vertices in 0(nlog*n) expected time.

Cites work

• -nets and simplex range queries
• A fast Las Vegas algorithm for triangulating a simple polygon
• An O(n\log \log n)-Time Algorithm for Triangulating a Simple Polygon
• Applications of random sampling in computational geometry. II
• Cascading Divide-and-Conquer: A Technique for Designing Parallel Algorithms
• scientific article; zbMATH DE number 43279 (Why is no real title available?)
• scientific article; zbMATH DE number 3482343 (Why is no real title available?)
• New applications of random sampling in computational geometry
• Simplified linear-time Jordan sorting and polygon clipping
• Sorting jordan sequences in linear time using level-linked search trees
• Triangulating a simple polygon
• Triangulating Simple Polygons and Equivalent Problems
• Triangulation and shape-complexity

Cited in

(11)

• Triangulating a simple polygon in linear time
• An introduction to randomized algorithms
• Polygon triangulation in \(O(n\log{}\log{}n)\) time with simple data structures
• Applications of random sampling in computational geometry. II
• A fast Las Vegas algorithm for triangulating a simple polygon
• Three problems about simple polygons
• POLYLINE FITTING OF PLANAR POINTS UNDER MIN-SUM CRITERIA
• A simple and fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygons
• Simplified linear-time Jordan sorting and polygon clipping
• Partitioning arrangements of lines. I: An efficient deterministic algorithm
• Reprint of: A simple and fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygons

This page was built for publication: A fast Las Vegas algorithm for triangulating a simple polygon

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1823686)