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
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
