Quasi-optimal range searching in spaces of finite VC-dimension (Q1823698)

The paper deals with the range searching problem, i.e. given a finite set S of points in d-dimensional space \(E^ d\) and a query region \(q\subseteq E^ d\), report or count the points of \(S\cap q\). On more abstract level one can consider a range space (X,R), where X is an arbitrary set (the elements of X are called points) and R is a subset of its power set (the members of R are called ranges). The authors consider the use of partition trees to solve this problem and show that ``good'' partition trees (i.e. with sublinear query time and linear size) can be characterized as those defined by range spaces of finite Vapnik- Chervonenkis dimension. Then they show that simplex and spherical range searching problems are both solvable in \(\theta (n^{1-1/d}\alpha (n))\) query time and \(\theta\) (n) storage in the arithmetical model, where \(\alpha\) (n) denotes the inverse Ackerman function. Finally algorithms for polygon, disk and tetrahedron range searching on RAM or pointer machine are discussed.