Table of Contents#### Download Safari Books Online apps: Apple iOS | Android | BlackBerry

### BACKGROUND

#### Voronoi Diagrams

Entire Site

Free Trial

Safari Books Online is a digital library providing on-demand subscription access to thousands of learning resources.

Our proposed approach to address the nearest neighbor queries is based on both the Voronoi diagram and Dijkstra 's algorithm. A Voronoi diagram divides a space into disjoint polygons where the nearest neighbor of any point inside a polygon is the generator of the polygon. Dijkstra's algorithm provides one of the most efficient algorithms that finds the shortest paths from the source node to all the other nodes. In this section, we review the principles of the Voronoi diagrams. We start with the Voronoi diagram for 2-dimensional Euclidean space and present only the properties that are used in our approach. We then discuss the network Voronoi diagram where the distance between two objects in space is their shortest path in the network rather than their Euclidean distance and hence can be used for spatial networks. Then, we talk about two different approaches for solving KNN queries (i.e., IE and PINE) that our proposed DAR and eDAR algorithms depend on. A thorough discussion on Voronoi diagrams is presented in Okabe, Boots, Sugihara, and Chiu (2000) and Safar (2005).

Imagine you are looking for a school for your kid. Among the criteria to be considered will be the length of the way to school. If you formulate this as a spatial analysis problem, you are looking for the school that is closest to your home, among all schools in your city. The classical approach to solve this spatial analysis problem is the Voronoi diagram. The Voronoi diagram isolates the area that is closest to each school. The Voronoi diagram of a point set P, VD(P), is a unique diagram that consists of a set of collectively exhaustive and mutually exclusive Voronoi polygons (Voronoi cells), VPs. Each Voronoi polygon is associated with a point in P (called generator point) and contains all the locations in the Euclidean plane that are closer to the generator point of the Voronoi cell than any other generator point in P. The boundaries of the polygons, called Voronoi edges, are the set of locations that can be assigned to more than one generator. The Voronoi polygons that share the same edges are called adjacent polygons and their generators are called adjacent generators. The following property holds for any Voronoi diagram and is used to answer KNN queries: