Two-Dimensional Range Search Based on the Voronoi Diagram

This paper studies the two-dimensional range search problem, and constructs a simple and efficient algorithm based on the Voronoi diagram. In this problem, a set of points and a query range are given, and we want to enumerate all the points which are inside the query range as quickly as possible. In most of the previous researches on this problem, the shape of the query range is restricted to particular ones such as circles, rectangles and triangles, and the improvement on the worst-case performance has been pursued. On the other hand, the algorithm proposed in this paper is designed for a general shape of the query range, and is intended to accomplish a good average-case performance. This performance is actually observed by numerical experiments. We can observe that our algorithm shows the better performance in almost all the cases.