Voronoi diagram of orthogonal polyhedra in two and three dimensions
- Creators
- Emiris, Ioannis Z.
- Katsamaki, Christina
- Others:
- National and Kapodistrian University of Athens (NKUA)
- AlgebRe, geOmetrie, Modelisation et AlgoriTHmes (AROMATH) ; Inria Sophia Antipolis - Méditerranée (CRISAM) ; Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-National and Kapodistrian University of Athens (NKUA)
- OUtils de Résolution Algébriques pour la Géométrie et ses ApplicatioNs (OURAGAN) ; Inria de Paris ; Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)
- Ilias Kotsireas
- Panos Pardalos
- Konstantinos E. Parsopoulos
- Dimitris Souravlias
- Arsenis Tsokas
Description
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.
Abstract
International audience
Additional details
- URL
- https://hal.inria.fr/hal-02398736
- URN
- urn:oai:HAL:hal-02398736v1
- Origin repository
- UNICA