Indexing Voronoi cells using quadtree in spatial database

摘要

Computational geometry is a mathematical knowlege in the field related to the design and analysis of algorithm to solve geometry problems. Its can be applicated in the fields of mapping, robotics, geometry and so forth. A method can be used is Voronoi diagram. Voronoi diagram is a method of deviding the area to a smaller area based on the principle of the nearest neighboring. This method only used in 1-order voronoi diagram. In voronoi diagram there is a new variation named Highest Order Voronoi Diagram (HSVD). HSVD can be used for all orders voronoi diagram. However, these methods have disadvantage that accessing fragment use linear search. Consequently make data fragment searches to find the region to be slow and takes a long time. Therefore, in this paper will present a index structure that incoperates Highest Order Voronoi Diagrams into Quadtree. Quadtree index used is capable of cutting more than half of the original data. This algorithm makes the search regions faster than before.