Computing a single cell in the overlay of two simple polygons

DOI10.1016/S0020-0190(97)00125-7zbMath1336.68269OpenAlexW2138405350MaRDI QIDQ287185

Katrin Dobrindt, Olivier Devillers, Mark T. de Berg, Otfried Schwarzkopf

Publication date: 26 May 2016

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0020-0190(97)00125-7

zbMATH Keywords

computational geometryrandomized algorithmsarrangement

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Randomized algorithms (68W20)

Related Items

Discrete-Euclidean operations

Cites Work

• A simple and fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygons
• Randomized incremental construction of Delaunay and Voronoi diagrams
• Applications of random sampling to on-line algorithms in computational geometry
• On the general motion-planning problem with two degrees of freedom
• Applications of random sampling in computational geometry. II
• RANDOMIZATION YIELDS SIMPLE O(n log^⋆ n) ALGORITHMS FOR DIFFICULT Ω(n) PROBLEMS
• ERRATUM: "RANDOMIZED PARALLEL ALGORITHMS FOR TRAPEZOIDAL DIAGRAMS"
• On lazy randomized incremental construction