PROXIMITY SEARCH WITH A TRIANGULATED SPATIAL MODEL

The proximity relations inherent in triangulations of geometric data c an be exploited in the implementation of nearest-neighbour search proc edures. This is relevant to applications such as terrain analysis, car tography and robotics, in which triangulations may be used to model th e spatial data. Here we describe neighbourhood search procedures withi n constrained Delaunay triangulations of the vertices of linear object s, for the queries of nearest object to an object and the nearest obje ct to an arbitrary point. The procedures search locally from object ed ges, or from a query point, to build triangulated regions that extend from the source edge or point by a distance at least equal to that to its nearest neighbouring feature. Several geographical datasets have b een used to evaluate the procedures experimentally. Average numbers of edge-edge distance calculations to find the nearest line feature edge disjoint to another line feature edge ranged between 15 and 39 for th e different datasets examined, while the average numbers of point-edge distance calculations to determine the nearest edge to an arbitrary p oint ranged between 7 and 35.