Triangulated spatial models and neighbourhood search: an experimental comparison with quadtrees
We describe a Delaunay triangulation-based algorithm to search for the nearest line or polygonal boundary to an arbitrary point. We use geographical data to compare the algorithm experimentally with a linear quadtree search procedure. Both algorithms use priority queues. The rich proximity relations of the triangulation result in run-time performance that is clearly competitive with the quadtree, being quite similar with respect to the numbers of distance-based calculations and faster with regard to execution time. It is envisaged that the main benefits of triangulation for neighbourhood search are in applications in which the data are permanently triangulated or in which a triangulation assists in an application-specific analysis or transformation.
quadtree priority queue nearest neighbour search delaunay triangulation gis