TY - CONF T1 - Tradeoffs in Approximate Range Searching Made Simpler T2 - Computer Graphics and Image Processing, 2008. SIBGRAPI '08. XXI Brazilian Symposium on Y1 - 2008 A1 - Arya,S. A1 - Fonseca,G. A1 - Mount, Dave KW - approximate range searching KW - computational geometry KW - data structure KW - Data structures KW - query range AB - 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. JA - Computer Graphics and Image Processing, 2008. SIBGRAPI '08. XXI Brazilian Symposium on M3 - 10.1109/SIBGRAPI.2008.24 ER -