Approximating the Generalized Voronoi Diagram of Closely Spaced Objects

Area of Science:

• Computational Geometry
• Computer Graphics
• Scientific Visualization

Background:

• Generalized Voronoi Diagrams (GVDs) are crucial for spatial analysis but computationally intensive.
• Existing algorithms struggle with datasets containing numerous, closely spaced geometric objects.
• Efficient GVD approximation is needed for various applications in 2D and 3D.

Purpose of the Study:

• To present a novel algorithm for approximating Generalized Voronoi Diagrams (GVDs).
• To enable efficient GVD computation on datasets with arbitrary and densely packed 2D/3D geometric objects.
• To provide a robust and parallelizable method for GVD surface generation.

Main Methods:

• Space subdivision using an octree with an adjacency structure.
• Novel adaptive distance transform for computing distance functions on octree vertices.
• Densely sampling the distance field in areas of close object spacing.

Main Results:

• Successful approximation of GVDs on diverse datasets, including those with tightly packed objects.
• Demonstrated feasibility of GVD computation on commodity hardware.
• Enabled robust and parallelizable GVD surface generation.

Conclusions:

• The proposed algorithm offers an efficient solution for GVD approximation, particularly for challenging datasets.
• The method is suitable for implementation on standard hardware, broadening accessibility.
• The generated GVDs have demonstrated utility in various 2D and 3D applications.