A fast Las Vegas algorithm for triangulating a simple polygon
From MaRDI portal
Publication:1823686
DOI10.1007/BF02187741zbMath0681.68061OpenAlexW1989150421WikidataQ56389443 ScholiaQ56389443MaRDI QIDQ1823686
Kenneth L. Clarkson, Christopher J. Van Wyk, Robert Endre Tarjan
Publication date: 1989
Published in: Discrete \& Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://eudml.org/doc/131090
Related Items (11)
Three problems about simple polygons ⋮ Simplified linear-time Jordan sorting and polygon clipping ⋮ Partitioning arrangements of lines. I: An efficient deterministic algorithm ⋮ 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 ⋮ Reprint of: A simple and fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygons ⋮ POLYLINE FITTING OF PLANAR POINTS UNDER MIN-SUM CRITERIA ⋮ Applications of random sampling in computational geometry. II ⋮ A fast Las Vegas algorithm for triangulating a simple polygon ⋮ A simple and fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygons
Cites Work
- Unnamed Item
- Unnamed Item
- Simplified linear-time Jordan sorting and polygon clipping
- \(\epsilon\)-nets and simplex range queries
- Triangulating a simple polygon
- New applications of random sampling in computational geometry
- Applications of random sampling in computational geometry. II
- A fast Las Vegas algorithm for triangulating a simple polygon
- Triangulation and shape-complexity
- Triangulating Simple Polygons and Equivalent Problems
- An $O(n\log \log n)$-Time Algorithm for Triangulating a Simple Polygon
- Cascading Divide-and-Conquer: A Technique for Designing Parallel Algorithms
- Sorting jordan sequences in linear time using level-linked search trees
This page was built for publication: A fast Las Vegas algorithm for triangulating a simple polygon
