]~psilon-Nets and Simplex Range Queries David Haussler and Emo Welzl* Department of Mathematics and Computer Science, University of Denver, Denver, Colorado 80208, USA. *Institutes for Information Processing, Technical University of Graz, A-8010 Graz, Aus- tria. Author D. Haussler gratefully acknowledges the support of NSF grant IST-8317918. This work was conducted while author E. Welzl visited the University of Denver. Altmtract We present a new technique for half-space and simplex range query using O(n) space and O(n a) query time, where a < if(a-l) +7 for all dimensions d ~2 a(a-l) + 1 and 7 > 0. These bounds are better than those previously published for all d ~ 2. The technique uses random sampling to build a partition-tree structure. We intro- duce the concept of an e-net for an abstract set of ranges to describe the desired result of this random sampling and give necessary and sufficient condi- tions that a random sample is an e-net with high probability. We illustrate the application of these ideas to other range query problems. 1. Introduction Rapid processing of geometric range queries has proven to be of fundamental importance in computational geometry, both as an end in itself and as a tech- nique in the effmient solution of other geometric problems, Yao and Yao [YAO 85] have recently demonstrated that a wide variety of range query prob- lems can be reduced to half-space query problems, =the basic form of which may be described as follows: Given a set of zt points in d-dimensional Euclidean space E d, find a data structure that uses O(rt) storage such that the number of points in any given half-space can be determined quickly (i.e. in sublinear time). This prob- Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the ACM copyright notice and the title of the publication and its date appear, and notice is given that copyin5 is by permission of the Association for Computing Machinery. To copy otherwise, or to republish, requires a fee and/or specific permission. © 1986 ACM 0-89791-194-6/86/0600/0061 $00.75 lem is called the half-slaace enumeration problem, A common variant of this prob- lem is the reporting problem, in which the set of points in the half-space is determined. The first sublinear bounds for half- space enumeration queries were given by Willard tWIt 82], who showed that O(n =) queries are possible in E ~ for a ~-0.774. Subsequently, Edelsbrunner and Welzl [EDL B2] improved this to a-" 0.695. In E a. the first bound is Yao's [YA083] (a "-0.936), which is followed by Dobkin and Edelsbrunner [DGBa 84] (a "- 0.918), Edelsbrunner and Huber [EDL 84] (a ~ 0.909), Dobkin, Edelsbrunner and F. Yao [DOBb 84] (a ~-0.899). Shortly after Cole [COL 85] showed a ~- 0.977 in E 4, Yao and Yao [ YAO 85] gave a generalized ver- sion of this result, showing that a = l°~(aa-1) can be achieved for all d d ~ 2. This bound is the best published for d ~ 4. In this paper we exhibit a data structure that allows half-space enumera- tion . queries in O(n =) for a= d(d-l! , +7, for any >0, which a(a-1) ~ , 7 improves on previous bounds for all d ~ 2. Specific bounds are: a ~- 0.687 (2 dimensions), a -~ 0.857 (3 dimensions) and tx ~ 0.923 (4 dimensions). The tech- nique also works for enumeration queries when ranges are simplices in d dimen- sions. Bounds for reporting are similar to those for enumeration, except that the number of points reported must be added to the time bound. It should be noted that better bounds are possible for reporting in two dimensions (that is, O(logr~ + t), where t is the number of points reported [CHA83]), but these techniques only work for half-planes. Our techniques are fundamentally similar to previous techniques employed 61for range queries. A partition tree is con- structed so that a recursive divide-and- conquer strategy can be efficiently applied to any query. The main difference is that our construction is probabilistic, using random sampling to build each level of the partition tree. It is analogous to the technique used by Clarkson [ CLA 85] to build efficient data structures for nearest neighbor queries. The construction of the partition tree in E ~ can be described as follows. Given a set A of n data points in the plane, create a root node and choose at random a sub- set N of A of size v. l Form the line arrangement consisting of all lines defirmd by pairs of points in N. For each cell in this arrangement, create a child of the root that contains the number of points of A that lie in this cell. Now proceed recursively for each of these children, creating a subtree for the points in its cell until each ceil contains less than v points. This tree is queried in the usual manner. Given a half-plane determined by a line, the point counts from all cells at the first level of the tree that are com- pletely contained in the half-plane are summed, and recursive calls are made for any cells that are cut by the line. The trick in establishing the time bound is to choose v such that with high probability (1) the total number of points in all cells that are intersected by any line is less than an for some small a (where rt is total number of points at the current level of recursion), while keeping the total number of ceils intersected reasonably small (this number is bounded by O(v~)). Thus, in contrast to previous techniques, we do noL rely on subdivisions of the points into parts of certain sizes. We show that it is onou o oo o for some constant c, to get (1) with t It actually suffices to make ~ independent random draws, even though this might not produce v distinct points. ~ is defined below. probability at least 1 -6 at any level of the tree. The key point is that for half- plane queries, the number v is essentially a constant that is independent of the