
Summary: 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 \({\mathcal 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+ {\mathbf E}K+ L_rn^{1/2})\), where \(Q\) is the size of the query polygon \({\mathcal Q}\), \({\mathbf E}K= O(n\cdot \text{area}({\mathcal Q}))\) is the expected number of output points, \(L_r\) is a parameter related to the shape of the query polygon \({\mathcal Q}\) and \(n\), and \(L_r\) is always bounded by the sum of the edge lengths of \({\mathcal Q}\). Theoretically, when \(L_r= O(1/n^{1/6})\) the expected query time is \(O(n^{1/3}+ Q+ {\mathbf 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.
Computing methodologies and applications, range searching, Computer graphics; computational geometry (digital and algorithmic aspects), Delaunay triangulation
Computing methodologies and applications, range searching, Computer graphics; computational geometry (digital and algorithmic aspects), Delaunay triangulation
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 0 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
