Computing a single cell in the overlay of two simple polygons

DOI10.1016/S0020-0190(97)00125-7MaRDI QIDQ287185zbMATH OpenOpenAlexFDO

Authors Olivier Devillers, Katrin Dobrindt, Mark de Berg, Otfried Cheong

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

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

Recommendations

• Computing a Face in an Arrangement of Line Segments and Related Problems
• scientific article; zbMATH DE number 3945383
• On lazy randomized incremental construction
• On lazy randomized incremental construction
• Computing Many Faces in Arrangements of Lines and Segments

Cites work

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

Cited in

(1)

• Discrete-Euclidean operations

This page was built for publication: Computing a single cell in the overlay of two simple polygons

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q287185)