Voronoi diagram is a method used to divide a region into smaller regions based on the principle of nearest-neighbor. Regions in Voronoi diagram are called Voronoi cells. When each cell considers only one facility point as the nearest generator point, this voronoi diagram is called an order-1 Voronoi diagram; when a cell considers n facility point as the nearest generator points, this diagram is called Higher Order Voronoi Diagram. The latest version of the Voronoi diagram as Highest order Voronoi diagram (HSVD) is an extension of Higher Order Voronoi Diagram. That consists of points (vertex) and segments that will produce polygon areas. The problem is how to nd the region which contain the query point quickly considering the number of regions is quite many. To access it can use linear search for checking. The polygon will be checked one by one for each polygon. Therefore, these problems will be solved using indexing method to speed up the searching process. Index that will proposed in this nal project is K-Dimensional Tree (K-D Tree) because that can process the points. If points of region is known then we can know candidate region of query point. So, indexing is required to solve this problem.
Keywords: indexing, region, voronoi diagram, spatial, k-d tree