Efficient Divide-and-Conquer Voronoi Diagram Algorithm
Explore a new divide-and-conquer algorithm for computing Voronoi diagrams, optimizing the process by focusing on specific quadrant corners and recursively subdividing when needed. This method improves computational efficiency and reduces the complexity of generating discretized Voronoi diagrams.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
A Divide-and-Conquer Algorithm for Computing Voronoi Diagrams Elijah Smith, Christian Trefftz, and Byron DeVries. 2020 IEEE International Conference on Electro Information Technology (EIT). IEEE, 2020. Presenter: Yen-Yu Chen Date: Sept. 10, 2024
Abstract(1/2) Identifying the closest of a set of locations typically requires computing the distance to each of these locations, given a current position. However, Voronoi Diagrams precompute the geometric areas that each of these locations is closest to in order to ameliorate the cost of computing distances later on. Problematically, the initial computations required to generate a Voronoi Diagram can be computationally expensive. Naive approaches to generating discretized Voronoi Diagrams require every discretized position to be analyzed with the set of locations. 2
Abstract(2/2) This paper introduces a new algorithm to compute discretized Voronoi Diagrams using a divide-and-conquer approach. Rather than calculate every position, our approach calculates the positions at the four corners of a quadrant. If the corners belong to the same region, there is no need to subdivide this quadrant anymore; but if they are different than the original quadrant is subdivided into smaller quadrants. The process is repeated recursively until the entire diagram has been calculated appropriately. 3
seed Voronoi Diagram A Voronoi diagram is a partition of a plane into regions close to each of a given set of objects(seed).
Classification of Voronoi Diagram infinite number of points discretized range of finite points 1 3 2
Naive Approach (0,1) (3,6) 1 1 3 3 2 2
Divide-And-Conquer Approach compute 4 corner different, recursive 1 1 3 3 2 2
Divide-And-Conquer Approach compute 4 corner same, fill region 1 1 3 3 2 2
Divide-And-Conquer Approach compute 4 corner different, recursive 1 1 3 3 2 2
Experiment Execution Times with a 2048 x 2048 Grid Execution Times with 50 Seeds
