Skip to Main content Skip to Navigation
Conference papers

Voronoi diagram of orthogonal polyhedra in two and three dimensions

Abstract : Voronoi diagrams are a fundamental geometric data structure for obtaining proximity relations. We consider collections of axis-aligned orthogonal polyhedra in two and three-dimensional space under the max-norm, which is a particularly useful scenario in certain application domains. We construct the exact Voronoi diagram inside an orthogonal polyhedron with holes defined by such polyhedra. Our approach avoids creating full-dimensional elements on the Voronoi diagram and yields a skeletal representation of the input object. We introduce a complete algorithm in 2D and 3D that follows the subdivision paradigm relying on a bounding-volume hierarchy; this is an original approach to the problem. The complexity is adaptive and comparable to that of previous methods. Under a mild assumption it is O(n/∆) in 2D or O(n.α^2 /∆^2) in 3D, where n is the number of sites, namely edges or facets resp., ∆ is the maximum cell size for the subdivision to stop, and α bounds vertex cardinality per facet. We also provide a numerically stable, open-source implementation in Julia, illustrating the practical nature of our algorithm.
Complete list of metadatas

Cited literature [15 references]  Display  Hide  Download

https://hal.inria.fr/hal-02398736
Contributor : Ioannis Emiris <>
Submitted on : Saturday, December 7, 2019 - 10:37:26 PM
Last modification on : Tuesday, January 14, 2020 - 1:36:09 PM
Document(s) archivé(s) le : Sunday, March 8, 2020 - 2:24:37 PM

File

vd_arxiv.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Ioannis Z. Emiris, Christina Katsamaki. Voronoi diagram of orthogonal polyhedra in two and three dimensions. SEA 2019 - Symposium on Experimental Algorithms, Jun 2019, Kalamata, Greece. ⟨10.1007/978-3-030-34029-2_1⟩. ⟨hal-02398736⟩

Share

Metrics

Record views

34

Files downloads

117