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-4zbMATH Open0733.68092OpenAlexW3011379640WikidataQ56389444 ScholiaQ56389444MaRDI QIDQ809630FDOQ809630
Authors: Raimund Seidel 
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
Recommendations
Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Parallel algorithms in computer science (68W10)
Cites Work
- ERRATUM: "RANDOMIZED PARALLEL ALGORITHMS FOR TRAPEZOIDAL DIAGRAMS"
- 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
- Title not available (Why is that?)
- Sorting jordan sequences in linear time using level-linked search trees
- A fast Las Vegas algorithm for triangulating a simple polygon
Cited In (46)
- A unified approach to tail estimates for randomized incremental construction
- Four results on randomized incremental constructions
- Tail estimates for the efficiency of randomized incremental algorithms for line segment intersection
- New lower bounds for Hopcroft's problem
- Space-efficient functional offline-partially-persistent trees with applications to planar point location
- Randomized geometric algorithms and pseudorandom generators
- Complete and robust no-fit polygon generation for the irregular stock cutting problem
- EXACT GEOMETRIC COMPUTATION USING CASCADING
- Computing the smallest \(k\)-enclosing circle and related problems
- Solving the geometric firefighter routing problem via integer programming
- A Linear Time Heuristics for Trapezoidation of GIS Polygons
- Finding exact solutions for the geometric firefighter problem in practice
- Abstract Voronoi diagrams from closed bisecting curves
- FIST: fast industrial-strength triangulation of polygons
- Computing a single cell in the overlay of two simple polygons
- On the performance of self-organizing maps for the non-Euclidean traveling salesman problem in the polygonal domain
- Four results on randomized incremental constructions
- Optimal Area Polygonization by Triangulation and Visibility Search
- A practical algorithm for decomposing polygonal domains into convex polygons by diagonals
- Optimal window queries on line segments using the trapezoidal search DAG
- 2-toroids and their 3-triangulation
- Analysis of single rock blocks for general failure modes under conservative and non-conservative forces
- A randomized algorithm for triangulating a simple polygon in linear time
- Triangulating a simple polygon in linear time
- Title not available (Why is that?)
- A contribution to triangulation algorithms for simple polygons
- Walking an unknown street with bounded detour
- Expected asymptotically optimal planar point location
- Finding the largest empty disk containing a query point
- Three problems about simple polygons
- Computing hereditary convex structures
- Optimal randomized incremental construction for guaranteed logarithmic planar point location
- Adaptive Point Location in Planar Convex Subdivisions
- Abstract Voronoi diagrams with disconnected regions
- Triangulating Simple Polygons and Equivalent Problems
- A local triangulation algorithm to determine the relation between monotone chains
- An introduction to randomization in computational geometry
- On-line construction of the upper envelope of triangles and surface patches in three dimensions
- Approximating the k-Level in Three-Dimensional Plane Arrangements
- Coupling of BEM with a large displacement and rotation algorithm
- A fast algorithm for approximating the detour of a polygonal chain.
- Union and split operations on dynamic trapezoidal maps
- Efficient and qualified mesh generation for Gaussian molecular surface using adaptive partition and piecewise polynomial approximation
- Markov incremental constructions
- Computing the smallest k-enclosing circle and related problems
- Enhanced modified-polygon method for point-in-polygon problem
This page was built for publication: A simple and fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygons
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q809630)
