We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Fast Range Searching with Delaunay Triangulations.
- Authors
Binhai Zhu
- Abstract
This paper studies the idea of answering range searching queries using simple data structures. The only data structure we need is the Delaunay Triangulation of the input points. The idea is to first locate a vertex of the (arbitrary) query polygon <MATH>{\cal q}</MATH> and walk along the boundary of the polygon in the Delaunay Triangulation and report all the points enclosed by the query polygon. For a set of uniformly distributed random points in 2-D and a query polygon the expected query time of this algorithm is <MATH>O(n^{1/3} + Q + {\bf E}K + L_{r}n^{1/2})</MATH>, where Q is the size of the query polygon <MATH>{\cal q}</MATH>, <MATH>{\bf E}K = O(n\bcdot area({\cal q}))</MATH> is the expected number of output points, <MATH>L_{r}</MATH> is a parameter related to the shape of the query polygon <MATH>{\cal q}</MATH> and n, and <MATH>L_{r}</MATH> is always bounded by the sum of the edge lengths of <MATH>{\cal q}</MATH>. Theoretically, when <MATH>L_{r} = O(1/n^{1/6})</MATH> the expected query time is <MATH>O(n^{1/3} + Q + {\bf E}K)</MATH>, which improves the best known average query time for general range searching. Besides the theoretical meaning, the good property of this algorithm is that once the Delaunay Triangulation is given, no additional preprocessing is needed. In order to obtain empirical results, we design a new algorithm for generating random simple polygons within a given domain. Our empirical results show that the constant coefficient of the algorithm is small, at least for the special (practical) cases when the query polygon is either a triangle (simplex range searching) or an axis-parallel box (orthogonal range searching) and for the general case when the query polygons are generated by our new polygon-generating algorithms and their sizes are relatively small.
- Subjects
DATA structures; ALGORITHMS; ELECTRONIC data processing; FOUNDATIONS of arithmetic
- Publication
GeoInformatica, 2000, Vol 4, Issue 3, p317
- ISSN
1384-6175
- Publication type
Article
- DOI
10.1023/A:1009857410665