On lazy randomized incremental construction

DOI10.1145/195058.195113zbMath1345.68272OpenAlexW2011771550MaRDI QIDQ5890839

Katrin Dobrindt, Mark T. de Berg, Otfried Schwarzkopf

Publication date: 1 September 2016

Published in: Proceedings of the twenty-sixth annual ACM symposium on Theory of computing - STOC '94 (Search for Journal in Brave)

Full work available at URL: https://hal.inria.fr/inria-00074409/file/RR-2262.pdf

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Randomized algorithms (68W20)

Related Items (7)

Computing a single cell in the overlay of two simple polygons ⋮ Almost tight upper bounds for lower envelopes in higher dimensions ⋮ Separating and shattering long line segments ⋮ Arrangements in higher dimensions: Voronoi diagrams, motion planning, and other applications ⋮ An introduction to randomization in computational geometry ⋮ Vertical decompositions for triangles in 3-space ⋮ On-line construction of the upper envelope of triangles and surface patches in three dimensions

This page was built for publication: On lazy randomized incremental construction