Unit:
Κατεύθυνση / ειδίκευση Θεωρητική Πληροφορική (ΘΕΩ)Πληροφορική
Author:
Katsamaki Christina
Supervisors info:
Ιωάννης Ζ. Εμίρης, Καθηγητής, Τμήμα Πληροφορικής και Τηλεπικοινωνιών, Ε.Κ.Π.Α.
Original Title:
Voronoi diagram of orthogonal polyhedra in two and three dimensions
Translated title:
Voronoi diagram of orthogonal polyhedra in two and three dimensions
Summary:
Voronoi diagrams are a fundamental geometric data structure for obtaining proximity relations. We consider axis-aligned orthogonal polyhedra in two and three-dimensional space. These are polyhedra whose faces meet at right angles and their edges are aligned with the axes of a coordinate system. We construct the exact Voronoi diagram inside an axis-aligned orthogonal polyhedron with holes defined by such polyhedra, under the max-norm. This is a particularly useful scenario in certain application domains, including raster graphics and VLSI design.
Our approach avoids creating full-dimensional elements on the Voronoi diagram and yields a skeletal representation of the input object, equivalent to the straight skeleton.
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 algorithm reads in a region bounding the input polyhedron and performs a recursive subdivision into cells (using quadtrees and octrees for 2D and 3D resp.). Then, a reconstruction technique is applied to produce an isomorphic representation of the Voronoi diagram. An hierarchical data structure of bounding volumes is used to accelerate the 2D algorithm for certain inputs and is necessary for the efficiency of the 3D algorithm.
The complexity is adaptive and comparable to that of previous methods. Under a mild assumption it is O(n / D+1 / D^2) in 2D or O(n a ^2 / D^2+1 / D^3) in 3D, where n is the number of sites, namely edges or facets respectively, D is the maximum cell size for the subdivision to stop (and is <1 under the appropriate scaling), and a bounds vertex cardinality per facet. We also provide a numerically stable, open-source implementation in Julia, illustrating the practical nature of our algorithm.
Part of the current thesis is given in the paper "Voronoi diagram of orthogonal polyhedra in two and three dimensions", co-authored with Prof. Ioannis Z. Emiris, that is about to appear in Proceedings of SEA^2 2019 (Special Event on Analysis of Experimental Algorithms).
Main subject category:
Technology - Computer science
Keywords:
max norm, axis-aligned, rectilinear, straight skeleton, subdivision method, numeric implementation, voronoi diagram, computational geometry
