Ibrahim Adamou - Computing the Topology of Voronoi Diagram of Parallels half Lines
28 March 2018 –
Computing the Topology of Voronoi Diagram of Parallels half Lines
The Voronoi Diagram (VD) is a one of the fundamental data structure in computational geometry with various applications in theoretical and practical areas. We consider the VD of a set of parallel half-lines, with the same orientation, constrained to a compact domain D0 in R^3, with respect to the Euclidean distance. We present an effcient algorithm for computing such VD, using a box subdivision process, which produces a mesh representing the topology of the VD in D0. By using criteria of topological regularity, the initial domain D0 will be subdivided into subdomains following a kd-trees structure. All subdomains generating cells of the Voronoi diagram will be identifed and linked according to an adjacency graph. During the reconstitution phase all VD faces and VD edges are meshed in identifed subdomains. An approximation of the VD cells which are topologically correct in D0 will thus be determined. In this talk, we will also present results of an implementation in Julia language with visualization using axel software of the algorithm. Some examples will be shown.