Tradeoffs in Approximate Range Searching Made Simpler

TitleTradeoffs in Approximate Range Searching Made Simpler
Publication TypeConference Papers
Year of Publication2008
AuthorsArya S, Fonseca G, Mount D
Conference NameComputer Graphics and Image Processing, 2008. SIBGRAPI '08. XXI Brazilian Symposium on
Date Published2008/10//
Keywordsapproximate range searching, computational geometry, data structure, Data structures, query range

Range searching is a fundamental problem in computational geometry. The problem involves preprocessing a set of n points in R^d into a data structure, so that it is possible to determine the subset of points lying within a given query range. In approximate range searching, a parameter eps epsiv gt; 0 is given, and for a given query range R the points lying within distance eps diam(R) of the range's boundary may be counted or not. In this paper we present three results related to the issue of tradeoffs in approximate range searching. First, we introduce the range sketching problem. Next, we present a space-time tradeoff for smooth convex ranges, which generalize spherical ranges. Finally, we show how to modify the previous data structure to obtain a space-time tradeoff for simplex ranges. In contrast to existing results, which are based on relatively complex data structures, all three of our results are based on simple, practical data structures.