Given an n-element point set in ℝ d , the range searching problem involves preprocessing these points so that the total weight, or for our purposes the semigroup sum, of the points lying within a given query range η can be determined quickly. In ε-approximate range searching we assume that η is bounded, and the sum is required to include all the points that lie within η and may additionally include any of the points lying within distance ε⋅diam(η) of η’s boundary. In this paper we contrast the complexity of approximate range searching based on properties of the semigroup and range space. A semigroup (S,+) is idempotent if x+x=x for all x∈S, and it is integral if for all k≥2, the k-fold sum x+⋅⋅⋅+x is not equal to x. Recent research has shown that the computational complexity of approximate spherical range searching is significantly lower for idempotent semigroups than it is for integral semigroups in terms of the dependencies on ε. In this paper we consider whether these results can be generalized to other sorts of ranges. We show that, as with integrality, allowing sharp corners on ranges has an adverse effect on the complexity of the problem. In particular, we establish lower bounds on the worst-case complexity of approximate range searching in the semigroup arithmetic model for ranges consisting of d-dimensional unit hypercubes under rigid motions. We show that for arbitrary (including idempotent) semigroups and linear space, the query time is at least $\varOmega(1/{\varepsilon }^{d-2\sqrt{d}})$ . In the case of integral semigroups we prove a tighter lower bound of Ω(1/ε d−2). These lower bounds nearly match existing upper bounds for arbitrary semigroups. In contrast, we show that the improvements offered by idempotence do apply to smooth convex ranges. We say that a range is smooth if at every boundary point there is an incident Euclidean sphere that lies entirely within the range whose radius is proportional to the range’s diameter. We show that for smooth ranges and idempotent semigroups, ε-approximate range queries can be answered in O(log n+(1/ε)(d−1)/2log (1/ε)) time using O(n/ε) space. We show that this is nearly tight by presenting a lower bound of Ω(log n+(1/ε)(d−1)/2). This bound is in the decision-tree model and holds irrespective of space.

Nearest neighbor searching is the problem of preprocessing a set of n point points in d -dimensional space so that, given any query point q , it is possible to report the closest point to q rapidly. In approximate nearest neighbor searching, a parameter ε > 0 is given, and a multiplicative error of (1 + ε) is allowed. We assume that the dimension d is a constant and treat n and ε as asymptotic quantities. Numerous solutions have been proposed, ranging from low-space solutions having space O ( n ) and query time O (log n + 1/ε d −1 ) to high-space solutions having space roughly O (( n log n )/ε d ) and query time O (log ( n /ε)). We show that there is a single approach to this fundamental problem, which both improves upon existing results and spans the spectrum of space-time tradeoffs. Given a tradeoff parameter γ, where 2 ≤ γ ≤ 1/ε, we show that there exists a data structure of space O ( n γ d −1 log(1/ε)) that can answer queries in time O (log( n γ) + 1/(εγ) ( d −1)/2 . When γ = 2, this yields a data structure of space O ( n log (1/ε)) that can answer queries in time O (log n + 1/ε ( d −1)/2 ). When γ = 1/ε, it provides a data structure of space O (( n /ε d −1 )log(1/ε)) that can answer queries in time O (log( n /ε)). Our results are based on a data structure called a ( t ,ε)-AVD, which is a hierarchical quadtree-based subdivision of space into cells. Each cell stores up to t representative points of the set, such that for any query point q in the cell at least one of these points is an approximate nearest neighbor of q . We provide new algorithms for constructing AVDs and tools for analyzing their total space requirements. We also establish lower bounds on the space complexity of AVDs, and show that, up to a factor of O (log (1/ε)), our space bounds are asymptotically tight in the two extremes, γ = 2 and γ = 1/ε.

Point location is the problem of preprocessing a planar polygonal subdivision S of size n into a data structure in order to determine efficiently the cell of the subdivision that contains a given query point. We consider this problem from the perspective of expected query time. We are given the probabilities $p_z$ that the query point lies within each cell $z \in S$. The entropy H of the resulting discrete probability distribution is the dominant term in the lower bound on the expected-case query time. We show that it is possible to achieve query time $H + O(\sqrt{H}+1)$ with space $O(n)$, which is optimal up to lower order terms in the query time. We extend this result to subdivisions with convex cells, assuming a uniform query distribution within each cell. In order to achieve space efficiency, we introduce the concept of entropy-preserving cuttings.

Given a planar polygonal subdivision S , point location involves preprocessing this subdivision into a data structure so that given any query point q , the cell of the subdivision containing q can be determined efficiently. Suppose that for each cell z in the subdivision, the probability p z that a query point lies within this cell is also given. The goal is to design the data structure to minimize the average search time. This problem has been considered before, but existing data structures are all quite complicated. It has long been known that the entropy H of the probability distribution is the dominant term in the lower bound on the average-case search time. In this article, we show that a very simple modification of a well-known randomized incremental algorithm can be applied to produce a data structure of expected linear size that can answer point-location queries in O ( H ) average time. We also present empirical evidence for the practical efficiency of this approach.

Range searching is among the most fundamental problems in computational geometry. An n-element point set in Rd is given along with an assignment of weights to these points from some commutative semigroup. Subject to a fixed space of possible range shapes, the problem is to preprocess the points so that the total semigroup sum of the points lying within a given query range η can be determined quickly. In the approximate version of the problem we assume that η is bounded, and we are given an approximation parameter ε > 0. We are to determine the semigroup sum of all the points contained within η and may additionally include any of the points lying within distance ε • diam(η) of η's boundar.In this paper we contrast the complexity of range searching based on semigroup properties. A semigroup (S,+) is idempotent if x + x = x for all x ∈ S, and it is integral if for all k ≥ 2, the k-fold sum x + ... + x is not equal to x. For example, (R, min) and (0,1, ∨) are both idempotent, and (N, +) is integral. To date, all upper and lower bounds hold irrespective of the semigroup. We show that semigroup properties do indeed make a difference for both exact and approximate range searching, and in the case of approximate range searching the differences are dramatic.First, we consider exact halfspace range searching. The assumption that the semigroup is integral allows us to improve the best lower bounds in the semigroup arithmetic model. For example, assuming O(n) storage in the plane and ignoring polylog factors, we provide an Ω*(n2/5) lower bound for integral semigroups, improving upon the best lower bound of Ω*(n1/3), thus closing the gap with the O(n1/2) upper bound.We also consider approximate range searching for Euclidean ball ranges. We present lower bounds and nearly matching upper bounds for idempotent semigroups. We also present lower bounds for range searching for integral semigroups, which nearly match existing upper bounds. These bounds show that the advantages afforded by idempotency can result in major improvements. In particular, assuming roughly linear space, the exponent in the ε-dependencies is smaller by a factor of nearly 1/2. All our results are presented in terms of space-time tradeoffs, and our lower and upper bounds match closely throughout the entire spectrum.To our knowledge, our results provide the first proof that semigroup properties affect the computational complexity of range searching in the semigroup arithmetic model. These are the first lower bound results for any approximate geometric retrieval problems. The existence of nearly matching upper bounds, throughout the range of space-time tradeoffs, suggests that we are close to resolving the computational complexity of both idempotent and integral approximate spherical range searching in the semigroup arithmetic model.

We consider the problem of computing large connected regions in a triangulated terrain of size n for which the normals of the triangles deviate by at most some small fixed angle. In previous work an exact near-quadratic algorithm was presented, but only a heuristic implementation with no guarantee was practicable. We present a new approximation algorithm for the problem which runs in O(n∈2) time and---apart from giving a guarantee on the quality of the produced solution---has been implemented and shows good performance on real data sets representing fracture surfaces consisting of around half a million triangles. Further we present a simple approximation algorithm for a related problem: given a set of n points in the plane, determine the placement of the unit disc which contains most points. This algorithm runs in linear time as well.

(MATH) Given a set $S$ of $n$ points in $\IR^d$, a {\em $(t,\epsilon)$-approximate Voronoi diagram (AVD)} is a partition of space into constant complexity cells, where each cell $c$ is associated with $t$ representative points of $S$, such that for any point in $c$, one of the associated representatives approximates the nearest neighbor to within a factor of $(1+\epsilon)$. Like the Voronoi diagram, this structure defines a spatial subdivision. It also has the desirable properties of being easy to construct and providing a simple and practical data structure for answering approximate nearest neighbor queries. The goal is to minimize the number and complexity of the cells in the AVD.(MATH) We assume that the dimension $d$ is fixed. Given a real parameter $\gamma$, where $2 \le \gamma \le 1/\epsilon$, we show that it is possible to construct a $(t,\epsilon)$-AVD consisting of \[O(n \epsilon^{\frac{d-1}{2}} \gamma^{\frac{3(d-1)}{2}} \log \gamma) \] cells for $t = O(1/(\epsilon \gamma)^{(d-1)/2})$. This yields a data structure of $O(n \gamma^{d-1} \log \gamma)$ space (including the space for representatives) that can answer $\epsilon$-NN queries in time $O(\log(n \gamma) + 1/(\epsilon \gamma)^{(d-1)/2})$. (Hidden constants may depend exponentially on $d$, but do not depend on $\epsilon$ or $\gamma$).(MATH) In the case $\gamma = 1/\epsilon$, we show that the additional $\log \gamma$ factor in space can be avoided, and so we have a data structure that answers $\epsilon$-approximate nearest neighbor queries in time $O(\log (n/\epsilon))$ with space $O(n/\epsilon^{d-1})$, improving upon the best known space bounds for this query time. In the case $\gamma = 2$, we have a data structure that can answer approximate nearest neighbor queries in $O(\log n + 1/\epsilon^{(d-1)/2})$ time using optimal $O(n)$ space. This dramatically improves the previous best space bound for this query time by a factor of $O(1/\epsilon^{(d-1)/2})$.(MATH) We also provide lower bounds on the worst-case number of cells assuming that cells are axis-aligned rectangles of bounded aspect ratio. In the important extreme cases $\gamma \in \{2, 1/\epsilon\}$, our lower bounds match our upper bounds asymptotically. For intermediate values of $\gamma$ we show that our upper bounds are within a factor of $O((1/\epsilon)^{(d-1)/2}\log \gamma)$ of the lower bound.

We consider the planar point location problem from the perspective of expected search time. We are given a planar polygonal subdivision S and for each polygon of the subdivision the probability that a query point lies within this polygon. The goal is to compute a search structure to determine which cell of the subdivision contains a given query point, so as to minimize the expected search time. This is a generalization of the classical problem of computing an optimal binary search tree for one-dimensional keys. In the one-dimensional case it has long been known that the entropy H of the distribution is the dominant term in the lower bound on the expected-case search time, and further there exist search trees achieving expected search times of at most H+2. Prior to this work, there has been no known structure for planar point location with an expected search time better than 2H, and this result required strong assumptions on the nature of the query point distribution. Here we present a data structure whose expected search time is nearly equal to the entropy lower bound, namely H+o(H). The result holds for any polygonal subdivision in which the number of sides of each of the polygonal cells is bounded, and there are no assumptions on the query distribution within each cell. We extend these results to subdivisions with convex cells, assuming a uniform query distribution within each cell.