Triangulated spatial models and neighbourhood search: an experimental comparison with quadtrees

We describe a Delaunay triangulation-based algorithm to search for the near est line or polygonal boundary to an arbitrary point. We use geographical d ata to compare the algorithm experimentally with a linear quadtree search p rocedure. Both algorithms use priority queues. The rich proximity relations of the triangulation result in run-time performance that is clearly compet itive with the quadtree, being quite similar with respect to the numbers of distance-based calculations and faster with regard to execution time. It i s envisaged that the main benefits of triangulation for neighbourhood searc h are in applications in which the data are permanently triangulated or in which a triangulation assists in an application-specific analysis or transf ormation.