A simple and fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygons
From MaRDI portal
Publication:809630
DOI10.1016/0925-7721(91)90012-4zbMath0733.68092OpenAlexW3011379640WikidataQ56389444 ScholiaQ56389444MaRDI QIDQ809630
Publication date: 1991
Published in: Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0925-7721(91)90012-4
Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Parallel algorithms in computer science (68W10)
Related Items
Computing the smallest \(k\)-enclosing circle and related problems ⋮ Computing a single cell in the overlay of two simple polygons ⋮ Expected asymptotically optimal planar point location ⋮ An introduction to randomization in computational geometry ⋮ Computing the smallest k-enclosing circle and related problems ⋮ Adaptive Point Location in Planar Convex Subdivisions ⋮ Complete and robust no-fit polygon generation for the irregular stock cutting problem ⋮ Finding exact solutions for the geometric firefighter problem in practice ⋮ Optimal randomized incremental construction for guaranteed logarithmic planar point location ⋮ On-line construction of the upper envelope of triangles and surface patches in three dimensions ⋮ Randomized geometric algorithms and pseudorandom generators ⋮ Space-efficient functional offline-partially-persistent trees with applications to planar point location ⋮ Optimal Area Polygonization by Triangulation and Visibility Search ⋮ Optimal window queries on line segments using the trapezoidal search DAG ⋮ Approximating the k-Level in Three-Dimensional Plane Arrangements ⋮ Three problems about simple polygons ⋮ On the performance of self-organizing maps for the non-Euclidean traveling salesman problem in the polygonal domain ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A fast algorithm for approximating the detour of a polygonal chain. ⋮ Triangulating a simple polygon in linear time ⋮ Enhanced Modified-Polygon Method for Point-in-Polygon Problem ⋮ Efficient and Qualified Mesh Generation for Gaussian Molecular Surface Using Adaptive Partition and Piecewise Polynomial Approximation ⋮ Markov incremental constructions ⋮ Walking an unknown street with bounded detour ⋮ Four results on randomized incremental constructions ⋮ Tail estimates for the efficiency of randomized incremental algorithms for line segment intersection ⋮ Solving the geometric firefighter routing problem via integer programming ⋮ Computing hereditary convex structures ⋮ Analysis of single rock blocks for general failure modes under conservative and non-conservative forces ⋮ EXACT GEOMETRIC COMPUTATION USING CASCADING ⋮ A practical algorithm for decomposing polygonal domains into convex polygons by diagonals ⋮ Four results on randomized incremental constructions ⋮ A unified approach to tail estimates for randomized incremental construction ⋮ New lower bounds for Hopcroft's problem ⋮ Coupling of BEM with a large displacement and rotation algorithm ⋮ Abstract Voronoi Diagrams from Closed Bisecting Curves ⋮ ABSTRACT VORONOI DIAGRAMS WITH DISCONNECTED REGIONS ⋮ FINDING THE LARGEST EMPTY DISK CONTAINING A QUERY POINT
Cites Work
- Unnamed Item
- Triangulating a simple polygon
- 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
- ERRATUM: "RANDOMIZED PARALLEL ALGORITHMS FOR TRAPEZOIDAL DIAGRAMS"
- Sorting jordan sequences in linear time using level-linked search trees
