Cauchy’s surface area formula expresses the surface area of a convex body as the average area of its orthogonal projections over all directions. While this tool is fundamental in Euclidean geometry, with applications ranging from geometric tomography to approximation theory, extensions to non-Euclidean settings remain less explored. In this paper, we establish an analog of Cauchy’s formula for the Funk geometry induced by a convex body K in ℝ^d, for the Holmes-Thompson surface area. The formula is based on central projections to boundary points of K. We show that when K is a convex polytope, the formula reduces to a weighted sum of contributions associated with the vertices of K. Finally, as a consequence of our analysis, we derive a generalization of Crofton’s formula for surface areas in the Funk geometry. By viewing Euclidean, Minkowski, Hilbert, and hyperbolic geometries as limiting or special cases of the Funk setting, our results provide a unified framework for these classical surface area formulas.

Abstract Approximating convex bodies is a fundamental problem in geometry. Given a convex body K in $$\mathbb {R}^d$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mrow> <mml:mi>R</mml:mi> </mml:mrow> <mml:mi>d</mml:mi> </mml:msup> </mml:math> for a fixed dimension d , the objective is to minimize the number of facets of an approximating polytope for a given Hausdorff error $$\varepsilon $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>ε</mml:mi> </mml:math> . The best known uniform bound, due to Dudley (1974), shows that $$O(({{\,\textrm{diam}\,}}(K)/\varepsilon )^{(d-1)/2})$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:msup> <mml:mrow> <mml:mo>(</mml:mo> <mml:mrow> <mml:mspace/> <mml:mtext>diam</mml:mtext> <mml:mspace/> </mml:mrow> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>K</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> <mml:mo>/</mml:mo> <mml:mi>ε</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>d</mml:mi> <mml:mo>-</mml:mo> <mml:mn>1</mml:mn> <mml:mo>)</mml:mo> <mml:mo>/</mml:mo> <mml:mn>2</mml:mn> </mml:mrow> </mml:msup> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> facets suffice. Although this bound is optimal for fat objects, such as Euclidean balls, it is far from optimal for “skinny” convex bodies. Skinniness can be characterized relative to the Euclidean ball. Given a convex body K , define its area radius , $${{\,\textrm{arad}\,}}(K)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mrow> <mml:mspace/> <mml:mtext>arad</mml:mtext> <mml:mspace/> </mml:mrow> <mml:mo>(</mml:mo> <mml:mi>K</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> , to be the radius of the Euclidean ball having the same surface area as K . It follows from generalizations of the isoperimetric inequality that $${{\,\textrm{diam}\,}}(K) \ge 2 \cdot {{\,\textrm{arad}\,}}(K)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mrow> <mml:mspace/> <mml:mtext>diam</mml:mtext> <mml:mspace/> </mml:mrow> <mml:mo>(</mml:mo> <mml:mi>K</mml:mi> <mml:mo>)</mml:mo> <mml:mo>≥</mml:mo> <mml:mn>2</mml:mn> <mml:mo>·</mml:mo> <mml:mrow> <mml:mspace/> <mml:mtext>arad</mml:mtext> <mml:mspace/> </mml:mrow> <mml:mo>(</mml:mo> <mml:mi>K</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> . We show that, given a convex body whose minimum width is at least $$\varepsilon $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>ε</mml:mi> </mml:math> , it is possible to approximate the body by a polytope having $$O(({{\,\textrm{arad}\,}}(K)/\varepsilon )^{(d-1)/2})$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:msup> <mml:mrow> <mml:mo>(</mml:mo> <mml:mrow> <mml:mspace/> <mml:mtext>arad</mml:mtext> <mml:mspace/> </mml:mrow> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>K</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> <mml:mo>/</mml:mo> <mml:mi>ε</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>d</mml:mi> <mml:mo>-</mml:mo> <mml:mn>1</mml:mn> <mml:mo>)</mml:mo> <mml:mo>/</mml:mo> <mml:mn>2</mml:mn> </mml:mrow> </mml:msup> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> facets. Our approach works by first reducing the problem of approximating convex bodies to that of approximating convex functions. We employ a classical concept from convexity, called Macbeath regions. We demonstrate that there is a polar relationship between the Macbeath regions of a function and the Macbeath regions of its Legendre dual. This is combined with known bounds on the Mahler volume to bound the total size of the approximation.

Support Vector Machines (SVMs) are a class of classification models in machine learning that are based on computing a maximum-margin separator between two sets of points. The SVM problem has been heavily studied for Euclidean geometry and for a number of kernels. In this paper, we consider the linear SVM problem in the Hilbert metric, a non-Euclidean geometry defined over a convex body. We present efficient algorithms for computing the SVM classifier for a set of n points in the Hilbert metric defined by convex polygons in the plane and convex polytopes in d-dimensional space. We also consider the problems in the related Funk distance.

Abstract Approximating convex bodies is a fundamental question in geometry, which has a wide variety of applications. Given a convex body K in $$\mathbb {R}^d$$ R d for fixed d , the objective is to minimize the number of facets of an approximating polytope for a given Hausdorff error $$\varepsilon $$ ε . It is known that $$O(({{\,\textrm{diam}\,}}(K)/\varepsilon )^{(d-1)/2})$$ O ( ( diam ( K ) / ε ) ( d - 1 ) / 2 ) facets suffice and are necessary for many instances, such as the Euclidean ball. However, this bound is far from optimal for “skinny” convex bodies. A natural way to characterize the skinniness of a convex object is in terms of its relationship to the Euclidean ball. Given a convex body K , its volume diameter $$\Delta _d(K)$$ Δ d ( K ) is defined to be the diameter of a Euclidean ball of the same volume as K . The surface diameter $$\Delta _{d-1}(K)$$ Δ d - 1 ( K ) is defined analogously for surface area. It follows from generalizations of the isoperimetric inequality that $${{\,\textrm{diam}\,}}(K) \ge \Delta _{d-1}(K) \ge \Delta _d(K)$$ diam ( K ) ≥ Δ d - 1 ( K ) ≥ Δ d ( K ) . Arya, da Fonseca, and Mount proved that the diameter-based bound could be made sensitive to the surface diameter, improving the above bound to $$O((\Delta _{d-1}(K)/\varepsilon )^{(d-1)/2})$$ O ( ( Δ d - 1 ( K ) / ε ) ( d - 1 )

Abstract. Coverings of convex bodies have emerged as a central component in the design of efficient solutions to approximation problems involving convex bodies. Intuitively, given a convex body [Formula: see text] and [Formula: see text], a covering is a collection of convex bodies whose union covers [Formula: see text] such that a constant factor expansion of each body lies within an [Formula: see text] expansion of [Formula: see text]. Coverings have been employed in many applications, such as approximations for diameter, width, and [Formula: see text]-kernels of point sets, approximate nearest neighbor searching, polytope approximations with low combinatorial complexity, and approximations to the closest vector problem (CVP). It is known how to construct coverings of size [Formula: see text] for general convex bodies in [Formula: see text]. In special cases, such as when the convex body is the [Formula: see text] unit ball, this bound has been improved to [Formula: see text]. This raises the question of whether such a bound generally holds. In this paper we answer the question in the affirmative. We demonstrate the power and versatility of our coverings by applying them to the problem of approximating a convex body by a polytope, where the error is measured through the Banach–Mazur metric. Given a well-centered convex body [Formula: see text] and an approximation parameter [Formula: see text], we show that there exists a polytope [Formula: see text] consisting of [Formula: see text] vertices (facets) such that [Formula: see text]. This bound is optimal in the worst case up to factors of [Formula: see text]. (This bound has been established recently using different techniques, but our approach is arguably simpler and more elegant.) As an additional consequence, we obtain the fastest [Formula: see text]-approximate CVP algorithm that works in any norm, with a running time of [Formula: see text] up to polynomial factors in the input size, and we obtain the fastest [Formula: see text]-approximation algorithm for integer programming. We also present a framework for constructing coverings of optimal size for any convex body (up to factors of [Formula: see text]).

Coverings of convex bodies have emerged as a central component in the design of efficient solutions to approximation problems involving convex bodies. Intuitively, given a convex body K and ε > 0, a covering is a collection of convex bodies whose union covers K such that a constant factor expansion of each body lies within an ε expansion of K. Coverings have been employed in many applications, such as approximations for diameter, width, and ε-kernels of point sets, approximate nearest neighbor searching, polytope approximations with low combinatorial complexity, and approximations to the Closest Vector Problem (CVP).

This article considers the question of how to succinctly approximate a multidimensional convex body by a polytope. Given a convex body K of unit diameter in Euclidean d -dimensional space (where d is a constant) and an error parameter ε > 0, the objective is to determine a convex polytope of low combinatorial complexity whose Hausdorff distance from K is at most ε. By combinatorial complexity , we mean the total number of faces of all dimensions. Classical constructions by Dudley and Bronshteyn/Ivanov show that O (1/ε ( d -1)/2 ) facets or vertices are possible, respectively, but neither achieves both bounds simultaneously. In this article, we show that it is possible to construct a polytope with O (1/ε ( d -1)/2 ) combinatorial complexity, which is optimal in the worst case. Our result is based on a new relationship between ε-width caps of a convex body and its polar body. Using this relationship, we are able to obtain a volume-sensitive bound on the number of approximating caps that are “essentially different.” We achieve our main result by combining this with a variant of the witness-collector method and a novel variable-thickness layered construction of the economical cap covering.

Convex bodies play a fundamental role in geometric computation, and approximating such bodies is often a key ingredient in the design of efficient algorithms. We consider the question of how to succinctly approximate a multidimensional convex body by a polytope. We are given a convex body K of unit diameter in Euclidean d-dimensional space (where d is a constant) along with an error parameter ε > 0. The objective is to determine a polytope of low combinatorial complexity whose Hausdorff distance from K is at most e. By combinatorial complexity we mean the total number of faces of all dimensions of the polytope. In the mid-1970's, a result by Dudley showed that O(1/ε(d–1)/2) facets suffice, and Bronshteyn and Ivanov presented a similar bound on the number of vertices. While both results match known worst-case lower bounds, obtaining a similar upper bound on the total combinatorial complexity has been open for over 40 years. Recently, we made a first step forward towards this objective, obtaining a suboptimal bound. In this paper, we settle this problem with an asymptotically optimal bound of O(1/ε(d–1)/2). Our result is based on a new relationship between ε-width caps of a convex body and its polar. Using this relationship, we are able to obtain a volume-sensitive bound on the number of approximating caps that are “essentially different.” We achieve our result by combining this with a variant of the witness-collector method and a novel variable-width layered construction.

We present a new approach to ε-approximate nearest-neighbor queries in fixed dimension under a variety of non-Euclidean distances. We consider two families of distance functions: (a) convex scaling distance functions including the Mahalanobis distance, the Minkowski metric and multiplicative weights, and (b) Bregman divergences including the Kullback-Leibler divergence and the Itakura-Saito distance. As the fastest known data structures rely on the lifting transformation, their application is limited to the Euclidean metric, and alternative approaches for other distance functions are much less efficient. We circumvent the reliance on the lifting transformation by a careful application of convexification, which appears to be relatively new to computational geometry. We are given n points in ℝd, each a site possibly defining its own distance function. Under mild assumptions on the growth rates of these functions, the proposed data structures answer queries in logarithmic time using O(n log(1/ε)/εd/2) space, which nearly matches the best known results for the Euclidean metric.

In the polytope membership problem, a convex polytope $K$ in $\mathbb{R}^d$ is given, and the objective is to preprocess $K$ into a data structure so that, given any query point $q \in \mathbb{R}^d$, it is possible to determine efficiently whether $q \in K$. We consider this problem in an approximate setting. Given an approximation parameter $\varepsilon$, the query can be answered either way if the distance from $q$ to $K$'s boundary is at most $\varepsilon$ times $K$'s diameter. We assume that the dimension $d$ is fixed, and $K$ is presented as the intersection of $n$ halfspaces. Previous solutions to approximate polytope membership were based on straightforward applications of classic polytope approximation techniques by Dudley [ Approx. Theory, 10 (1974), pp. 227--236] and Bentley, Faust, and Preparata [ Commun. ACM, 25 (1982), pp. 64--68]. The former is optimal in the worst case with respect to space, and the latter is optimal with respect to query time. We present four main results. First, we show how to combine the two above techniques to obtain a simple space-time trade-off. Second, we present an algorithm that dramatically improves this trade-off. In particular, for any constant $\alpha \ge 4$, this data structure achieves query time roughly $O(1/\varepsilon^{(d-1)/\alpha})$ and space roughly $O(1/\varepsilon^{(d-1)(1 - \Omega(\log \alpha)/\alpha)})$. We do not know whether this space bound is tight, but our third result shows that there is a convex body such that our algorithm achieves a space of at least $\Omega( 1/\varepsilon^{(d-1)(1-O(\sqrt{\alpha})/\alpha} )$. Our fourth result shows that it is possible to reduce approximate Euclidean nearest neighbor searching to approximate polytope membership queries. Combined with the above results, this provides significant improvements to the best known space-time trade-offs for approximate nearest neighbor searching in $\mathbb{R}^d$. For example, we show that it is possible to achieve a query time of roughly $O(\log n + 1/\varepsilon^{d/4})$ with space roughly $O(n/\varepsilon^{d/4})$, thus reducing by half the exponent in the space bound.

The computation of (i) eps-kernels, (ii) approximate diameter, and (iii) approximate bichromatic closest pair are fundamental problems in geometric approximation. In each case the input is a set of points in d-dimensional space for a constant d and an approximation parameter eps > 0. In this paper, we describe new algorithms for these problems, achieving significant improvements to the exponent of the eps-dependency in their running times, from roughly d to d/2 for the first two problems and from roughly d/3 to d/4 for problem (iii). These results are all based on an efficient decomposition of a convex body using a hierarchy of Macbeath regions, and contrast to previous solutions that decomposed the space using quadtrees and grids. By further application of these techniques, we also show that it is possible to obtain near-optimal preprocessing time for the most efficient data structures for (iv) approximate nearest neighbor searching, (v) directional width queries, and (vi) polytope membership queries.

In the polytope membership problem, a convex polytope K in ℝd is given, and the objective is to preprocess K into a data structure so that, given a query point q ∊ ℝd, it is possible to determine efficiently whether q ∊ K. We consider this problem in an approximate setting and assume that d is a constant. Given an approximation parameter ∊ > 0, the query can be answered either way if the distance from q to K's boundary is at most ∊ times K's diameter. Previous solutions to the problem were on the form of a space-time tradeoff, where logarithmic query time demands O(1/∊d-1) storage, whereas storage O(1/∊(d-1)/2) admits roughly O(1/∊(d-1)/8) query time. In this paper, we present a data structure that achieves logarithmic query time with storage of only O(1/∊(d-1)/2), which matches the worst-case lower bound on the complexity of any ∊- approximating polytope. Our data structure is based on a new technique, a hierarchy of ellipsoids defined as approximations to Macbeath regions. As an application, we obtain major improvements to approximate Euclidean nearest neighbor searching. Notably, the storage needed to answer ∊-approximate nearest neighbor queries for a set of n points in O(log n/∊) time is reduced to O(n/∊d/2). This halves the exponent in the ∊-dependency of the existing space bound of roughly O(n/∊d), which has stood for 15 years (HarPeled, 2001).

Approximating convex bodies succinctly by convex polytopes is a fundamental problem in discrete geometry. A convex body K of diameter $$\mathrm {diam}(K)$$ is given in Euclidean d-dimensional space, where d is a constant. Given an error parameter $$\varepsilon > 0$$ , the objective is to determine a polytope of minimum combinatorial complexity whose Hausdorff distance from K is at most $$\varepsilon \cdot \mathrm {diam}(K)$$ . By combinatorial complexity we mean the total number of faces of all dimensions of the polytope. A well-known result by Dudley implies that $$O(1/\varepsilon ^{(d-1)/2})$$ facets suffice, and a dual result by Bronshteyn and Ivanov similarly bounds the number of vertices, but neither result bounds the total combinatorial complexity. We show that there exists an approximating polytope whose total combinatorial complexity is $$\widetilde{O}(1/\varepsilon ^{(d-1)/2})$$ , where $$\widetilde{O}$$ conceals a polylogarithmic factor in $$1/\varepsilon $$ . This is a significant improvement upon the best known bound, which is roughly $$O(1/\varepsilon ^{d-2})$$ . Our result is based on a novel combination of both old and new ideas. First, we employ Macbeath regions, a classical structure from the theory of convexity. The construction of our approximating polytope employs a new stratified placement of these regions. Second, in order to analyze the combinatorial complexity of the approximating polytope, we present a tight analysis of a width-based variant of Bárány and Larman’s economical cap covering. Finally, we use a deterministic adaptation of the witness-collector technique (developed recently by Devillers et al.) in the context of our stratified construction.

Approximating convex bodies succinctly by convex polytopes is a fundamental problem in discrete geometry. A convex body K of diameter $diam(K)$ is given in Euclidean d-dimensional space, where $d$ is a constant. Given an error parameter eps > 0, the objective is to determine a polytope of minimum combinatorial complexity whose Hausdorff distance from K is at most eps diam(K). By combinatorial complexity we mean the total number of faces of all dimensions of the polytope. A well-known result by Dudley implies that O(1/eps^{(d-1)/2}) facets suffice, and a dual result by Bronshteyn and Ivanov similarly bounds the number of vertices, but neither result bounds the total combinatorial complexity. We show that there exists an approximating polytope whose total combinatorial complexity is O-tilde(1/eps^{(d-1)/2}), where O-tilde conceals a polylogarithmic factor in 1/eps. This is an improvement upon the best known bound, which is roughly O(1/eps^{d-2}). Our result is based on a novel combination of both new and old ideas. First, we employ Macbeath regions, a classical structure from the theory of convexity. The construction of our approximating polytope employs a new stratified placement of these regions. Second, in order to analyze the combinatorial complexity of the approximating polytope, we present a tight analysis of a width-based variant of Barany and Larman's economical cap covering, which may be of independent interest. Finally, we use a deterministic variation of the witness-collector technique (developed recently by Devillers et al.) in the context of our stratified construction.

The Euclidean minimum spanning tree (EMST) is a fundamental and widely studied structure. In the approximate version we are given an n-element point set P in ℝd and an error parameter ∊ > 0, and the objective is to compute a spanning tree over P whose weight is at most (1 + ∊) times that of the true minimum spanning tree. Assuming that d is a fixed constant, existing algorithms have running times that (up to logarithmic factors) grow as O(n/∊Ω(d)). We present an algorithm whose running time is . Thus, this is the first algorithm for approximate EMSTs that eliminates the exponential ∊ dependence on dimension. (Note that the O-notation conceals a constant factor of the form O(1)d.) The algorithm is deterministic and very simple.

Range searching is a widely-used method in computational geometry for efficiently accessing local regions of a large data set. Typically, range searching involves either counting or reporting the points lying within a given query region, but it is often desirable to compute statistics that better describe the structure of the point set lying within the region, not just the count. In this paper we consider the geometric minimum spanning tree (MST) problem in the context of range searching where approximation is allowed. We are given a set P of n points in R^d. The objective is to preprocess P so that given an admissible query region Q, it is possible to efficiently approximate the weight of the minimum spanning tree of the subset of P lying within Q. There are two natural sources of approximation error, first by treating Q as a fuzzy object and second by approximating the MST weight itself. To model this, we assume that we are given two positive real approximation parameters eps_q and eps_w. Following the typical practice in approximate range searching, the range is expressed as two shapes Q^- and Q^+, where Q^- is contained in Q which is contained in Q^+, and their boundaries are separated by a distance of at least eps_q diam(Q). Points within Q^- must be included and points external to Q^+ cannot be included. A weight W is a valid answer to the query if there exist subsets P' and P'' of P, such that Q^- is contained in P' which is contained in P'' which is contained in Q^+ and wt(MST(P')) <= W <= (1+eps_w) wt(MST(P'')). In this paper, we present an efficient data structure for answering such queries. Our approach uses simple data structures based on quadtrees, and it can be applied whenever Q^- and Q^+ are compact sets of constant combinatorial complexity. It uses space O(n), and it answers queries in time O(log n + 1/(eps_q eps_w)^{d + O(1)}). The O(1) term is a small constant independent of dimension, and the hidden constant factor in the overall running time depends on d, but not on eps_q or eps_w. Preprocessing requires knowledge of eps_w, but not eps_q.

Recently, Arya, da Fonseca, and Mount [STOC 2011, SODA 2012] made notable progress in improving the ϵ-dependencies in the space/query-time tradeoffs for (1 + ϵ)-factor approximate nearest neighbor search in fixed-dimensional Euclidean spaces. However, ϵ-dependencies in the preprocessing time were not considered, and so their data structures cannot be used to derive faster algorithms for offline proximity problems. Known algorithms for many such problems, including approximate bichromatic closest pair (BCP) and approximate Euclidean minimum spanning trees (EMST), typically have factors near (1/ϵ)d/2±O(1) in the running time when the dimension d is a constant.

Approximating convex bodies is a fundamental question in geometry and has applications to a wide variety of optimization problems. Given a convex body K in REd for fixed d, the objective is to minimize the number of vertices or facets of an approximating polytope for a given Hausdorff error ε. The best known uniform bound, due to Dudley (1974), shows that O((diam(K)/ε)(d-1)/2) facets suffice. While this bound is optimal in the case of a Euclidean ball, it is far from optimal for skinny convex bodies. We show that, under the assumption that the width of the body in any direction is at least ε, it is possible to approximate a convex body using O(√area(K)/ε(d-1)/2) facets, where area(K) is the surface area of the body. This bound is never worse than the previous bound and may be significantly better for skinny bodies. This bound is provably optimal in the worst case and improves upon our earlier result (which appeared in SODA 2012).

The problem of approximating convex bodies by polytopes is an important and well studied problem. Given a convex body K in Rd, the objective is to minimize the number of vertices (alternatively the number of facets) of an approximating polytope for a given Hausdorff error ε. Results to date have been of two types. The first type assumes that K is smooth, and bounds hold in the limit as ε tends to zero. The second type requires no such assumptions. The latter type includes the well known results of Dudley (1974) and Bronshteyn and Ivanov (1976), which show that in spaces of fixed dimension, O((diam(K)/ε)(d − 1)/2) vertices (alt., facets) suffice. Our results are of this latter type. In our first result, under the assumption that the width of the body in any direction is at least ε, we strengthen the above bound to . This is never worse than the previous bound (by more than logarithmic factors) and may be significantly better for skinny bodies. Our analysis exploits an interesting analogy with a classical concept from the theory of convexity, called the Mahler volume. This is a dimensionless quantity that involves the product of the volumes of a convex body and its polar dual. In our second result, we apply the same machinery to improve upon the best known bounds for answering ε-approximate polytope membership queries. Given a convex polytope P defined as the intersection of halfspaces, such a query determines whether a query point q lies inside or outside P, but may return either answer if q's distance from P's boundary is at most ε. We show that, without increasing storage, it is possible to reduce the best known search times for ε-approximate polytope membership significantly. This further implies improvements to the best known search times for approximate nearest neighbor searching in spaces of fixed dimension.

We consider an approximate version of a fundamental geometric search problem, polytope membership queries. Given a convex polytope P in REd, presented as the intersection of halfspaces, the objective is to preprocess P so that, given a query point q, it is possible to determine efficiently whether q lies inside P subject to an error bound ε. Previous solutions to this problem were based on straightforward applications of classic polytope approximation techniques by Dudley (1974) and Bentley et al. (1982). The former yields minimum storage, and the latter yields constant query time. A space-time tradeoff can be obtained by interpolating between the two. We present the first significant improvements to this tradeoff. For example, using the same storage as Dudley, we reduce the query time from O(1/ε(d-1)/2) to O(1/ε(d-1)/4). Our approach is based on a very simple algorithm. Both lower bounds and upper bounds on the performance of the algorithm are presented.

We establish two new lower bounds for the halfspace range searching problem: Given a set of n points in ℜd, where each point is associated with a weight from a commutative semigroup, compute the semigroup sum of the weights of the points lying within any query halfspace. Letting $m$ denote the space requirements, we prove a lower bound for general semigroups of Ω(n1-1/(d+1)/m1/(d+1)) and for integral semigroups of Ω(n/m1/d).

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.

Most research in algorithms for geometric query problems has focused on their worst-case performance. However, when information on the query distribution is available, the alternative paradigm of designing and analyzing algorithms from the perspective of expected-case performance appears more attractive. We study the approximate nearest neighbor problem from this perspective. As a first step in this direction, we assume that the query points are sampled uniformly from a hypercube that encloses all the data points; however, we make no assumption on the distribution of the data points. We show that with a simple partition tree, called the sliding-midpoint tree, it is possible to achieve linear space and logarithmic query time in the expected case; in contrast, the data structures known to achieve linear space and logarithmic query time in the worst case are complex, and algorithms on them run more slowly in practice. Moreover, we prove that the sliding-midpoint tree achieves optimal expected query time in a certain class of algorithms.

(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.

Consider a set of S of n data points in real d -dimensional space, R d , where distances are measured using any Minkowski metric. In nearest neighbor searching, we preprocess S into a data structure, so that given any query point q ∈ R d , is the closest point of S to q can be reported quickly. Given any positive real ϵ, data point p is a (1 +ϵ)- approximate nearest neighbor of q if its distance from q is within a factor of (1 + ϵ) of the distance to the true nearest neighbor. We show that it is possible to preprocess a set of n points in R d in O(dn log n ) time and O(dn) space, so that given a query point q ∈ R d , and ϵ > 0, a (1 + ϵ)-approximate nearest neighbor of q can be computed in O ( c d , ϵ log n ) time, where c d,ϵ ≤ d ⌈1 + 6d/ϵ⌉ d is a factor depending only on dimension and ϵ. In general, we show that given an integer k ≥ 1, (1 + ϵ)-approximations to the k nearest neighbors of q can be computed in additional O(kd log n ) time.

The range searching problem is a fundamental problem in computational geometry, with numerous important applications. Most research has focused on solving this problem exactly, but lower bounds show that if linear space is assumed, the problem cannot be solved in polylogarithmic time, except for the case of orthogonal ranges. In this paper we show that if one is willing to allow approximate ranges, then it is possible to do much better. In particular, given a bounded range Q of diameter w and >0, an approximate range query treats the range as a fuzzy object, meaning that points lying within distance w of the boundary of Q either may or may not be counted. We show that in any fixed dimension d, a set of n points in can be preprocessed in O(n+logn) time and O(n) space, such that approximate queries can be answered in O(logn(1/)d) time. The only assumption we make about ranges is that the intersection of a range and a d-dimensional cube can be answered in constant time (depending on dimension). For convex ranges, we tighten this to O(logn+(1/)d-1) time. We also present a lower bound for approximate range searching based on partition trees of (logn+(1/)d-1), which implies optimality for convex ranges (assuming fixed dimensions). Finally, we give empirical evidence showing that allowing small relative errors can significantly improve query execution times.

Given n data points in d-dimensional space, nearest neighbor searching involves determining the nearest of these data points to a given query point. Most averagecase analyses of nearest neighbor searching algorithms are made under the simplifying assumption that d is fixed and that n is so large relative to d that boundary effects can be ignored. This means that for any query point the statistical distribution of the data points surrounding it is independent of the location of the query point. However, in many applications of nearest neighbor searching (such as data compression by vector quantization) this assumption is not met, since the number of data points n grows roughly as 2 d. Largely for this reason, the actual performances of many nearest neighbor algorithms tend to be much better than their theoretical analyses would suggest. We present evidence of why this is the case. We provide an accurate analysis of the number of cells visited in nearest neighbor searching by the bucketing and k-d tree algorithms. We assume m d points uniformly distributed in dimension d, where m is a fixed integer ≥ 2. Further, we assume that distances are measured in the L ∞ metric. Our analysis is tight in the limit as d approaches infinity. Empirical evidence is presented showing that the analysis applies even in low dimensions.

Euclidean spanners are important data structures in geometric algorithm design, because they provide a means of approximating the complete Euclidean graph with only O(n) edges, so that the shortest path length between each pair of points is not more than a constant factor longer than the Euclidean distance between the points. In many applications of spanners, it is important that the spanner possess a number of additional properties: low tot al edge weight, bounded degree, and low diameter. Existing research on spanners has considered one property or the other. We show that it is possible to build spanners in optimal O (n log n) time and O(n) space that achieve optimal or near optimal tradeoffs between all combinations of these *Max-Planck-Institut fiir Informatik, D-66123 Saarbrucken, Germany. Email: {arya, michiel}@mpi-sb. mpg. de. Supported by the ESPRIT Basic Research Actions Program, under contract No. 7141 (project ALCOM 11). t Math Sciences Dept., The University of Memphis, Memphis, TN 38152. Supported in part by NSF Grant CCR9306822. E-mail: dasg@next 1.msci .memst . edu. i Department of Computer Science and Institute for Advanced Computer Studies, University of Maryland, College Park, Maryland. Partially supported by NSF Grant CCR-93107O5. This work was done while visiting the Max-Planck-Institut fiir Informatik, Saarbriicken. E-mail: mount @cs. umd. edu. SQue~Tech, IIIC., 7600A Leesburg Pike, Falls Church, VA 22043. This work was done while visiting the Max-Planck-Institut fiir Informatik, Saarbriicken. E-mail: jsalowet!nvl, army .mil. Permission to copy without fee all or part of thk material is granted provided that the copies are not made or distributed for direct commercial advantage, the ACM copyri ht notice and the title of thq publication and, is date appear, a#notice is given that copyt~isby~n,sslon of the Ass@ationof Computing Machinery. o cop otherwise, or to republish, requires a fee ancf/or speci ic permission. STOC’ 95, Las Vegas, Nevada, USA @ 1995 ACM 0-89791 -718-9/95/0005..$3.50 properties. We achieve these results in large part because of a new structure, called the dumbbell tree which provides a method of decomposing a spanner into a constant number of trees, so that each of the O(n2) spanner paths is mapped entirely to a path in one of these trees.

Let S be a set of n points in IR/sup d/ and let t>1 be a real number. A t-spanner for S is a directed graph having the points of S as its vertices, such that for any pair p and q of points there is a path from p to q of length at most t times the Euclidean distance between p and p. Such a path is called a t-spanner path. The spanner diameter of such a spanner is defined as the smallest integer D such that for any pair p and q of points there is a t-spanner path from p to q containing at most D edges. Randomized and deterministic algorithms are given for constructing t-spanners consisting of O(n) edges and having O(log n) diameter. Also, it is shown how to maintain the randomized t-spanner under random insertions and deletions. Previously, no results were known for spanners with low spanner diameter and for maintaining spanners under insertions and deletions.>

This paper shows that if one is willing to relax the requirement of finding the true nearest neighbor, it is possible to achieve significant improvements in running time and at only a very small loss in the performance of the vector quantizer. The authors present three algorithms for nearest neighbor searching: standard and priority k-d tree search algorithms and a neighborhood graph search algorithm in which a directed graph is constructed for the point set and edges join neighboring points.>