A Divide-and-Conquer Algorithm for Computing Voronoi Diagrams.

Area of Science:

• Computational Geometry
• Spatial Analysis

Background:

• Voronoi Diagrams efficiently identify the closest site for any given position.
• Generating discretized Voronoi Diagrams traditionally involves high computational costs.

Purpose of the Study:

• To develop a more computationally efficient algorithm for generating discretized Voronoi Diagrams.
• To reduce the complexity of calculating Voronoi Diagrams for large datasets.

Main Methods:

• A novel divide-and-conquer algorithm is proposed.
• The algorithm recursively subdivides quadrants based on the Voronoi regions of their corner points.
• Quadrants are only further subdivided if their corners belong to different regions.

Main Results:

• The proposed algorithm offers a significant improvement in computational efficiency compared to naive approaches.
• The recursive subdivision strategy avoids unnecessary calculations for uniform regions.

Conclusions:

• The divide-and-conquer approach provides an effective method for computing discretized Voronoi Diagrams.
• This algorithm presents a computationally lighter alternative for spatial analysis applications.