Randomized incremental constructions of three-dimensional convex hulls and planar voronoi diagrams, and approximate range counting

DOI10.1145/1109557.1109611zbMath1192.68749OpenAlexW4251862102MaRDI QIDQ3581543

Haim Kaplan, Micha Sharir

Publication date: 16 August 2010

Published in: Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm - SODA '06 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1109557.1109611

Mathematics Subject Classification ID

Computational aspects related to convexity (52B55) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items (5)

Range minima queries with respect to a random permutation, and approximate range counting ⋮ Relative \((p,\varepsilon )\)-approximations in geometry ⋮ The overlay of minimization diagrams in a randomized incremental construction ⋮ On approximate range counting and depth ⋮ A general approach for cache-oblivious range reporting and approximate range counting

This page was built for publication: Randomized incremental constructions of three-dimensional convex hulls and planar voronoi diagrams, and approximate range counting