Search

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 $\{\backslash cal\; q\}$ 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 $O(n^\{1/3\}\; +\; Q\; +\; \{\backslash bf\; E\}K\; +\; L\_\{r\}n^\{1/2\})$, where Q is the size of the query polygon $\{\backslash cal\; q\}$, $\{\backslash bf\; E\}K\; =\; O(n\backslash bcdot\; area(\{\backslash cal\; q\}))$ is the expected number of output points, $L\_\{r\}$ is a parameter related to the shape of the query polygon $\{\backslash cal\; q\}$ and n, and $L\_\{r\}$ is always bounded by the sum of the edge lengths of $\{\backslash cal\; q\}$. Theoretically, when $L\_\{r\}\; =\; O(1/n^\{1/6\})$ the expected query time is $O(n^\{1/3\}\; +\; Q\; +\; \{\backslash bf\; E\}K)$, 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. [ABSTRACT FROM AUTHOR]