Sunil Arya
email: arya@cse.ust.hk

Guilherme D Da Fonseca

David M Mount
email: mount@cs.umd.edu

Approximate Polytope Membership Queries *

Keywords: Polytope membership, nearest-neighbor searching, geometric retrieval, space-time tradeoffs, approximation algorithms, convex approximation, Mahler volume

. 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 α ≥ 4, this data structure achieves query time roughly O 1/ε (d-1)/α and space roughly O 1/ε (d-1)(1-Ω(log α)/α) . 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 Ω 1/ε (d-1)(1-O( √ α)/α . 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 R d . For example, we show that it is possible to achieve a query time of roughly O(log n + 1/ε d/4 ) with space roughly O(n/ε d/4 ), thus reducing by half the exponent in the space bound.

Introduction

Convex polytopes are key structures in many areas of mathematics and computation. In this paper, we consider a fundamental search problem related to convex polytopes. Let K denote a convex body in R d , that is, a closed, convex set of bounded diameter that has a nonempty interior. We assume that K is presented as the intersection of n closed halfspaces. (Our results generally hold for any representation that satisfies the access primitives given at the start of Section 3.) The polytope membership problem is that of preprocessing K so that it is possible to determine efficiently whether a given query point q ∈ R d lies within K. Throughout, we assume that the dimension d is a fixed constant that is at least 2.

It follows from standard results in projective duality that polytope membership is equivalent to answering halfspace emptiness queries for a set of n points in R d . In dimension d ≤ 3, it is possible to build a data structure of linear size that can answer such queries in logarithmic time [START_REF] Berg | Computational Geometry: Algorithms and Applications[END_REF]. In higher dimensions, however, all known exact data structures with roughly linear space have a query time of Ω n1-1/ d/2 1 [START_REF] Matoušek | Reporting points in halfspaces[END_REF], which is unacceptably high for many applications. Polytope membership is a special case of polytope intersection queries [START_REF] Barba | Optimal detection of intersections between convex polyhedra[END_REF][START_REF] Chazelle | Intersection of convex objects in two and three dimensions[END_REF][START_REF] Dobkin | Fast detection of polyhedral intersection[END_REF]. Barba and Langerman [START_REF] Barba | Optimal detection of intersections between convex polyhedra[END_REF] showed that for any fixed d, it is possible to preprocess polytopes in R d so that given two such polytopes that have been translated and rotated, it can be determined whether they intersect each other in time that is logarithmic in their total combinatorial complexity. However, the preprocessing time and space grow as the combinatorial complexity of the polytope raised to the power d/2 .

The lack of efficient exact solutions motivates the question of whether polytope membership queries can be answered approximately. Let ε be a positive real parameter, and let diam(K) denote K's diameter. Given a query point q ∈ R d , an ε-approximate polytope membership query returns a positive result if q ∈ K, a negative result if the distance from q to its closest point in K is greater than ε • diam(K), and it may return either result otherwise (see Figure 1(a)). Polytope membership queries, both exact and approximate, arise in many application areas, such as linear-programming and ray-shooting queries [START_REF] Chan | Fixed-dimensional linear programming queries made easy[END_REF][START_REF] Chan | Optimal partition trees[END_REF][START_REF] Matoušek | On ray shooting in convex polytopes[END_REF][START_REF] Matoušek | Linear optimization queries[END_REF][START_REF] Ramos | Linear programming queries revisited[END_REF], nearest neighbor searching and the computation of extreme points [START_REF] Chan | Output-sensitive results on convex hulls, extreme points, and related problems[END_REF][START_REF] Clarkson | An algorithm for approximate closest-point queries[END_REF], collision detection [START_REF] Erickson | Separation-sensitive collision detection for convex objects[END_REF], and machine learning [START_REF] Burges | A tutorial on support vector machines for pattern recognition[END_REF]. Existing solutions to approximate polytope membership queries have been based on straightforward applications of classic polytope approximation techniques. We say that a polytope P is an outer ε-approximation of K if K ⊆ P , and the Hausdorff distance between P and K is at most ε • diam(K) (see Figure 1(b)). An inner ε-approximation is defined similarly but with P ⊆ K. Dudley [START_REF] Dudley | Metric entropy of some classes of sets with differentiable boundaries[END_REF] showed that there exists an outer ε-approximating polytope for any bounded convex body in R d formed by the intersection of O 1/ε (d-1)/2 halfspaces, and Bronshteyn and Ivanov [START_REF] Bronshteyn | The approximation of convex sets by polyhedra[END_REF] proved an analogous bound on the number of vertices needed to obtain an inner ε-approximation. Both bounds are known to be asymptotically tight in the worst case (see, e.g., [START_REF] Bronstein | Approximation of convex sets by polytopes[END_REF]). These results have been applied to a number of problems, for example, the construction of coresets [START_REF] Agarwal | Geometric approximation via coresets[END_REF]. By checking that a given query point lies within each of the halfspaces of Dudley's approximation, ε-approximate polytope membership queries can be answered with space and query time of O 1/ε (d-1)/2 .

ε • diam(K) K P (
The principal contribution of this paper is to show that it is possible to achieve nontrivial space-time trade-offs for approximate polytope membership. In order to motivate our methods, in Section 2 we present a simple space-time trade-off (stated in the following theorem), which is based on a straightforward combination of the approximations of Dudley [START_REF] Dudley | Metric entropy of some classes of sets with differentiable boundaries[END_REF] and Bentley et al. [START_REF] Bentley | Approximation algorithms for convex hulls[END_REF]. Throughout, we will treat n and ε as asymptotic quantities, while the dimension d is a constant.

Theorem 1 (Simple Trade-off). Given a convex polytope K in R d , a positive approximation parameter ε, and a real parameter α ≥ 2, there is a data structure for ε-approximate polytope membership queries that achieves Query time:

O 1/ε d-1 α Space: O 1/ε (d-1)(1-1 α ) .
The constant factors in the space and query time depend only on d (not on K, α, or ε).

We will strengthen this trade-off significantly in Sections 3 and 4. We will show that it is possible to build a data structure with O 1/ε (d-1)/2 space that allows polytope membership queries to be answered in roughly O 1/ε (d-1)/8 time, thus reducing the exponent in the query time of Theorem 1 (for α = 2) by 1/4. Further, we will show that by iterating a suitable generalization of this construction, we can obtain the following trade-offs.

Theorem 2. Given a convex polytope K in R d , an approximation parameter 0 < ε ≤ 1, and a real constant α ≥ 4, there is a data structure for ε-approximate polytope membership queries that achieves Query time:

O (log 1 ε )/ε d-1 α Space: O 1/ε (d-1) 1- 2 lg α -2 α
.

The constant factors in the space and query time depend only on d and α (not on K or ε).

The above space bound is a simplification, and the exact bound is given in Lemma 6.4. Both bounds are piecewise linear in 1/α (with breakpoints at powers of two), but the bounds of Lemma 6.4 are continuous as a function of α. The resulting space-time trade-off is illustrated below in Figure 2(a). (The plot reflects the more accurate bounds.)

The above theorem is intentionally presented in a purely existential form. This is because our construction algorithm assumes the existence of a procedure that computes an ε-approximating polytope whose number of bounding hyperplanes is at most a constant factor larger than optimal. Unfortunately, we know of no efficient solution to this problem. In Lemma 7.6 we will show that, if the input polytope is expressed as the intersection of n halfspaces, it is possible to build such a structure in time O n+1/ε O (1) , such that the space and query times of the above theorem increase by an additional factor of O(log 1 ε ). Note that, in contrast to many complexity bounds in the area of convex approximation, which hold only in the limit as ε approaches zero (see, e.g., [START_REF] Gruber | Asymptotic estimates for best and stepwise approximation of convex bodies I[END_REF][START_REF] Boroczky | Approximation of general smooth convex bodies[END_REF]), Theorems 1 and 2 hold for any positive ε ≤ 1.

The data structure of Theorem 2 is quite simple. It is based on a quadtree subdivision of space in which each cell is repeatedly subdivided until the combinatorial complexity of the approximating polytope within the cell is small enough to achieve the desired query time.

We do not know whether the upper bounds presented in Theorem 2 are tight for our algorithm. In Section 8, we establish the following lower bound on the trade-off achieved by this algorithm. Theorem 3. In any fixed dimension d ≥ 2 and for any constant α ≥ 4, there exists a polytope such that for all sufficiently small positive ε, the data structure described in Theorem 2 when generated to achieve query time O 1/ε (d-1)/α has space

Ω 1/ε (d-1) 1-2 √ 2α-3 α -1 .
Although α is not an asymptotic quantity, for the sake of comparing the upper and lower bounds, let us imagine that it is. For roughly the same query time, the α dependencies appearing in the exponents of the upper bounds on space are 1 -1 α for Theorem 1, 1 -Ω(log α) α for Theorem 2, and the lower bound of Theorem 3 is roughly 1

-O( √ α) α
. The trade-offs provided in these theorems are illustrated in Figure 2(a). The second major contribution of this paper is to demonstrate that our trade-offs for approximate polytope membership queries imply significant improvements to the best known space-time trade-offs for approximate nearest neighbor searching (ANN). We are given a set X of n points in R d . Given any q ∈ R d , an ε-approximate nearest neighbor of q is any point of X whose distance from q is at most (1 + ε) times the distance to q's closest point in X. The objective is to preprocess X in order to answer such queries efficiently. Data structures for approximate nearest neighbor searching (in fixed dimensions) have been proposed by several authors [START_REF] Chan | Closest-point problems simplified on the RAM[END_REF][START_REF] Clarkson | An algorithm for approximate closest-point queries[END_REF][START_REF] Duncan | Balanced aspect ratio trees: Combining the advantages of k-d trees and octrees[END_REF][START_REF] Har-Peled | A replacement for Voronoi diagrams of near linear size[END_REF][START_REF] Sabharwal | Nearest neighbors search using point location in balls with applications to approximate Voronoi decompositions[END_REF]. The best space-time trade-offs [START_REF] Arya | Space-time tradeoffs for approximate nearest neighbor searching[END_REF] have query times roughly O 1/ε d/α with storage roughly O n/ε d(1-2/α) , for α ≥ 2 (see the dashed line in Figure 2(b)).

These results are based on a data structure called an approximate Voronoi diagram (or AVD). In general, a data structure for approximate nearest neighbor searching is said to be in the AVD model if it has the general form of decomposition of space (generally a covering) by hyperrectangles of bounded aspect ratio, each of which is associated with a set of representative points. Given any hyperrectangle that contains the query point, at least one of these representatives is an ε-approximate nearest neighbor of the query point [START_REF] Arya | Space-time tradeoffs for approximate nearest neighbor searching[END_REF]. The AVD model is of interest because it is possible to prove lower bounds on the performance of such a data structure. In particular, the lower bounds proved in [START_REF] Arya | Space-time tradeoffs for approximate nearest neighbor searching[END_REF] are shown in the dotted curve in Figure 2(b). By violating the AVD model, small additional improvements were obtained in [START_REF] Arya | A unified approach to approximate proximity searching[END_REF].

Our improvements to ANN searching are given in the following theorem.

Theorem 4. Let 0 < ε ≤ 1 be a real parameter, α ≥ 1 be a real constant, and X be a set of n points in R d . There is a data structure in the AVD model for approximate nearest neighbor searching that achieves Query time:

O log n + (1/ε d/2α ) • log 2 1 ε Space: O n • max log 1 ε , 1/ε d( 1 2 -1 2α ) , for 1 ≤ α < 2 and, O n/ε d 1- lg α α -1 2α
, for α ≥ 2.

The constant factors in the space and query time depend only on d and α (not on ε).

The above space bound is a simplification of the more accurate bound given in Lemma 9.5. (Also see the remarks following the proof of this lemma for further minor improvements achievable by forgoing the AVD model.) As before, both bounds are piecewise linear in 1/α (with breakpoints at powers of two), but the bounds of Lemma 9.5 are continuous as a function of α. The resulting space-time trade-off is illustrated in Figure 2(b). (The plot reflects the more accurate bounds of Lemma 9.5.)

As an example of the strength of the improvement that this offers, observe that in order for the existing AVD-based results to yield a query time of O 1/ε d/4 the required space would be roughly Ω n/ε d/2 . The exponent in the space bound is nearly twice that given by Theorem 4, which arises by setting α = 2. The connection between the polytope membership problem and ANN has been noted before by Clarkson [START_REF] Clarkson | An algorithm for approximate closest-point queries[END_REF]. Unlike Clarkson's, our results hold for point sets with arbitrary aspect ratios.

Our data structure is based on a simple quadtree-based decomposition of space. Let t denote the desired query time. We begin by preconditioning K so that it is fat and has at most unit diameter. We then employ a quadtree that hierarchically subdivides space into hypercube cells. The decomposition stops whenever we can declare that a cell is either entirely inside or outside of K, or (if it intersects K's boundary) it is locally approximable by at most t halfspaces. This procedure, called SplitReduce is presented in Section 3. Queries are answered by descending the quadtree to determine the leaf cell containing the query point, and (if not inside or outside) testing whether the query point lies within the approximating halfspaces.

Although the algorithm itself is very simple, the analysis of its space requirements is quite involved. In Section 4, we begin with a simple analysis, which shows that it is possible to obtain a significant improvement over the Dudley-based approach (in particular, reducing the exponent in the query time by half with no increase in space). While this simple analysis introduces a number of useful ideas, it is neither tight nor does it provide space-time trade-offs.

Our final analysis requires a deeper understanding of the local structure of the convex body's boundary. In Section 5 we introduce local surface patches of K's boundary, called ε-dual caps. We relate the data structure's space requirements to the existence of a low cardinality hitting set of the dual caps. We present a two-pronged strategy for generating such a hitting set, one focused on dual caps of large surface area (intuitively corresponding to boundary regions of low curvature) and the other focused on dual caps of small surface area (corresponding to boundary regions of high curvature). We show that simple random sampling suffices to hit dual caps of high surface area, and so the challenge is to hit the dual caps of low surface area. To do this, we show that dual caps of low surface area generate Voronoi patches on a hypersphere enclosing K of large surface area. We refer to this result as the area-product bound, which is stated in Lemma 5.2. This admits a strategy based on sampling points randomly on this hypersphere, and then projecting them back to their nearest neighbor on the surface of K.

The area-product bound is proved with the aid of a classical concept from the theory of convexity, called the Mahler volume [START_REF] Bourgain | New volume ratio properties for convex symmetric bodies[END_REF][START_REF] Santaló | An affine invariant for convex bodies of n-dimensional space[END_REF]. The Mahler volume of a convex body is a dimensionless quantity that involves the product of the body's volume and the volume of its polar body. We demonstrate that dual caps and their Voronoi patches exhibit a similar polar relationship. The proof of the area-product bound is quite technical and is deferred to Section 10.

Armed with the area-product bound, in Section 6 we establish our final bound on the space-time trade-offs of SplitReduce, which culminates in the proof of Theorem 2. In Section 7 we present details on how the data structure is built and discuss preprocessing time. In Section 8 we establish the lower bound result, which is stated in Theorem 3.

Finally, in Section 9 we show how these results can be applied to improve the performance of approximate nearest neighbor searching in Euclidean space. It is well known that (exact) nearest neighbor searching can be reduced to vertical ray shooting to a polyhedron that results by lifting points in dimension d to tangent hyperplanes for a paraboloid in dimension d + 1 [START_REF] Agarwal | Ray shooting and parametric search[END_REF][START_REF] Edelsbrunner | Algorithms in Combinatorial Geometry[END_REF]. We show how to combine approximate vertical ray shooting (based on approximate polytope membership) with approximate Voronoi diagrams to establish Theorem 4.

Preliminaries

Throughout, we will use asymptotic notation to eliminate constant factors. In particular, for any positive real x, let O(x) denote a quantity that is at most cx, for some constant c. Define Ω(x) and Θ(x) analogously. We will sometimes introduce constants within a local context (e.g., within the statement of single lemma). To simplify notation, we will often use the same symbol "c" to denote such generic constants. Recall that we use "lg" to denote the base-2 logarithm. We will use "log" when the base does not matter. Some of our search algorithms involve integer grids, and for these we assume a model of computation that supports integer division.

Let K denote a full-dimensional convex body in R d , and let ∂K denote its boundary. For concreteness, we assume that K is represented as the intersection of n closed halfspaces. Our data structure can generally be applied to any representation that supports access primitives (i)-(iii) given at the start of Section 3.

Absolute and Relative Approximations

Earlier, we defined approximation relative to K's diameter, but it will be convenient to define the approximation error in absolute terms. Given a positive real r, define K ⊕ r to be set of points that lie within Euclidean distance r of K. We say that a polytope P is an absolute ε-approximation of a convex body K if

K ⊆ P ⊆ K ⊕ ε.
When we wish to make the distinction clear, we refer to the definition in the introduction as a relative approximation. Henceforth, unless otherwise stated approximations are in the absolute sense.

In order to reduce the general approximation problem into a more convenient absolute form, we will transform K into a "fattened" body of bounded diameter. Given a parameter 0 < γ ≤ 1, we say that a convex body K is γ-fat if there exist concentric Euclidean balls B and B , such that B ⊆ K ⊆ B , and radius(B)/radius(B ) ≥ γ. We say that K is fat if it is γ-fat for a constant γ (possibly depending on d, but not on n or ε). The following lemma shows that K can be fattened without significantly altering the approximation parameter. Let Q (d) 0 denote the d-dimensional axis-aligned hypercube of unit diameter centered at the origin. When d is clear, we refer to this as Q 0 .

Lemma 2.1. Given a convex body K in R d and 0 < ε ≤ 1, there exists an affine transformation T such that

T (K) is (1/d)-fat and T (K) ⊆ Q 0 . If P is an absolute (ε/d √ d)-approximation of T (K), then T -1 (P ) is a relative ε-approximation of K.
We omit the proof of this lemma for now, since it is subsumed by Lemma 7.1 below. Our approach will be to map K to T (K), set ε ← ε/d √ d, and then apply an absolute ε -approximation algorithm to T (K) (or more accurately, to the result of applying T to each of K's defining halfspaces). Since ε is within a constant factor of ε, the asymptotic complexity bounds that we will prove for the absolute case will apply to the original (relative) approximation problem case as well.

Concepts from Quadtrees

By the above reduction, it suffices to consider the problem of computing an absolute ε-approximation to a fat convex body K that lies within Q 0 . Our construction will be based on a quadtree decomposition of Q 0 . More formally, we define a quadtree cell by the following well known recursive decomposition. Q 0 is a quadtree cell, and given any quadtree cell Q, each of the 2 d hypercubes that result by bisecting each of Q's sides by an axis-orthogonal hyperplane is also a quadtree cell. A cell Q that results from subdividing Q is a child of Q. Clearly, the child's diameter is half that of its parent. The subdivision process defines a (2 d )-ary tree whose nodes are quadtree cells, and whose leaves are cells that are not subdivided.

It will be useful to define a notion of approximation that is local to a quadtree cell Q. An obvious definition would be to approximate K ∩ Q. The problem with this is that a point p ∈ Q that is close to K need not be close to K ∩ Q (see Figure 3(a)). To remedy this we say that a polytope P is an 3(b)). This definition implies that for any query point q ∈ Q, we can correctly answer ε-approximate polytope membership queries with respect to K by checking whether q ∈ P . We do not care what happens outside of Q, and indeed P may even be unbounded.

ε-approximation of K within Q if K ∩ Q ⊆ P ∩ Q ⊆ (K ⊕ ε) ∩ Q (see Figure
As we shall see later, computing an ε-approximation of K within a quadtree cell Q, will generally require that we consider ∂K in a region that extends slightly beyond Q. We define E δ (K, Q) to be the portion of ∂K that lies within distance δ of Q (see Figure 3(c)). Because δ = √ ε will be of particular interest, we use E(K, Q) as a shorthand for E √ ε (K, Q). In order to apply constructions on quadtree cells of various sizes, it will be convenient to transform all such constructions into a common form. Given a quadtree cell Q, we define standardization to be the application of an affine transformation that uniformly scales and translates space so that Q is aligned

E δ (K, Q) δ Q K (c) (b) Q (a) K K ∩ Q Q K p K ∩ Q P ≤ ε p Figure 3: (a) and (b): ε-approximation of K within Q and (c): E δ (K, Q).
with the standard quadtree cell Q 0 . We transform K using this same transformation, and apply the same scale factor to ε. Although we assume that the input body is contained within Q 0 , after standardization, the transformed image of K need not be contained within Q 0 .

Polarity and the Mahler Volume

Some of our analysis will involve the well known concept of polarity. Let us recall some general facts (see, e.g., Eggleston [START_REF] Eggleston | Convexity[END_REF]). Given vectors u, v ∈ R d , let u, v denote their inner product, and let v = v, v denote v's Euclidean length. Given a convex body K ∈ R d define its polar to be the convex set

polar(K) = {u : u, v ≤ 1, for all v ∈ K}.
If K contains the origin then polar(K) is bounded. Given v ∈ R d , polar(v) is simply the closed halfspace that contains the origin whose bounding hyperplane is orthogonal to v and at distance 1/ v from the origin (on the same side of the origin as v). The polar has the inclusion-reversing property that v lies within polar(u) if and only if u lies within polar(v). We may equivalently define polar(K) as the intersection of polar(v), for all v ∈ K.

Generally, given r > 0, define

polar r (K) = {u : u, v ≤ r 2 , for all v ∈ K}.
It is easy to see that for any v ∈ R d , polar r (v) is the closed halfspace at distance r 2 / v (see Figure 4(a)). Thus, polar r (K) is a uniform scaling of polar(K) by a factor of r 2 . In particular, if B is a Euclidean ball of radius x centered at the origin, then polar r (B) is a concentric ball of radius r 2 /x.

(b) (a) r v r 2 / v polar r (v) polar r (K) K Figure 4:
The generalized polar transform and polar body.

An important concept related to polarity is the Mahler volume, which is defined to be the product of the volumes of a convex body and its polar. There is a large literature on the Mahler volume, mostly for centrally symmetric bodies. Later in the paper we will make use of the following bound on the Mahler volume for arbitrary convex bodies (see, e.g., Kuperberg [40]). Given a convex body K in R d , let vol(K) denote its volume, or more formally, its d-dimensional Hausdorff measure.

Lemma 2.2 (Mahler volume).

There is a constant c m depending only on d, such that given a convex body

K in R d , vol(K) • vol(polar(K)) ≥ c m . More generally, given r > 0, vol(K) • vol(polar r (K)) ≥ c m r 2d .

Simple Approximation Trade-off

Before presenting our results, it will be illuminating to see how to obtain simple data structures for approximate polytope membership by combining two existing approximation methods. Let us begin by describing Dudley's approximation. Assuming that K is contained within Q 0 , let S denote the (d -1)dimensional sphere of radius 3 centered at the origin, which we call the Dudley hypersphere. (The value 3 is not critical; any sufficiently large constant suffices.) For δ > 0, a set Σ of points on S is said to be δ-dense if every point of S lies within distance δ of some point of Σ. Let Σ be a √ ε-dense set of points on S (see Figure 5(a)). By a simple packing argument there exists such a set of cardinality Θ 1/ε (d-1)/2 . For each point x ∈ Σ, let x 0 be its nearest point on K's boundary. For each such point x 0 , consider the halfspace containing K that is defined by the supporting hyperplane passing through x 0 that is orthogonal to the line segment xx 0 . Dudley shows that the intersection of these halfspaces is an outer ε-approximation of K. We can answer approximate membership queries by testing whether q lies within all these halfspaces (by brute force). This approach takes O 1/ε (d-1)/2 query time and space. An alternative solution is related to a grid-based approximation by Bentley et al. [START_REF] Bentley | Approximation algorithms for convex hulls[END_REF]. Again, we assume that K is contained within Q 0 . For the sake of illustration, let us think of the d-th coordinate axis as pointing upwards. Partition the upper facet of Q 0 into a (d -1)-dimensional square grid with cells of diameter ε. A packing argument implies that the number of cells is O(1/ε d-1 ). Extend each of these cells downwards to form a subdivision of Q 0 into vertical columns (see Figure 5(b)). Trim each column at the highest and lowest points at which it intersects K. Together, these trimmed columns define a collection of hyperrectangles whose union contains K. The resulting data structure has O(1/ε d-1 ) space. Given a query point q, in O(1) time we can determine the vertical column containing q (assuming a model of computation that supports integer division), and we then test whether q lies within the trimmed column. In contrast to the method based on Dudley's construction, this method provides a better query time of O(1) but with higher space of O(1/ε d-1 ).

q r K K x x 0 S ≤ √ ε q ε K (a) (b) (c)
It is possible to combine these two solutions into a simple unified approach that achieves a trade-off between space and query time. Given a parameter r, where ε ≤ r ≤ 1, subdivide Q 0 into a grid of hypercube cells each of diameter Θ(r). For each cell Q that intersects K's boundary, apply Dudley's approximation to this portion of the polytope. By a straightforward packing argument, the number of grid cells that intersect K's boundary is O(1/r d-1 ) (see, for example, Lemma 3 of [START_REF] Arya | Approximate range searching[END_REF]). We apply standardization to Q (thus mapping Q to Q 0 and scaling ε to Ω(ε/r)) and apply Dudley's construction. By Dudley's results, the number of halfspaces needed to approximate

K within Q is O (r/ε) (d-1)/2 .
To answer a query, in O(1) time we determine which hypercube of the grid contains the query point (assuming a model of computation that supports integer division). We then apply brute-force search to determine whether the query point lies within all the associated halfspaces in time O (r/ε) (d-1)/2 . The query time is dominated by this latter term. The space is dominated by the total number of halfspaces, which is O (1/r d-1 ) • (r/ε) (d-1)/2 = O 1/(εr) (d-1)/2 . If we express r in terms of a parameter α, where r = ε 1-2/α , then Theorem 1 follows as an immediate consequence. Note that the resulting trade-off interpolates nicely between the two extremes for ε ≤ r ≤ 1.

The Data Structure and Construction

In this section we show how to improve the approach from the previous section by replacing the grid with a quadtree. The data structure is constructed by the recursive procedure, called SplitReduce, whose inputs consist of a convex body K and a quadtree cell Q. We are also given the approximation parameter 0 < ε ≤ 1, and a parameter t ≥ 1 that controls the query time. Although we assume that K is presented as the intersection of n halfspaces, this procedure can be applied to any representation that supports the following access primitives: (i) Determine whether Q is disjoint from K.

(ii) Determine whether Q is contained within K ⊕ ε.

(iii) Determine whether there exists a set of at most t halfspaces whose intersection ε-approximates K within Q, and if so generate such a set.

Recall that we assume that K has been transformed so it is (1/d)-fat and lies within Q 0 (the hypercube of unit diameter centered at the origin). The data structure is built by the call SplitReduce(K, Q 0 ). In general, SplitReduce(K, Q) checks whether any of the above access primitives returns a positive result, and if so it terminates the decomposition and Q is declared a leaf cell. Otherwise, it makes a recursive call on the children of Q (see Figure 6(a)). On termination, each leaf cell is labeled as either "inside" or "outside" or is associated with a set of at most t approximating halfspaces (see Figure 6(b)). SplitReduce(K, Q):

(1) If Q ∩ K = ∅, label Q as "outside." (2) If Q ⊆ K ⊕ ε, label Q as "inside."
(3) If there exists a set at most t halfspaces whose intersection provides an ε-approximation to K within Q, associate Q with such a set P (Q) of minimum size. (4) Otherwise, split Q into 2 d quadtree cells and recursively invoke SplitReduce on each.

For the sake of our space-time trade-offs, we will usually assume that t is reasonably large, say, t = Ω(log 1 ε ). Under our assumption that t ≥ 1, steps (1) and ( 2) are not needed, since it is possible to ε-approximate any cell satisfying these conditions with a single halfspace. This assumption on the value of t is mainly a convenience to simplify the formulas of our mathematical analysis. Observe that even if t = 0, the procedure will terminate and provide a correct answer once the cell diameter falls below ε.

It is easy to see that the recursion must terminate as soon as diam(Q) ≤ ε (since, irrespective of whether it intersects ∂K, any such cell can be labeled either as "inside" or "outside"). Of course, it may terminate much sooner. Since Q 0 is of unit diameter, it follows that the height of the quadtree is O(log 1 ε ). The total space used by the data structure is the sum of the space needed to store the quadtree and the space needed to store the approximating halfspaces for the cells that intersect K's boundary. Our next lemma shows that if the query time is sufficiently large, the latter quantity dominates the space asymptotically. For each leaf cell Q generated by Step (3), define t(Q) = |P (Q)|, and define t(Q) = 1 for all the other leaf cells.

Lemma 3.1. Given a convex body K ⊆ Q 0 in R d . If t is Ω(log 1
ε ), then the total space of the data structure produced by SplitReduce(K, Q 0 ) on K for query time t is asymptotically dominated by the sum of t(Q) over all the leaf cells Q that intersect K's boundary.

Proof : Let T denote the quadtree produced by running SplitReduce on K. As mentioned above, T is of height O(log 1 ε ). By our hypothesis that t is Ω(log 1 ε ), there exists a constant c such that height(T ) ≤ ct. Let L denote the set of leaves of T that intersect the boundary of K, and let M denote the internal nodes of T that have the property that all their children are leaves. (These are the lowest internal nodes of the tree.) Let t(L) denote the sum of t(Q) over all Q ∈ L.

The fact that each node u ∈ M was subdivided by SplitReduce implies that more than t halfspaces are needed to approximate K within u's cell. Therefore, the children of u that intersect K's boundary together require at least t halfspaces. In addition to P (Q), each quadtree leaf Q can (implicitly) contribute its 2d bounding hyperplanes to the approximation. Therefore, t(L) + 2d|L| hyperplanes suffice to approximate K in all the cells of M , implying that t(L)

+ 2d|L| ≥ t • |M |. Since t(Q) ≥ 1, we have t(L) ≥ |L|, and thus (1 + 2d)t(L) ≥ t • |M |.
Each internal node of T is either in M or is an ancestor of a node in M . Thus, the total number of internal nodes of T is at most |M | • height(T ). Since each internal node of a quadtree has 2 d children, the total number of nodes in the tree, excluding the root, is at most

2 d • |M | • height(T ) ≤ 2 d • |M | • (ct) ≤ 2 d c(1 + 2d)t(L) = O(t(L)).
Each internal node of T and each leaf node that does not intersect K's boundary contributes only a constant amount to the total space. Therefore, the space contribution of the nodes other than those of L is at most a constant factor larger than the total number of nodes of T , which we have shown is O(t(L)). Therefore, the total space is O(t(L)), as desired.

A query is answered by performing a point location in the quadtree to determine the leaf cell containing the query point. If the leaf cell is not labeled as being "inside" or "outside", we test whether the query point lies within all the associated halfspaces, and if so, we declare the point to be inside K. Otherwise it is declared to be outside. Clearly, the query time is O(log 1 ε + t). The algorithm is correct provided that the set of halfspaces P (Q) computed in Step (3) defines any ε-approximation of K within Q, but our analysis of the data structure's space requirements below (see the proof of Lemma 4.3) relies on the assumption that the size of P (Q) is within a constant factor of the minimum number of halfspaces of any ε-approximating polytope within Q. Unfortunately, we know of no constant-factor approximation to the problem of computing such a polytope. Thus, strictly speaking, the bounds stated in Theorem 2 are purely existential. In Section 7 we will show that through a straightforward modification of the greedy set-cover heuristic, it is possible to compute an approximation in which the number of defining halfspaces exceeds the optimum (for slightly smaller approximation parameter) by a factor of at most ρ = O(log 1 ε ). From the following result it follows that this increases our space and query time bounds by O(log 1 ε ). Lemma 3.2. Given any ρ ≥ 1 and any constant 0 < β ≤ 1, if the number of halfspaces of P (Q) computed in Step (3) of SplitReduce is within a factor ρ of the minimum number of facets of any (βε)approximating polytope within Q, then Theorems 2 and 4 hold but with the asymptotic space and query time bounds larger by a factor of ρ.

Proof : Let us refer to the hypothesized version of SplitReduce whose Step (3) is suboptimal as SplitReduce . Consider an execution of SplitReduce using ρt as the desired query time and ε as the approximation parameter, and let us compare this to an execution of SplitReduce using t and βε, respectively. Since β is a constant, the asymptotic dependencies on ε are unaffected, and therefore the space and query times stated in Theorems 2 and 4 apply without modification to the execution of SplitReduce. In this execution, if the subdivision declares some quadtree cell Q to be a leaf, then t halfspaces suffice to (βε)-approximate K within Q, and so by our hypothesis in the corresponding execution of SplitReduce , Step (3) returns at most ρt halfspaces, implying this execution also declares Q to be a leaf. Therefore, the tree generated by SplitReduce is a subtree of the tree generated by SplitReduce, but each leaf node may contain up to a factor of ρ more halfspaces. Thus, the asymptotic space and query time bounds for SplitReduce are larger than those of SplitReduce by this same factor.

Simple Upper Bound

In this section, we present a simple upper bound of O 1/ε (d-1)/2 on the storage of the data structure obtained by the SplitReduce algorithm for any given query time t ≥ 1/ε (d-1)/4 . The tools developed in this section will be useful for the more comprehensive upper bounds, which will be presented in subsequent sections.

Throughout this section we do not necessarily assume that K has been scaled to lie within Q 0 and may generally be much larger. Recall that S denotes a hypersphere of radius 3 centered at the origin. Let X denote a surface patch of K that lies within S. Let Vor(X) denote the set of points exterior to K whose closest point on ∂K lies within X. We refer to the surface patch Vor(X) ∩ S (the points of S whose closest point on ∂K lies within X) as the Voronoi patch of X. Voronoi patches are related to Dudley's construction. In particular, a sample point x ∈ S from Dudley's construction generates a supporting halfspace at a point of X if and only if x ∈ Vor(X) ∩ S. The following two lemmas are straightforward adaptations of Dudley's analysis [START_REF] Dudley | Metric entropy of some classes of sets with differentiable boundaries[END_REF]. The first is just a restatement of Dudley's result. Lemma 4.1. Given a convex body K in R d that lies within Q 0 and 0 < ε ≤ 1, there exists an εapproximating polytope P bounded by at most c/ε (d-1)/2 facets, where c is a constant depending only on d.

The second lemma is a technical result that is implicit in Dudley's analysis. Given two points x, y ∈ R d , let xy denote the segment between them, and let xy denote the Euclidean length of this segment.

Lemma 4.2. Let K be a convex body, let 0 < ε ≤ 1, and let z and x be two points of S such that zx ≤ √ ε/4. Let z 0 and x 0 be the points on ∂K that are closest to z and x, respectively. If z 0 is within unit distance of the origin, then

(i) z 0 x 0 ≤ √ ε/4 and
(ii) the supporting hyperplane at x 0 orthogonal to the segment xx 0 intersects segment zz 0 at distance less than ε from z 0 (see Figure 7). The following lemma is an extension of Dudley's results, which allows us to bound the complexity of an ε-approximation of K within a quadtree cell Q. Recall from Section 2.2 that E(K, Q) denotes portion of ∂K that lies within distance √ ε of Q.

Lemma 4.3. Let K be a convex body, Q ⊆ Q 0 be a quadtree cell that intersects ∂K, and 8(a)).

0 < ε ≤ 1/2. Let Σ denote a set of ( √ ε/4)-dense points on the Dudley sphere S. Then t(Q) ≤ |Σ ∩ Vor(E(K, Q))| (see Figure
Proof : We construct an approximating polytope P by the following local variant of Dudley's construction. For each point x ∈ Σ ∩ Vor(E(K, Q)), let x 0 be its nearest point on the boundary of K. (Note that x 0 ∈ E(K, Q).) For each point x 0 , take the supporting halfspace to K passing through x 0 that is orthogonal to the segment xx 0 . Let P be the (possibly unbounded) intersection of these halfspaces.

First, we show that Σ ∩ Vor

(E(K, Q)) is nonempty. Consider any point z 0 on ∂K ∩ Q. Let z denote any point of S ∩ Vor(E(K, Q)) whose closest point on ∂K is z 0 . By definition of Σ, there is a point x ∈ Σ whose distance from z is at most √ ε/4. Letting x 0 denote x's closest point on ∂K, by Lemma 4.2(i), z 0 x 0 ≤ √ ε/4 < √ ε. Thus, x 0 lies within E(K, Q), which implies that x ∈ Σ ∩ Vor(E(K, Q)).
It follows that P is bounded by at least one halfspace.

We now show that P is an (outer) ε-approximation of K within Q. Since P is defined by supporting hyperplanes, K is contained within P . Consider any q ∈ Q that is at distance greater than ε from K. It suffices to show that q / ∈ P , that is, there exists a bounding hyperplane for P that separates q from K. Let q 0 denote the point of K ∩ Q that is closest to q (see Figure 8(b)). Note that q 0 is constrained to lie within Q, and hence this may not be the closest point to q on ∂K. By continuity, there must be a point on the segment qq 0 that is at distance exactly ε from ∂K, which we denote by q ε . Since Q is convex, this segment is contained in Q, and, hence, so is q ε . Let z 0 be the point on ∂K that is closest to q ε . (Note that z 0 need not lie within Q.)

(b) (a) E(K, Q) S q ε z 0 x x 0 q Q z q 0 Q 0 Q E(K, Q) S K Σ ∩ Vor(E(K, Q)) h
Because Q 0 is centered at the origin, z 0 's distance from the origin is at most diam(Q 0 )/2 + q ε z 0 ≤ 1/2 + ε ≤ 1.
Let z denote the point of intersection with the Dudley hypersphere S of the ray emanating from z 0 and passing through q ε . Let x be a point of Σ that lies within distance √ ε/4 of z , and let x 0 be its closest point on ∂K. By Lemma 4.2(i) x 0 z 0 ≤ √ ε/4, and (ii) the supporting hyperplane h at x 0 orthogonal to the segment x x 0 intersects segment z z 0 at distance less than ε from z 0 . Thus, h separates q ε from K, and therefore it separates q from K.

To complete the proof that q / ∈ P , it suffices to show that h is indeed included in our construction of P . By the triangle inequality and our assumption that ε ≤ 1/2, the distance from x 0 to Q is at most

x 0 z 0 + z 0 q ε ≤ √ ε 4 + ε ≤ √ ε.
It follows that x 0 ∈ E(K, Q), and so h is included in the construction of P . By our hypothesis that the set

P (Q) constructed in Step (3) of SplitReduce is the minimum-sized set of halfspaces needed to ε-approximate K within Q, we have t(Q) = |P (Q)| ≤ |P | = |Σ ∩ Vor(E(K, Q))|.
(Note that this works even if Q is an "inside" cell that intersects K's boundary. In such a case t(Q) = 1 by definition, and as argued above, Σ ∩ Vor(E(K, Q)) is nonempty.) This completes the proof.

Next, we prove a useful technical lemma, which bounds the total complexity of a set of leaves whose cells are of a given minimum size. Recalling the definition of Σ from the previous lemma, we may assume that |Σ| = Θ 1/ε (d-1)/2 . Lemma 4.4. Let K be a convex body in R d , let 0 < ε ≤ 1/2, and let L denote a set of disjoint quadtree cells contained within Q 0 such that each intersects ∂K and is of diameter

Ω( √ ε). Then Q∈L t(Q) = O 1/ε (d-1)/2 . Proof : By applying Lemma 4.3 to each Q ∈ L we have Q∈L t(Q) ≤ Q∈L |Σ ∩ Vor(E(K, Q))|. Since |Σ| = O 1/ε (d-1)/2 ,
to complete the proof it suffices to show that each x ∈ Σ lies within Vor(E(K, Q)) for at most constant number of Q ∈ L. To see this, let x 0 be the point on ∂K that is closest to x. Since each cell Q ∈ L has size at least Ω( √ ε), by disjointness and a packing argument it follows that at most a constant number (depending on dimension) of such cells can lie within distance √ ε of x 0 , which establishes the claim.

Combining the above results, we obtain the main result of this section.

Lemma 4.5. Let K be a convex body in R d and 0

< ε ≤ 1/2. The output of SplitReduce(K, Q 0 ) for t ≥ 1/ε (d-1)/4 has total space O 1/ε (d-1)/2 .
Proof : Let c 2 be the constant of Lemma 4.1, and define 1) . We may assume that ε ≤ c 2 1 , for otherwise ε = Ω(1) and clearly SplitReduce will not generate more than a constant number of cells.

c 1 = (1/c 2 ) 2/(d-
Let T denote the quadtree produced by the algorithm, and let L denote the set of leaf cells of T that intersect the boundary of K. Recall from Lemma 3.1 that the data structure's total space is asymptotically bounded by the sum of t(Q) for all Q ∈ L. Thus, it suffices to prove that

Q∈L t(Q) = O 1/ε (d-1)/2 .
Towards this end, we first prove a lower bound on the size of any leaf cell Q. We assert that the cell Q associated with any internal node has diameter at least δ = c 1 √ ε. It will then follow that each leaf cell has diameter at least δ/2. Suppose to the contrary that diam(Q) < δ. Recall the standardization transformation from Section 2.2, which maps Q to Q 0 and scales ε to at least ε/δ = √ ε/c 1 . Let us denote this value by ε . Since ε ≤ c 2 1 , we have ε ≤ 1. By applying Lemma 4.1 to the transformed body (with ε playing the role of ε), it follows that the polytope K ∩ Q can be ε-approximated by a polytope P defined by the intersection of at most

c 2 (ε ) (d-1)/2 = c 2 c 1 √ ε (d-1)/2 ≤ 1 ε (d-1)/4 halfspaces. Since K ∩ Q ⊆ P , it is easy to see that P is an ε-approximation of K within Q. Since t ≥ 1/ε (d-1)/4
, the termination condition of our algorithm implies that such a cell is not further subdivided, contradicting our hypothesis that this is an internal node. Therefore, the cells of L satisfy the conditions of Lemma 4.4. The desired bound follows by applying this lemma.

It is useful to contrast this with the Dudley-based approach described in Section 2.4. For t = 1/ε (d-1)/4 , we obtain the same O(1/ε (d-1)/2 ) space in each case, but the exponent in the query time of SplitReduce is only half that of the Dudley-based approach. Later, in Lemma 6.3, we will present a more refined analysis showing that it is possible to reduce this further, achieving a query time of only O 1/ε (d-1)/8 .

It will be useful in later sections to generalize the above lemma to quadtree cells of arbitrary size. By a direct application of standardization, we obtain the following. Lemma 4.6. Let K be a convex body in R d , Q be a quadtree cell contained within Q 0 , and let 0

< ε ≤ diam(Q)/2. The output of the call SplitReduce(K, Q) for t ≥ (diam(Q)/ε) (d-1)/4 has total space O (diam(Q)/ε) (d-1)/2 .

Dual Caps and Approximation

The bounds proved in the previous section apply to query times t ≥ 1/ε (d-1)/4 . In Section 6 we will show how to obtain good space bounds for smaller query times. This will involve analyzing the local geometry about small boundary patches of the convex body. In this section, we introduce the principal geometric underpinnings that will be needed for this more refined analysis. In particular, we discuss the concepts of dual caps and restricted dual caps and their role in polytope approximation.

Although we do not assume that K is smooth, it will simplify the presentation to imagine that each boundary point has a unique supporting hyperplane and a unique normal vector. To achieve this, we employ an augmented representation of the boundary points of K. In particular, each boundary point p ∈ ∂K will be expressed as a pair (p, h), where h is a supporting hyperplane at p. We will often refer to h as h(p). When h is clear from context or unimportant, we avoid explicit reference to it.

We first observe that computing an outer ε-approximation of a convex body K by halfspaces can be reduced to a hitting-set problem. Consider any point p ε that is external to K at distance ε from its boundary, and let (p, h) denote the augmented boundary point consisting of the closest point p ∈ ∂K to p ε and the supporting hyperplane through p that is orthogonal to the segment pp ε (see Figure 9(a)). We define the ε-dual cap of p, denoted D(p), to be the set of augmented boundary points (q, h ) such that the supporting hyperplane h through q intersects the closed line segment pp ε . (Equivalently, these are the points of ∂K that are visible to p ε .) Any outer ε-approximation of K by halfspaces must contain at least one halfspace that separates p from p ε , and this can be achieved by including h for any pair (q, h ) within D(p). A set of augmented points Σ ⊆ ∂K is said to be an ε-hitting set for K if for every p ∈ ∂K, Σ ∩ D(p) = ∅. It follows directly that the intersection of the supporting halfspaces for any ε-hitting set is an outer ε-approximation of K. This observation will be formalized within our quadtree-based context in our next lemma. Before stating the lemma, we need to introduce one additional concept. In order to approximate K within a given quadtree cell Q, we are interested only in the geometry of K's boundary that lies close to Q. For this reason, it will be desirable to limit the diameter of dual caps. Given δ > 0, let B δ (p) denote the closed Euclidean ball of radius δ centered at p. Define the δ-restricted dual cap, denoted D δ (p), to be the intersection of D(p) with B δ (p) (see Figure 9(b)).

p ε K D δ (p) (b) (a) δ p ε K D(p) p ε p p ε S K D(p) Vor(D(p)) ∩ S (c) p ε K D δ (p) p δ
Lemma 5.1. Let K be a convex body, Q ⊆ Q 0 be a quadtree cell that intersects ∂K, and 0 < ε ≤ 1/2. Let Σ be any set of augmented points on E(K, Q) that hits the set of all √ ε-restricted ε-dual caps whose defining point is in E(K, Q) (see Figure 10(a)). Then there is a polytope P defined as the intersection of |Σ| halfspaces that ε-approximates K within Q.

Proof : Let P be the polytope defined by the intersection of the supporting halfspaces associated with each augmented point of Σ (see Figure 10(b)). Clearly, K ⊆ P . Consider any point q ∈ Q that is at distance greater than ε from K ∩ Q. It suffices to show that q / ∈ P , that is, there exists a bounding hyperplane for P that separates q from K.

√ ε Q K Q K (a) (c) q q 0 = z 0 x 0 q ε E(K, Q) Q P (b) Σ h 0 Figure 10: Lemma 5.1.
We apply a similar argument to the one that we used in the proof of Lemma 4.3. Consider any q ∈ Q that is at distance greater than ε from K (see Figure 10(c)). It suffices to show that there exists a bounding hyperplane for P that separates q from K. Let q 0 denote the point of K ∩ Q that is closest to q. By continuity, there must be a point on the segment qq 0 that is at distance exactly ε from ∂K, which we denote by q ε . Since Q is convex, this segment must be contained in Q, and, hence, so is q ε . Let z 0 be the point on ∂K that is closest to q ε . (In our figure

z 0 = q 0 , but generally z 0 need not lie within Q.) Since ε ≤ 1, we have q ε z 0 = ε ≤ √ ε. It follows that z 0 ∈ E(K, Q).
Therefore, there exists an augmented point (x 0 , h 0 ) ∈ Σ that hits the √ ε-restricted ε-dual cap defined by z 0 (whose apex is at q ε ). The supporting hyperplane h 0 separates q ε (and therefore q) from K, as desired.

Our analysis of the space bounds of SplitReduce is based on the combined sizes of the ε-hitting sets for K within each quadtree cell Q. Dudley's construction can be viewed as one method of computing ε-hitting sets. Unfortunately, Dudley's construction does not lead to the best bounds because it tends to over-sample in regions of very low or very high curvature. Our analysis will be based on a more refined, area-based approach to bounding the sizes of hitting sets. The key geometric observation is that the product of the areas of any ε-dual cap and its associated Voronoi patch on the Dudley sphere S must be large. Intuitively, if the surface area of an ε-dual cap is small, then the total curvature of the patch must be high, and so the associated Voronoi patch must have relatively large area (see Figure 9(c)). More precisely, we show that (under certain conditions) the product of the areas of an ε-dual cap and its Voronoi patch is Ω(ε d-1 ). This result is stated formally in Lemma 5.2 below. Given a (d-1)-dimensional manifold, let area(Y ) denote its (d -1)-dimensional Hausdorff measure. Given a convex body X in R d , we use area(X) as a shorthand for area(∂X).

Lemma 5.2 (Area-Product Bound). Let K be a convex body in R d , let 0 < ε ≤ 1/8.
(D) • area(Vor(D) ∩ S) > c a • ε d-1 .
The proof of the lemma is quite technical and will be deferred to Section 10. The geometric basis of the proof involves the Mahler volume, which was introduced in Section 2.3. The bound stated in the lemma holds if K is γ-fat for any γ in the interval (0, 1] under the assumption that γ does not depend on ε. In particular, the proof will reveal that c a = Ω(γ d-1 ).

We will exploit this observation to demonstrate the existence of smaller ε-hitting sets than those given by Dudley's construction. We will hit the restricted ε-dual caps that have large surface area by sampling points randomly on the boundary of K, and we will hit those with small surface area by sampling points randomly on the Dudley hypersphere and then selecting their nearest neighbors on ∂K. In order to prove that such a random sampling strategy works to stab all the dual caps, we need to establish bounds on the VC-dimension of an appropriate range space based on dual caps. This is not surprising given that dual caps and restricted dual caps are defined by a constant number of parameters. The result is stated in the following lemma. The proof involves a straightforward application of basic geometric principles and appears in the appendix. Lemma 5.3. Let K be a convex body in R d that lies within Q 0 , and let ε and δ be positive real parameters. The following range spaces (X i , R i ) have constant VC-dimension (where the constant depends only on d):

(1) X 1 = ∂K and R 1 is the set of ε-dual caps.

(2) X 2 = S and R 2 is the set of Voronoi patches of the ε-dual caps.

(3) X 3 = ∂K and R 3 is the set of δ-restricted ε-dual caps. (4) X 4 = S and R 4 is the set of Voronoi patches of the δ-restricted ε-dual caps.

In the next section we will exploit this result to establish the existence of small ε-nets for these range spaces. Note that the range spaces defined in this lemma are defined over ∂K, a domain of infinite cardinality. However, for our purposes, it suffices to consider dual caps and restricted dual caps whose defining points are drawn from any sufficiently dense set of points on ∂K (depending on ε), and therefore the domains of the range spaces can be treated as finite sets.

Final Upper Bound

In this section, we use the tools developed in Sections 4 and 5 to obtain better upper bounds for approximate polytope membership. In particular, we present a proof of Theorem 2. We will first show how to apply the area-based techniques described in the previous section to improve the simple upper bound from Lemma 4.5 at the low-space end of the trade-off spectrum. (This will be presented in Lemma 6.3.) We will then apply this improvement repeatedly in an inductive manner to establish tradeoffs throughout the spectrum. For technical reasons, many of the lemmas of this section assume constant upper bounds on the value of ε. There is no loss of generality in doing so, since it is easy to show that if ε is bounded below by any fixed constant, the asymptotic space and query times of SplitReduce are both O(1).

Throughout this section, recall that

E δ (K, Q) is the portion of ∂K that is within distance δ of Q, and E(K, Q) = E √ ε (K, Q). Also, define E + (K, Q) = E 2 √ ε (K, Q).
We will assume that diam(K) ≥ 2ε, for otherwise it is trivial to compute an ε-approximation of constant size. Our first result establishes an area-based bound on the number of halfspaces needed to approximate K within a quadtree cell Q. Lemma 6.1. Let K be a fat convex body in R d , let 0 < ε ≤ 1/8, and let Q ⊆ Q 0 be a quadtree cell that intersects ∂K. Letting c a denote the constant of Lemma 5.2, define

r = area(E + (K, Q)) • area (Vor(E + (K, Q)) ∩ S) c a • ε d-1 1/2 .
There is a polytope P defined as the intersection of O(r log r) halfspaces that is an ε-approximation of K within Q.

Proof : Letting A K = area(E + (K, Q)) and A S = area (Vor(E + (K, Q)) ∩ S), we can express the value of r more succinctly as A K A S /c a ε d-1 1/2 . First, we assert that r = Ω(1). To see this, we consider two cases. First, if K lies entirely within distance 2 √ ε of Q, then Vor(E + (K, Q)) ∩ S = S, which implies that A S = Ω(1). Since K is fat and by our assumption that diam(K) ≥ 2ε, it follows that A K = Ω(ε d-1 ). Therefore, r = Ω(1). On the other hand, if some part of K lies at distance greater than 2

√ ε from Q, E + (K, Q) is a boundary patch of K of diameter Ω( √ ε). Since both K and Q are fat, it follows that A K = Ω ε (d-1)/2
. By convexity, as we go from a boundary patch on K to its Voronoi cell on S, distances cannot decrease. Therefore A S ≥ A K , and again we have r = Ω(1). Through a minor adjustment to constant factor c a in r's definition, we may assume that log r ≥ 1.

By Lemma 5.1, in order to show the existence of an ε-approximating polytope P for K within Q, it suffices to show that it is possible to hit all √ ε-restricted ε-dual caps whose defining point lies in E(K, Q) (not to be confused with E + (K, Q)) using O(r log r) points. To do this, we distinguish between two types of such restricted dual caps. A restricted dual cap

D is of type 1, if area(D) ≥ c a ε d-1 A K /A S 1/2
, and otherwise it is of type 2.

By assertions ( 3) and ( 4) of Lemma 5.3, we know that √ ε-restricted ε-dual caps and their Voronoi patches both have constant VC-dimension. The VC-dimension is no larger if we restrict the domain of the range space. Therefore, by standard machinery (see, e.g., [START_REF] Alon | The Probabilistic Method[END_REF]) we can build a (1/r)-net for any restriction of these range spaces of size O(r log r) each by random sampling.

For type-1 dual caps, consider the restriction (E + (K, Q), R 3 ) of the range space given in Lemma 5.3(3). Let Σ 1 denote a (1/r)-net. Consider any type-1 dual cap D. Since D's defining point lies within E(K, Q) and it is √ ε-restricted, it lies entirely within E + (K, Q). Thus, we have

area(D ∩ E + (K, Q)) area(E + (K, Q)) = area(D) area(E + (K, Q)) ≥ c a • ε d-1 A K /A S 1/2 A K = c a • ε d-1 A K A S 1/2 = 1 r .
Therefore D contains at least one point of Σ 1 . It follows that Σ 1 hits all type-1 dual caps. For type-2 dual caps, let us consider the restriction (Vor(E + (K, Q)) ∩ S, R 4 ) of the range space of Lemma 5.3(4). Let Σ 2 denote a (1/r)-net. Because ε ≤ 1/8 and Q ⊆ Q 0 , E(K, Q) lies within a ball centered at the origin of radius diam(Q 0 )/2 + √ ε ≤ 1. Given any type-2 dual cap D whose defining (augmented) point lies in E(K, Q), we may apply Lemma 5.2 to obtain

area(Vor(D) ∩ S) ≥ c a • ε d-1 area(D) ≥ c a • ε d-1 c a • ε d-1 A K /A S 1/2 = c a • ε d-1 A S A K 1/2 .
As before, since D's defining point lies within

E(K, Q), D ⊆ E + (K, Q). From this we have area(Vor(D ∩ E + (K, Q)) ∩ S) area(Vor(E + (K, Q)) ∩ S) = area(Vor(D) ∩ S) area(Vor(E + (K, Q)) ∩ S) ≥ c a • ε d-1 A S /A K 1/2 A S = c a • ε d-1 A K A S 1/2 = 1 r .
Therefore Vor(D) ∩ S contains at least one point of Σ 2 , implying that Σ 2 hits the Voronoi patches of all type-2 dual caps. For each point of Σ 2 , we select its nearest neighbor on ∂K, obtaining a set

Σ 2 ⊂ E + (K, Q).
It follows directly that the set Σ 2 hits all type-2 dual caps. Therefore, the union Σ 1 ∪ Σ 2 forms the desired set of size O(r log r) that hits all √ ε-restricted ε-dual caps whose defining point lies within E(K, Q).

In order to establish our storage bounds, we analyze the behavior of the algorithm at a particular level of the decomposition. Given the query-time parameter t, recall that we stop the subdivision process in SplitReduce(K, Q) if the number of hyperplanes needed to approximate K within Q falls below t. Also recall that t(Q) denotes the number of approximating halfspaces associated with Q. Let us consider the state of the subdivision process when the cell sizes reach roughly √ ε. Cells that have stopped subdividing by this point are "good," since we can bound the total space requirements for all such cells by appealing to Lemma 4.4. For the remaining "bad" cells, we will bound their space requirements on a cell-by-cell basis by using the simple upper bound from Lemma 4.6. For our approach to work well, it is crucial to obtain a good bound on the number of such bad cells. We exploit the area bound of Lemma 6.1 for this purpose. Whenever SplitReduce subdivides a cell of size O( √ ε), we can infer that more than t hyperplanes are required to approximate K within this cell. Since the portion of ∂K lying within this cell is small, the area of its Voronoi patch on the Dudley sphere must be large. A packing argument applied on the Dudley sphere will be used to limit the number of these bad cells.

In order to formalize the notion of good and bad cells, let T denote the quadtree produced by SplitReduce(K, Q 0 ), and let T denote the subtree of T induced by cells of diameter at least √ ε/2. For the remainder of this section, let L 1 denote the (good) leaf cells of T that are not subdivided further by the algorithm, and let L 2 be the remaining (bad) leaf cells of T . The cells of L 1 and L 2 are all of diameter Ω( √ ε). Each cell in L 1 can be approximated using at most t halfspaces, and those in L 2 require more. In our next lemma, we bound the total number of approximating halfspaces over all the good leaf cells and the total number of bad leaf cells. Lemma 6.2. Let K be a fat convex body in R d , let 0 < ε ≤ 1/8. Let T denote the quadtree produced by SplitReduce(K, Q 0 ), for t ≥ 1, and let L 1 and L 2 be as defined above. Then

(i) Q∈L 1 t(Q) = O 1/ε (d-1)/2 , (ii) |L 2 | = O (1 + log t)/t) 2 (1/ε) (d-1)/2 .
Proof : Because the cells of L 1 are disjoint and each is of diameter Ω( √ ε), assertion (i) follows as a direct consequence of Lemma 4.4. Thus, it remains to prove assertion (ii). Let Q be any cell of L 2 . Since any child of a cell of L 2 is of diameter smaller than √ ε/2 and Q's diameter is twice this, we have

√ ε/2 ≤ diam(Q) < √ ε. Recall that E + (K, Q) = E 2 √ ε (K, Q). Also, let A K (Q) and A S (Q)
denote the values of A K and A S , respectively, from the proof of Lemma 6.1, when applied to Q.

Because diam(Q) ≤ √ ε and E + (K, Q) involves a boundary patch of K that intersects Q and includes an additional expansion by distance 2 √ ε, it follows that this boundary patch has diameter O( √ ε). Therefore, A K (Q) = O ε (d-1)/2 . By applying Lemma 6.1 (and recalling the constant c a from Lemma 5.2), we have t(Q) = O(r log r), where

r = area(E + (K, Q)) • area (Vor(E + (K, Q)) ∩ S) c a • ε d-1 1/2 = A K (Q)A S (Q) c a • ε d-1 1/2 = O A S (Q) ε (d-1)/2 .
In Lemma 6.1 we showed that (after a suitable adjustment to c a ), we have log r ≥ 1. Since Q is subdivided further, we know that t(Q) > t, which implies that t = O(r log r). Because t ≥ 1, by simple manipulations we have t/(1 + log t) = O(r). By combining this with the upper bound on r from above, we obtain A S (Q) = Ω (t/(1 + log t)) 2 ε (d-1)/2 , which yields the lower bound

Q∈L 2 A S (Q) = |L 2 | • Ω t 1 + log t 2 ε d-1 2 .
As shown in the proof of Lemma 4.4, given any set of disjoint quadtree cells of diameter Ω( √ ε) a point of S can be in Vor(E + (K, Q)) for at most a constant number of these cells. Since the quadtree cells of L 2 satisfy these conditions,

Q∈L 2 A S (Q) = Q∈L 2 area(Vor(E + (K, Q)) ∩ S) = O(area(S)).
Combining this with our lower bound, we have

|L 2 | = O area(S) • 1 + log t t 2 • 1 ε d-1 2 .
Since S is a hypersphere of constant radius, its area is bounded, and assertion (ii) follows immediately.

Recall that we showed in Lemma 4.5 that it is possible to answer approximate membership queries in 1/ε (d-1)/4 time using space O 1/ε (d-1)/2 . By using the above lemma, we show next that we can improve this to achieving query time roughly O 1/ε (d-1)/8 for the same space. Lemma 6.3. Let K be a fat convex body in R d , and let 0 < ε ≤ 1/16. For t ≥ (lg 1 ε )/ε (d-1)/8 , the output of SplitReduce(K, Q 0 ) has total space O 1/ε (d-1)/2 .

Proof : Let T denote the quadtree produced by the algorithm. By Lemma 3.1, the data structure's total space is dominated by the space needed to store the hyperplanes in the leaf cells. Thus, it suffices to show that the sum of t(Q) over all leaf cells Q of T is O 1/ε (d-1)/2 . Let T , L 1 , and L 2 be as defined just prior to Lemma 6.2. By Lemma 6.2(i), the total contribution of t(Q) for all cells in L 1 is O 1/ε (d-1)/2 . So, it suffices to bound the contribution due to L 2 .

Let Q be any cell of L 2 . Recall from the proof of Lemma 6.2 that

√ ε/2 ≤ diam(Q) ≤ √ ε. Since t ≥ 1/ε (d-1)/8 , it follows that t ≥ (diam(Q)/ε) (d-1)/4 . Because ε ≤ 1/16, we have ε ≤ √ ε/4 ≤ diam(Q)/2. By Lemma 4.6, the output of SplitReduce(K, Q) has total space at most O diam(Q) ε d-1 2 = O 1 ε d-1 4
.

By Lemma 6.2(ii), |L 2 | = O ((1 + log t)/t) 2 (1/ε) (d-1)/2 . Since t ≥ (lg 1 ε )/ε (d-1)/8 , we have |L 2 | = O 1/ε (d-1)/4
. Summing up the space contributions of all Q ∈ L 2 , the total space for these cells is

|L 2 | • O 1/ε (d-1)/4 = O 1/ ε (d-1)/4 • ε (d-1)/4 = O 1/ε (d-1)/2 ,
as desired.

In order to extend the space-time trade-off to other query times, we will apply the previous result as the basis case in an induction argument. The induction will be controlled by a parameter α, which we assume to be a constant. The proof is rather technical, but it involves a straightforward application of the earlier results of this section. Lemma 6.4. Let K be a fat convex body in R d , and let 0 < ε ≤ 1/16. Let α ≥ 4 be a real-valued constant. For t ≥ (lg 1 ε )/ε (d-1)/α , the output of SplitReduce(K, Q 0 ) has total space

O 1/ε (d-1) 1-2 lg α -2 α + 1 2 lg α
.

Proof : Define k = lg α , which implies that k ≥ 2, and 2 k ≤ α < 2 k+1 . Expressed as a function of k, the desired space bound can be expressed as

c k • 1/ε (d-1) 1-2 k-2 α + 1 2 k , (1)
for a constant c k (depending on k but not on ε).

We begin exactly as in the proof of the previous lemma. Let T denote the quadtree produced by the algorithm, and by Lemma 3.1, it suffices to bound the sum of t(Q) over all leaf cells of T . Given T , L 1 , and L 2 defined prior to Lemma 6.2, the space contribution due to the cells of L 1 is O 1/ε (d-1)/2 . To see that this satisfies our space bound, observe that since k ≥ 2 and α ≥ 2 k , we have

1 4 ≥ k -1 2 k = k -2 2 k + 1 2 k ≥ k -2 α + 1 2 k .
Therefore, the total contribution of t(Q) for all cells in L 1 is

O 1/ε (d-1)/2 = O 1/ε (d-1)(1-2( 1 4 )) ≤ O 1/ε (d-1) 1-2 k-2 α + 1 2 k , (2)
which matches the desired bound given in Eq. [START_REF] Agarwal | Approximating extent measures of points[END_REF]. It remains to bound the contribution to the space of the cells of L 2 . We do this by induction on k. For the basis case k = 2, we have 4 ≤ α < 8. Therefore t > (lg 1 ε )/ε (d-1)/8 . By applying Lemma 6.3, the total space of the data structure (which includes the contribution of L 2 ) is O 1/ε (d-1)/2 . It follows from Eq. (2) (for the case k = 2) that this satisfies our storage bound.

For the induction step, we assume that the lemma holds for k -1 (that is, 2 k-1 ≤ α/2 < 2 k ), and our objective is to prove it for k. It will be convenient to express the induction hypothesis in a form that holds for an arbitrary quadtree cell Q ⊆ Q 0 . By applying standardization to Q (thus mapping Q to Q 0 and scaling ε to ε/diam(Q)), the induction hypothesis states that for

0 < ε ≤ diam(Q) 16 and t ≥ lg diam(Q) ε • diam(Q) ε d-1 α/2 , (3)
there is a constant c k-1 such that the output of SplitReduce(K, Q) has total space at most

c k-1 • (diam(Q)/ε) (d-1) 1-2 k-3 α/2 + 1 2 k-1 . (4)
Let Q be any cell of L 2 . In the proof of Lemma 6.2 we showed that

√ ε/2 ≤ diam(Q) < √ ε.
By the bound on t from the statement of this lemma, we have

t ≥ lg 1 ε 1 ε d-1 α ≥ lg 1 √ ε 1 √ ε 2(d-1) α ≥ lg diam(Q) ε diam(Q) ε d-1 α/2
, implying that t satisfies Eq. ( 3). If ε is at most diam(Q)/16, we may apply the induction hypothesis, yielding the space bound given in Eq. ( 4). Since diam(Q) < √ ε, this can be simplified to

c k-1 • (1/ √ ε) (d-1) 1-2 k-3 α/2 + 1 2 k-1 = c k-1 • 1/ε (d-1) 1 2 - 2(k-3) α -1 2 k-1 . (5)
By combining Lemma 6.2(ii) with the lower bound on t given in the statement of this lemma, the number of cells in L 2 satisfies

|L 2 | = O lg t t 2 1 ε d-1 2 = O ε 2(d-1) α 1 ε d-1 2 = O 1 ε (d-1)( 1 2 -2 α ) . ( 6
)
The total contribution to the space by the cells of L 2 is the product of the space requirements for each cell of L 2 , given in Eq. ( 5), and the number of such cells, given in Eq. ( 6). There exists a constant c k (depending on k but not on ε) such the total space is at most

c k • 1/ε (d-1) 1 2 - 2(k-3) α -1 2 k-1 +( 1 2 -2 α ) = c k • 1/ε (d-1) 1-2 k-2 α + 1 2 k
.

On the other hand, if ε exceeds diam(Q)/16, then since diam(Q) ≥ √ ε/2 it follows that ε is Ω(1), and we can adjust to c k to satisfy this bound. In either case, we achieve the bound in Eq. [START_REF] Agarwal | Approximating extent measures of points[END_REF].

Observe that the exponent in the space bound in the preceding lemma is a piecewise linear function in 1/α, whose breakpoints coincide with powers of two. It is easily verified that the exponent is a continuous function of α. (In particular, observe that lim δ→0 f (2 k-δ ) = f (2 k ), where f (α) = 1/2 lg α + ( lg α -2)/α.)

We can now present the proof of Theorem 2. Recall that K is a convex polytope in R d . By Lemma 2.1, we can precondition K so that it is (1/d)-fat and is contained within Q 0 , thus allowing us to approximate K absolutely. Also, if 1/16 < ε ≤ 1, we set ε = 1/16. (Both of these changes result in a constant factor decrease to ε, which will not affect the asymptotic bounds.) We then set t = (lg 1 ε )/ε (d-1)/α and invoke SplitReduce(K, Q 0 ). Let T denote the resulting data structure. Given the preconditioning of K and the alteration of ε, we may apply Lemma 6.4 to show that the total space for T is

O 1/ε (d-1) 1-2 lg α -2 α + 1 2 lg α .
Using the fact that 1/2 lg α ≥ 1/α, this is

O 1/ε (d-1) 1-2 lg α -2 α + 1 α = O 1/ε (d-1) 1- 2 lg α -2 α
, which matches the space bound of Theorem 2.

Recall that a query is answered by locating the leaf node of T that contains the query point, followed by an inspection of the (at most) t halfspaces stored in this leaf node. By our remarks following the presentation of SplitReduce, T is of height O(log 1 ε ), which implies that the query time is dominated by the value of t. This completes the proof of Theorem 2.

Preprocessing

Our principal focus so far has been in establishing the existence of trade-offs between space and query time, without considering how to construct the data structure. In this section we discuss preprocessing issues. We first discuss the preconditioning of K as described in Lemma 2.1 and then discuss the implementation of the access primitives (i)-(iii) needed for SplitReduce as presented at the start of Section 3. We assume that the input convex body K is presented as the intersection of a set H of n halfspaces in R d . Throughout, let Q denote an arbitrary quadtree cell.

Let t denote the query-time parameter in SplitReduce. As observed in Section 3, under our assumption that t ≥ 1, Steps 1 and 2 are not needed, since we can rely entirely on Step 3, and therefore access primitives (i) and (ii) are not needed. 2 The remainder of this section will be focused on preconditioning (Section 7.1) and the implementation of access primitive (iii), which locally approximates K within Q (Section 7.2).

Preconditioning

Recall that we assume that K is a (full-dimensional) convex polytope in R d that is presented as the intersection of a set of n closed halfspaces. Also recall that Q 0 is the axis-aligned hypercube of unit diameter that is centered at the origin. Our objective is to precondition K by computing an affine transformation that both fattens K and maps it to lie within Q 0 . Q 0 has a side length of 1/ √ d, and therefore it contains a ball of radius 1/2 √ d centered at the origin. Let B 0 denote this ball, and let r 0 denote its radius. For 0 < γ ≤ 1, let γB 0 denote the concentric ball of radius γ r 0 = γ/2 √ d. We say that a polytope is in γ-canonical position if it is nested between γB 0 and B 0 (see Figure 11). Clearly, a polytope that is in canonical position is contained within Q 0 and is γ-fat. The following lemma shows that K can be efficiently mapped into this form, and furthermore an absolute approximation to the transformed body can be easily mapped to a relative approximation of K. (Lemma 2.1 of Section 2.1 follows as an immediate consequence of this.) Such fattening operations are commonplace in geometric approximation algorithms (see, e.g., [START_REF] Agarwal | Approximating extent measures of points[END_REF][START_REF] Barequet | Efficiently approximating the minimum-volume bounding box of a point set in three dimensions[END_REF][START_REF] Chan | Faster core-set constructions and data-stream algorithms in fixed dimensions[END_REF][START_REF] Har-Peled | Geometric Approximation Algorithms[END_REF]), and we employ the standard approach based on minimum enclosing volumes, the John Ellipsoid in particular. Proof : Chazelle and Matoušek [START_REF] Chazelle | On linear-time deterministic algorithms for optimization problems in fixed dimension[END_REF] show that in any fixed dimension, there exists an O(n) time algorithm that, given a convex polytope K presented as the intersection of n halfspaces, computes an ellipsoid E of maximum volume contained within K, also known as the John Ellipsoid [START_REF] Ball | An elementary introduction to modern convex geometry[END_REF]. (At the expense of an increase in the constant factors, we can apply the simpler construction by Har-Peled and Barequet [START_REF] Barequet | Efficiently approximating the minimum-volume bounding box of a point set in three dimensions[END_REF].) Since d is fixed, in constant time we can compute an affine transformation T that maps E to the ball B 0 /d (that is, 1 d B 0 ). (Because K is full dimensional, both T and its inverse T -1 are well-defined.) It is well known from John's Theorem (see, e.g., [START_REF] Ball | An elementary introduction to modern convex geometry[END_REF]) that K is contained within a uniform scaling of E by a factor of d, which we denote by dE. Therefore, we have E ⊆ K ⊆ dE, which implies that

γr 0 = γ/2 √ d r 0 = 1/2 √ d Q 0 B 0 γB 0
B 0 /d ⊆ T (K) ⊆ B 0 . Let σ = d √ d • diam(E).
Because T maps an ellipse of diameter diam(E) to a ball of diameter 2r 0 /d = 1/d √ d, it follows that T maps any vector v to a vector of length at least v /σ. (The principal axis aligned with E's diameter is scaled by exactly 1/σ, and all other principal axes, which form a basis for the space, are scaled by at least this much.) Therefore, T -1 (v) ≤ σ v .

If P is any absolute ε/(d √ d)-approximation to T (K), then by definition

T (K) ⊆ P ⊆ T (K) ⊕ ε d √ d . (7)
To show that T -1 (P ) is a relative ε-approximation to K, observe first that by applying T -1 to the first inclusion of Eq. ( 7), we have K ⊆ T -1 (P ). Also, by the second inclusion of Eq. ( 7) we know that for any p ∈ P , there exists q ∈ T (K) such that the vector pq is of length at most ε/(d √ d). Therefore,

T -1 (p -q) ≤ σ p -q ≤ σ ε d √ d = ε • diam(E) ≤ ε • diam(K).
We conclude that

K ⊆ T -1 (P ) ⊆ K ⊕ (ε • diam(K)),
and therefore T -1 (P ) is a relative ε-approximation of K.

In order to make subsequent processing more efficient, we adapt a standard coreset construction to reduce the number of halfspaces to a function depending only on ε and d. The process will involve some further scaling, which will slightly modify the parameters. Lemma 7.2. Let K be a convex polytope in R d defined as the intersection of a set H of n halfspaces, and let 0 < ε ≤ 1. There is an algorithm that, given H and ε, in O n + 1/ε d-1 time computes an affine transformation T and a subset H ⊆ H of size O 1/ε (d-1)/2 such that:

(i) applying T to the intersection of H results in a convex polytope K that is in (1/2d)-canonical position; (ii) furthermore, if P is an absolute ε/(4d √ d)-approximation of K , then T -1 (P ) is a relative ε- approximation of K.
Proof : Given H, we begin by computing the transformation T of Lemma 7.1 in O(n) time. Let T (K) denote the resulting polytope, which is in (1/d)-canonical position (see Figure 13(a)).

Given a set S of points R d , the extent measure associates each unit vector u ∈ R d with the minimum distance between two hyperplanes orthogonal to u that contain S between them (see Figure 12(a)). More formally, define w u (S) = max p,q∈S pq, u (recalling that •, • denotes inner product). A subset S ⊆ S is said to be an ε-coreset for the extent measure if for all unit vectors u, w u (S ) ≥ (1ε)w u (S) (see Figure 12(b)). Agarwal et al. [START_REF] Agarwal | Approximating extent measures of points[END_REF] showed that, given a set of n points in R d , it is possible to construct an ε-coreset for the extent measure of size O 1/ε (d-1)/2 . We will employ an improvement of this result due to Chan, who presented an algorithm to compute such a coreset in O n + (1/ε) d-1 time [START_REF] Chan | Faster core-set constructions and data-stream algorithms in fixed dimensions[END_REF].

Since T (K) is in (1/d)-canonical position, we have B 0 /d ⊆ T (K) ⊆ B 0 . Let S denote the set of n points in R d that result by applying the polar transformation (see Section 2.3) to each hyperplane of T (H). It follows from the definition of the polar transformation that conv(S) = polar(T (K)) (see Figure 13(b)). As mentioned in Section 2.3, the polar transformation maps an origin-centered ball of radius r to a ball of radius 1/r. Thus, conv(S) is nested between an inner ball of radius 2 √ d and an outer ball of radius 2d √ d. Given H and T , we can easily compute the set S in O(n) time. Let ε = ε/4d 2 . We then apply Chan's algorithm to compute an ε

-coreset S ⊆ S in time O n+(1/ε ) d-1 = O n+(1/ε) d-1
(see Figure 13(c)). Let H be the subset of H that results by taking the polar duals of the points of S , and let K be the convex body that results from intersecting these halfspaces (see Figure 13(d)). . We assert that the Hausdorff distance between T (K) and K is at most ε/2d √ d. To prove this, we apply an observation due to Chan [START_REF] Chan | Faster core-set constructions and data-stream algorithms in fixed dimensions[END_REF]. Define the one-sided extent measure, denoted w u (S) to be max p∈S p, u . (This is the distance from the origin to S's closest supporting hyperplane orthogonal to and on the same side as u.) In Observation 1.4 of [START_REF] Chan | Faster core-set constructions and data-stream algorithms in fixed dimensions[END_REF] Chan shows that if S is an ε -coreset for the extent measure, then w u (S ) ≥ w u (S)ε • w u (S). Given the nesting properties of S and the fact that u is a unit vector we have

(b) (a) (c) (d) 1 2d √ d 1 2 √ d 2 √ d 2d √ d polar T (K) conv (
2 √ d ≤ w u (S) ≤ 2d √ d and 4 √ d ≤ w u (S) ≤ 4d √ d.
Therefore, w u (S) ≤ 2d • w u (S), and with Chan's observation this yields w u (S ) ≥ (1 -2dε )w u (S). Under our assumption that ε ≤ 1, we have ε ≤ 1/4d 2 , and so 1

-2dε ≥ 1 -1/2d ≥ 1/2.
Let p ∈ S be the point that determines w u (S) (see Figure 13(c)). Treating p as a vector, its polar dual is a hyperplane, which we denote by h p (see Figure 13(d)). It follows directly from the definition of polarity that if we shoot a bullet from the origin parallel to u until it hits h p , the length of the resulting segment is 1/w u (S). (To see this, observe that h p = {v : p, v = 1}, and so c • u lies on h p , for c = 1/ p, u = 1/w u (S).) Analogously, letting p ∈ S denote the point that determines w u (S ), the length of the segment parallel to u that hits the associated polar dual hyperplane h p is of length 1/w u (S ). Applying this to every unit vector in R d , the Hausdorff distance between T (K) and K is at most the supremum over all unit vectors of

1 w u (S ) - 1 w u (S) ≤ 1 (1 -2dε ) • w u (S) - 1 w u (S) = 2dε (1 -2dε ) • w u (S) ≤ 2dε (1/2) • 2 √ d ≤ 2 √ dε ≤ ε 2d √ d ,
which establishes our assertion. Therefore, if P is any absolute (ε/2d √ d)-approximation to K , then by the triangle inequality (applied to the Hausdorff distance) P is an absolute (ε/2d

√ d) + (ε/2d √ d) = ε/d √ d approximation to T (K)
. By Lemma 7.1, P is a relative ε-approximation of K.

We are almost done, but the canonical-position condition fails, because K need not lie within B 0 of radius r 0 = 1/2 √ d (even though T (K) does). Since the Hausdorff distance between K and T (K) is at most ε/2d √ d ≤ 1/2 √ d = r 0 , it follows that K lies within 2B 0 . The simple fix is to apply a uniform scaling of space by a factor of 1/2. In particular, define T to be the composition of T with such a scaling transformation, and apply the above coreset construction to H transformed by T , but now with ε scaled accordingly to ε/8d 2 . The resulting transformed and reduced polytope is nested between B 0 and B 0 /2d, and so it is in (1/2d)-canonical position. Also, if P is an absolute (ε/4d √ d)-approximation of the transformed and reduced polytope, then T -1 (P ) is a relative ε-approximation of K, as desired.

Efficient Local Approximations

Next, we consider the implementation of access primitive (iii), which given a convex body K in γcanonical position, a quadtree cell Q, and query-time t, determines whether there exist t halfspaces whose intersection ε-approximates K within Q. The space and query times stated in Theorem 2 are based on the assumption that the number of bounding halfspaces of this local approximating polytope is within a constant factor of optimal. However, we know of no efficient algorithm that can achieve this. In this section we show how to efficiently implement Step (3) of SplitReduce approximately in the sense that the number of halfspaces in the approximation exceeds the optimum (for a slightly smaller approximation parameter) by a factor of O(log 1 ε ). As shown in Lemma 3.2, this will lead to an increase in the space and query times stated in Theorem 2 by a factor of only O(log 1 ε ). A natural approach would be to adapt Clarkson's algorithm for polytope approximation [START_REF] Clarkson | Algorithms for polytope covering and approximation[END_REF]. There are a few messy technical issues involved with such an adaptation. (For example, Clarkson's algorithm applies to the convex hull of a set of points, rather than the intersection of halfspaces.) Since we do not require the strong approximation bounds provided by Clarkson's algorithm, we will instead present a simple direct solution based on a reduction to the set-cover problem. Our approach is to construct a set system where the point set consists of a dense set of points of spacing Θ(ε) that covers the portion of Q that is external to K ⊕ c ε, for a suitable constant c < 1. We associate each bounding halfspace of K with the set of grid points that lie outside of this halfspace. We will show that the halfspaces associated with a minimum set cover for this system produces the desired local approximation. We use the greedy set cover heuristic to construct this cover.

Recall that K ⊕ r denotes the set of points that lie within Euclidean distance r of K. In order to avoid the complexities of determining whether a point lies outside of K ⊕ c ε, it will suffice for our purposes to perform the simpler test of whether a point lie outside a scaled copy of K. Lemma 7.3. For 0 < γ ≤ 1 and 0 < ε ≤ 1, let K be a polytope in R d that is in γ-canonical position, and let

K + = 1 + 2 √ dε K. Then K ⊕ γε ⊆ K + ⊆ K ⊕ ε.
Proof : By definition of γ-canonical position, the distance of every point of ∂K to the origin lies between γ/2 √ d and 1/2 √ d (see Figure 14(a)). To prove the first inclusion (K ⊕γε ⊆ K + ), notice that the distance between any supporting hyperplane of K and its parallel supporting hyperplane of K + is at least

γ 2 √ d • 2 √ dε = γε.
The Minkowski sum K ⊕ γε is equivalent to translating every supporting hyperplane of K away from the origin by distance γε and intersecting the associated (infinite) set of halfspaces. If we apply this to just the (finitely many) defining hyperplanes of K, we obtain a polytope that contains K ⊕ γε, and therefore K ⊕ γε ⊆ K + (see Figure 14(b) and (c)). To establish the second inclusion (K

(c) (b) (a) K K K K ⊕ γε K ⊕ ε γε 1/2 √ d γ/2 √ d K ⊕ γε K +
+ ⊆ K ⊕ ε), observe that each point p ∈ K is in 1-1 correspon- dence with the point p = 1 + 2 √ dε p ∈ K + . Since p is within distance 1/2 √ d of the origin, p is within distance 2 √ dε/2 √ d = ε of p. This implies that K + ⊆ K ⊕ ε, as desired.
While access primitive (iii) does not place any restrictions on the halfspaces used when computing an ε-approximation to K within Q, when the query point q lies outside of K, it may be useful to add further restrictions. In particular, when the query point lies outside of K, it is desirable to obtain a witness to nonmembership in the form of a bounding halfspace of K that does not contain q. (This will be exploited in Section 9 in the reduction of approximate nearest neighbor searching to approximate polytope membership. The witness hyperplane is used to identify the approximate nearest neighbor.) To achieve this, we would like to use bounding halfspaces from the original polytope in our approximation. By a simple application of Carathéodory's Theorem, we can show that we sacrifice only a constant factor by adding this restriction. The following is a straightforward generalization of Lemma 3.1 from Mitchell and Suri [START_REF] Mitchell | Separation and approximation of polyhedral objects[END_REF].

Lemma 7.4. Let K be a convex polytope in R d defined as the intersection of a set H of halfspaces, and let Q ⊆ Q 0 be a quadtree cell. If there exists an ε-approximation of K within Q bounded by m halfspaces, then there exists a subset of H of size at most dm that ε-approximates K within Q.

Proof : The cases K ∩ Q = ∅ and Q ⊆ K are both trivial, so let us assume that the boundary of K intersects Q. Let P be an ε-approximation of K within Q that is bounded by m halfspaces, and let h be any one of these halfspaces. By the definition of such an approximation,

K ∩ Q ⊆ P ∩ Q ⊆ (K ⊕ ε) ∩ Q.
We may assume that h is a supporting halfspace of K ∩ Q, for otherwise we can translate it until it is. Let v be any vertex of K ∩ Q on h's boundary. Let H denote the union of H and Q's bounding halfspaces. By Carathéodory's Theorem there exist d halfspaces from H such that the complement of h is contained within the union of the complement of these d halfspaces. If we replace h with these d halfspaces, the resulting polytope still ε-approximates K within Q.

After repeating this for each of the m halfspaces bounding P , we obtain an ε-approximating polytope by a subset of at most dm halfspaces of H . Let P be the result of removing from this polytope all the halfspaces that are not in H (and hence must bound Q). We have

K ∩ Q ⊆ P ∩ Q ⊆ P ∩ Q ⊆ (K ⊕ ε) ∩ Q,
and therefore P is the desired ε-approximation.

We are now in a position to present our set-cover-based local approximation. This is a bi-criteria approximation since it is suboptimal with respect to both the number of bounding halfspaces and the approximation parameter. Lemma 7.5. For 0 < γ ≤ 1 and 0 < ε ≤ 1, let K be a polytope in R d in γ-canonical position that is given as the intersection of a set H of n halfspaces. Let Q ⊆ Q 0 be a quadtree cell. In O(n/ε d ) time, it is possible to compute a subset H ⊆ H such that (i) The intersection of the halfspaces of H is an ε-approximation of K within Q (ii) If m denotes the minimum number of halfspaces needed to (γε/2)-approximate

K within Q, then |H | is O(m log 1 ε ).
Proof : First, we may assume without loss of generality that ε ≤ 2/ √ d. Otherwise, setting ε = 2/ √ d will certainly satisfy (i) and will only affect the constant factors in the asymptotic bounds of claim (ii) and the construction time. Define β = √ dε/2. By the above assumption, we have

(1 + β) 2 = 1 + √ dε + dε 2 4 ≤ 1 + 3 2 √ dε. Let K + = (1 + β)K and let K ++ = (1 + β)K + = (1 + β) 2 K.
By applying Lemma 7.3 but with ε taking on the values ε/4 and 3ε/4, respectively, we have (see Figure 15(a)). Let δ = γε/4 and let G denote the vertices of a hypercube grid of diameter δ. Let R be the set of grid points that lie within Next, we define a set system to model the approximation process. For each h ∈ H we define a subset R(h) ⊆ R as follows. First, let h + = (1 + β)h denote the corresponding bounding halfspace of the scaled body K + (see Figure 15(b)). Define R(h) to be the subset of points of R that lie outside of h + . Consider a set system consisting of the points of R and the sets R(h) for all h ∈ H. Since every point of R lies outside of K ++ , and hence outside of K + , together these sets cover R. The resulting collection of sets has total cardinality O(n/ε d ).

K ⊕ γε 4 ⊆ K + ⊆ K ++ ⊆ K ⊕ 3ε 4 (8) Q K (a) (c) (b) K ⊕ γε 4 K + K ++ Q h R(h) K ⊕ 3ε 4 h + q h + h q K K + K ++
Q but outside of K ++ , that is, R = G∩(Q\K ++ ). Since Q ⊆ Q 0 ,
Consider any set cover C of the resulting set system. Let P (C) denote the polyhedron that results by intersecting the halfspaces h whose associated set R(h) is included in this cover. (Note that the sets R(h) are based on the halfspaces bounding the scaled body K + while P (C) is based on the halfspaces bounding the original body K.) We assert that P (C) ε-approximates K within Q. It suffices to show that for any point q ∈ Q \ (K ⊕ ε), q is not in P (C). First, observe that for such a point q, all the vertices of the grid cell in which it lies are within distance δ of q. Therefore, by the triangle inequality, each such vertex is at distance at least εδ ≥ 3ε/4 from K. Since by Eq. ( 8), K ++ ⊆ K ⊕ 3ε/4, these vertices are all exterior to K ++ , which implies that they are all members of R. Let q be any of these vertices. Since C is a cover, there exists a halfspace h ∈ H such that R(h) is in the cover and contains this point. This implies that q lies outside the associated halfspace h + (see Figure 15(c)). Because K is in γ-canonical position, the minimum distance between h's bounding hyperplane and the origin is at least γ/2 √ d. Therefore the distance between any point in h to any point exterior to h + is at least

γ 2 √ d ((1 + β) -1) = γ 2 √ d • √ dε 2 = γε 4 = δ.
It follows by the triangle inequality that q is exterior to h, and therefore it lies outside of P (C), as desired.

Let C denote a set cover that results by running the greedy heuristic [START_REF] Cormen | Introduction to Algorithms[END_REF] on the aforementioned set system. By standard results on the greedy heuristic, the size of the resulting cover exceeds that of an optimal cover by a factor of at most ln |R| = O(log 1 ε ). C can be computed in time that is proportional to the total cardinality of the sets of the set system, which is O(n/ε d ). Let H denote the associated set of halfspaces, and let P (C ) denote the intersection of these halfspaces. By the above remarks, P (C ) is an ε-approximation to K within Q, which establishes claim (i).

To establish (ii), consider a (γε/4)-approximation of K within Q that is bounded by the minimum number m of halfspaces. By Lemma 7.4 there exists such an approximation that uses only the bounding halfspaces of K, such that the number of halfspaces is larger by a factor of at most d. Let P + denote this approximation, and let H + ⊆ H denote its bounding halfspaces. By Eq. ( 8), we have P + ⊆ K ⊕ γε/4 ⊆ K + . Let P ++ = (1 + β)P + . Clearly, P ++ ⊆ (1 + β)K + = K ++ . Therefore, every point of R lies outside of P ++ . It follows that the sets R(h) associated with the halfspaces h that bound P + form a set cover of R within our system. Letting C ++ denote this cover, we have

|C | ≤ O(log 1 ε ) • |C ++ | ≤ O(log 1 ε ) • dm = O(m log 1 ε ), as desired.
We can now present the main result of this section, which summarizes the preprocessing time.

Lemma 7.6. Given a full-dimensional convex polytope K in R d defined as the intersection of a set of n halfspaces, approximation parameter 0 < ε ≤ 1, and query time parameter t ≥ 1, there is an algorithm that runs in time O n + 1/ε cp d for some constant c p (which does not depend on d) that constructs a data structure satisfying Theorem 2 but with an additional factor of O(log 1 ε ) in both the space and query times.

Proof : Given K's bounding halfspaces, we apply Lemma 7.2. In O(n + 1/ε d-1 ) time we obtain a polytope K , such that K is in γ-canonical position for γ = 1/2d. K is bounded by a subset H of halfspaces of size n = O 1/ε (d-1)/2 , and the problem of computing a relative ε-approximation of K reduces to the problem of computing an absolute ε -approximation of K where ε = ε/4d √ d. Ideally, we would like to invoke SplitReduce on K using ε as the approximation parameter and t as the query time parameter. Since we do not know how to determine minimum-sized convex approximations efficiently, we will need to relax our expectations. For any quadtree cell Q generated by SplitReduce, we apply Lemma 7.5 on the set H of halfspaces. By claim (i) of this lemma, after O(n /(ε ) d ) = O(1/ε 3d/2 ) time, a subset H ⊆ H can be computed that is an ε -approximation of K within Q. Irrespective of the choice of the query time, the maximum number of quadtree cells generated by SplitReduce is O(1/ε d ), and therefore (after preconditioning) the overall running time of SplitReduce is O(1/ε 5d/2 ). Combined with the O(n + 1/ε d ) time for preconditioning, the algorithm's overall running time is O n + 1/ε cp d , where c p = 5/2.

Let ε = γε /2 = γε/8d √ d. By Lemma 7.5(ii) the number of halfspaces in H is within a factor of ρ = O(log 1 ε ) = O(log 1 ε ) of the size of the minimum-sized ε -approximation of K within Q. Since ε = βε for a constant β, Lemma 3.2 implies that the conclusions of Theorem 2 hold but with an additional factor of ρ = O(log 1 ε ) in both the space and query times.

Lower Bound

In this section, we establish lower bounds on the space-time trade-offs obtained by SplitReduce for polytope membership. In particular, we will prove Theorem 3 from Section 1. Our approach is similar to the lower bound proof of [START_REF] Arya | Space-time tradeoffs for approximate nearest neighbor searching[END_REF]. (Note that this is a lower bound on the performance of SplitReduce, not on the problem complexity. It applies to the stronger existential version of the algorithm.) It is based on analyzing the performance of the algorithm on a particular convex body, a generalized hypercylinder that is curved in k + 1 dimensions and flat in d -1k dimensions. We select the value of k that produces the best lower bound on the storage as a function of t, ε, and d. Throughout, we use the term ε-approximation in the absolute sense, as defined in Section 2.1.

As mentioned earlier, it is well known that Ω 1/ε (d-1)/2 facets are required to ε-approximate a Euclidean ball of unit radius (see, e.g., [START_REF] Bronstein | Approximation of convex sets by polytopes[END_REF]), and this holds for any polytope that that is sufficiently close to a ball in terms of Hausdorff distance. The following utility lemma generalizes this observation to different diameters. The proof is straightforward, but for the sake of completeness we include its proof in the appendix. Lemma 8.1. Let ε and ∆ be real parameters, where 0 < ε ≤ ∆/4. There exists a constant c b and a polytope P in R d of diameter at most ∆ such that any outer ε-approximation of P requires at least c b (∆/ε) (d-1)/2 facets.

Intuitively, in order to produce a polytope that is hard to approximate, it should have high curvature. If the curvature is high in all dimensions, however, the polytope will have a small surface area, and this will make it easier to approximate. Our approach is to consider polytopes based on generalized cylinders, which have constant curvature in some dimensions but are flat in others. Our next lemma introduces such a cylindrical polytope where the number of curved dimensions has been carefully chosen to maximize the space needed by our algorithm for a given query time. Theorem 3 is an immediate consequence. Lemma 8.2. There exists a polytope P in R d such that for all sufficiently small positive ε (depending on d and α) and t = 1/ε (d-1)/α , the output of SplitReduce(K, Q 0 ) on P has total space

Ω 1/ε (d-1) 1-2 √ 2α-3 α -1 .
Proof : To start, as a function of α, we wish to compute an integer dimension k in order to apply Lemma 8.1. Define reals δ = α/2/(d -1), κ = (d -1) 2/α and κ = κ(1 + δ). We observe first that

κ -κ = δ(d -1) 2/α = 1.
Let k = κ , implying that κ ≤ k ≤ κ . (Although we do not include the derivation here, κ has been chosen to produce the best lower bound, but since it is not necessarily an integer, k is obtained by rounding to a nearby integer.) Since α ≥ 4 and d ≥ 2, we have 1

≤ k ≤ d -1.
Let c b denote the constant of Lemma 8.1, and let ∆ = ε((2 d + 1)t/c b ) 2/k . By our assumptions about d and α, we have t = 1/ε Θ (1) and ∆ = ε • t Θ (1) . It follows that for all sufficiently small ε, ∆/4 ≥ ε. Let h denote the linear subspace spanned by the first k + 1 coordinate axes. We apply Lemma 8.1 in R k+1 for this value of ∆. The resulting polytope P (lying in h) has the property that the number of facets of any ε-approximation is at least

c b ∆ ε k/2 = c b    ε (2 d +1)t c b 2/k ε    k/2 = (2 d + 1)t.
We can bound P 's diameter by observing that for all sufficiently small ε

diam(P ) ≤ ∆ = ε (2 d + 1)t c b 2/k ≤ ε 2 d + 1 c b • ε (d-1)/α 2/κ = ε 2 d + 1 c b • ε (d-1)/α √ 2α/(d-1)
.

(Here we made use of the fact that for all sufficiently small ε, the quantity raised to power of 2/k is greater than 1.) Letting c b = (( 1) , we obtain

2 d + 1)/c b ) √ 2α/(d-
diam(P ) ≤ c b ε 1 ε (d-1)/α √ 2α/(d-1) = c b ε 1- √ 2/α .
Since α ≥ 4, for all sufficiently small ε, we have diam(P ) ≤ 1/ √ d. Therefore, P can be enclosed within Q (k+1) 0 . Returning to R d , consider an infinite polyhedral hypercylinder whose "axis" is the (d -1k)dimensional orthogonal complement of h, and whose "cross-section" (i.e., intersection with any (k + 1)dimensional hyperplane parallel to h) is P . Define the polytope C to be the truncated cylinder obtained by intersecting the infinite hypercylinder with hypercube Q (d) 0

(see Figure 16(a)). Let T denote the output of SplitReduce(K, Q (d) 0 ) for C, ε, and t. We will show that T 's total space satisfies the bound given in the lemma's statement. To do this, let Σ denote any set of points placed on C's axis such that the distance between each pair of points is at least 2∆ √ d. (In the degenerate case where k = d -1 the axis is 0-dimensional and Σ degenerates to a single point.) By a simple packing argument, there exists such a set having Ω(1/∆ d-1-k ) points. For any q ∈ Σ, let P q denote the cross-section of C passing through q (see Figure 16(b)). Consider the set of leaf cells of T that intersect P q . By applying Lemma 8.1 to the (k + 1)-dimensional hyperplane on which P lies, it follows that these cells together must contain at least (2 d + 1)t halfspaces. We count the contributions of these cells by classifying them into two types. We say that a leaf cell of T is large if its side length is at least ∆, and otherwise it is small. By a simple packing argument, the number of large leaf cells intersecting P q is at most 2 d . Since each leaf cell contains at most t halfspaces, the large leaf cells can together contain at most 2 d t halfspaces.

∆ ≥ 2∆ √ d (b) ∆ h C (a) P q q 1 √ d
Therefore, the small leaf cells intersecting P q together contain at least (2 d + 1)t -2 d t = t halfspaces. Because the points of Σ are separated from each other by distance at least 2∆ √ d, which is strictly larger than the diameter of any small leaf cell, each small leaf cell can intersect P q for at most one q ∈ Σ. Therefore, the total space contribution of all the small leaf cells for all points of Σ is at least t

• |Σ|. Let c b = (c b /(2 d + 1)) 2(d-1-k)/k
. T 's total space can be asymptotically bounded from below as

t ∆ d-1-k = t ε (2 d +1)t c b 2/k d-1-k = c b • t ε • t 2/k d-1-k = c b • t 1-2(d-1-k)/k ε d-1-k .
Clearly, c b = Θ(1). Recall that t = 1/ε (d-1)/α . Then, T 's total space is asymptotically bounded from below as 1 ε

(d-1)-k+ d-1 α 1- 2(d-1-k) k = 1 ε (d-1)-k+ d-1 α 3- 2(d-1) k (9)
Let E(α) denote this exponent. In order to complete the proof, we provide a lower bound on E(α). We use the fact that κ ≤ k ≤ κ , apply the definitions of κ, κ , and δ, and straightforward manipulations to obtain

E(α) ≥ (d -1) -κ + d -1 α 3 - 2(d -1) κ = (d -1) 1 - 2 √ 2α -3 α -1.
Substituting this value for the exponent in Eq. ( 9) completes the proof.

Approximate Nearest Neighbor Searching

In this section, we present a reduction from approximate nearest neighbor searching to approximate polytope membership, which will allow us to prove Theorem 4 from Section 1. Our reduction will involve the following additional assumptions regarding the implementation of SplitReduce. First, (as in Section 7) we assume that K is presented as the intersection of n halfspaces. Second, we assume that a leaf node is labeled as "inside" only if it lies entirely within K (as opposed to lying within K ⊕ ε as described in SplitReduce). Third, we assume that leaf cells that store halfspaces use only bounding halfspaces of K.

Clearly, these assumptions do not affect the data structure's correctness. We assert that they do not affect the data structure's asymptotic query time or space bounds. Regarding the second assumption, observe that for any cell Q that lies within K ⊕ ε, K can be ε-approximated within Q using a single halfspace (any halfspace that contains Q suffices). Regarding the third assumption, recall that Lemma 7.4 shows that we may assume that the approximating halfspaces for each node are drawn from the input halfspaces at the expense of a constant factor increase in the query time.

The reduction from approximate nearest neighbor searching to approximate polytope membership is based on the approximate Voronoi diagram (AVD) construction from [START_REF] Arya | Space-time tradeoffs for approximate nearest neighbor searching[END_REF]. The AVD employs a height balanced variant of a quadtree, a balanced box decomposition (BBD) tree [START_REF] Arya | Approximate range searching[END_REF] to be precise. Each cell of a BBD tree corresponds to the set theoretic difference of two quadtree cells, an outer box and an optional inner box. Each leaf cell of the tree stores a set of representative points with the property that for any query point q lying within this cell, at least one of these representatives is an ε-nearest neighbor of q. A query is answered by locating the leaf cell that contains the query point and then determining the nearest representative from this cell (by brute force). The AVD's space is dominated by the total number of representatives over all the leaf cells. The query time is the height of the tree plus the number of representatives in the leaf cell. A data structure for nearest neighbor searching is said to be in the AVD model if it has this general form, that is, a covering of the query region by hyperrectangles of bounded aspect ratio, each of which is associated with a set of representative points [START_REF] Arya | Space-time tradeoffs for approximate nearest neighbor searching[END_REF]. Lower bounds on the performance of any data structure in the AVD model were given in [START_REF] Arya | Space-time tradeoffs for approximate nearest neighbor searching[END_REF].

The reader need not be familiar with the details of the AVD data structure. The next lemma encapsulates the important technical information needed for our reduction. It follows easily from the proofs of Lemmas 6.1 and 8.1 in [START_REF] Arya | Space-time tradeoffs for approximate nearest neighbor searching[END_REF]. Given a cell Q in a BBD tree, let B Q denote the ball of radius 2•diam(Q) whose center coincides with the center of Q's outer box (see Figure 17(a)). Given a Euclidean ball B of radius r and positive c, let cB denote the ball concentric with B of radius cr. Lemma 9.1. Let 0 < ε ≤ 1/2 be a real parameter and X be a set of n points in R d . It is possible to construct a BBD tree T with O(n • log 1 ε ) nodes, where each leaf cell Q stores a subset R Q ⊂ X satisfying the following properties:

(i) For any point q in Q, one of the points in R Q is an ε-approximate nearest neighbor of q. (ii) At most one point of R Q is contained in the ball B Q , and the remaining points of R Q are contained in c q B Q \ B Q for some constant c q (which depends on the dimension). (iii) The total number of representative points over all the leaf cells of

T is O(n • log 1 ε ).
Moreover, it is possible to compute the tree T and the sets R Q for all the leaf cells in total time O(n • log n • log 1 ε ), and the cell that contains a query point can be located in time In the AVD data structure of [START_REF] Arya | Space-time tradeoffs for approximate nearest neighbor searching[END_REF] the closest representative point to a query point is determined by brute-force enumeration of the elements of R Q . We consider whether it is possible search them more efficiently by reduction to polytope approximation. The following lemma explains how to connect Lemma 9.1 with approximate polytope membership queries. Our construction uses the well known lifting transformation [START_REF] Agarwal | Ray shooting and parametric search[END_REF][START_REF] Edelsbrunner | Algorithms in Combinatorial Geometry[END_REF]. Let (x 1 , . . . , x d+1 ) denote the coordinates of R d+1 , and let us think of (d + 1)st coordinate axis as being directed vertically upwards. Let Ψ denote the paraboloid x d+1 = d i=1 x 2 i . Given a point p ∈ R d , let p ↑ denote the vertical projection of p onto Ψ (see Figure 17(b)), and let h(p) denote the hyperplane tangent to Ψ at p ↑ . That is, the points of h(p) satisfy x d+1 = d i=1 2p i x ip 2 . Given q ∈ R d , let q [p] denote the point on h(p) hit by a vertical ray shot downwards from q ↑ . A straightforward consequence of the definition of Ψ is that the squared distance between q and p in R d is equal to the length of this vertical segment, that is,

O(log n + log log 1 ε ). ∈ R Q ∈ S Q cB Q B Q (a) (b) h(p) E Q p q r x d+1 r ↑ Ψ p ↑ q ↑ q [p]
qp 2 = q ↑ q [p] .
This suggests the following approach to computing the closest representative point through vertical ray shooting. Consider the (unbounded) convex polyhedron that results by taking the upper envelope of the hyperplanes h(p) associated with the lifted representatives. Given the query point q ∈ R d , a ray shot vertically downward from q ↑ hits some facet of this polyhedron. It follows from the above remarks, that the representative associated with this hyperplane is the closest to q. We can simulate ray shooting by applying polytope membership queries in concert with binary search. Of course, some care will be needed to map this problem into our context, which assumes a bounded polytope and approximation. Lemma 9.2. Let 0 < ε ≤ 1/2 be a real parameter and consider a quadtree cell Q and a set of representative points R Q as in Lemma 9.1. Given a data structure for ε-approximate polytope membership in d-dimensional space with query time t d (ε) and space s d (ε), it is possible to preprocess R Q into an ANN data structure for query points in Q with query time O(t d+1 (ε) • log 1 ε ) and space O(s d+1 (ε)).

Proof : Since at most one point of R Q is contained in B Q , the corresponding point may be inspected separately without increasing the complexity bounds. Therefore, we may assume that all points of

R Q are contained in c q B Q \ B Q .
Although we assume that the errors in polytope membership are absolute (because of standardization), errors in approximate nearest neighbor searching are relative. That is, a point r is an ε-approximate nearest neighbor of q if qr ≤ (1 + ε) qp , where p is q's true nearest neighbor. Because errors are relative, we may assume that space has been translated and uniformly scaled so that Q is mapped to

Q (d)
0 , the hypercube of unit diameter centered at the origin in R d . As a result, B Q is mapped to a ball of radius 2. It follows that the distance from any point of Q to any point of R Q is greater than 1. Therefore, an absolute error of ε implies a relative error of at most ε.

In order to reduce nearest neighbor searching among the points of R Q to polytope membership, let E Q denote the upper envelope, that is, the intersection of the upper halfspaces, of the hyperplanes h(p), for all p ∈ R Q (the shaded region in Figure 17(b)). As mentioned above, the facet of E Q hit by shooting a ray vertically downward from q ↑ corresponds to the closest point of R Q to q.

Since the upper envelope is unbounded, we first compute a bounded convex polytope on which to perform approximate membership queries. Because the query points lie in Q, we are only interested in the portion of E Q that projects vertically onto Q. Given that the distance of any point p ∈ R Q to the origin is at most 2c q = O(1), it follows that the portion of E Q of interest fits within an axis-aligned (d + 1)-dimensional hypercube of constant diameter that is centered at the origin. Let Q denote such a hypercube, let K Q = E Q ∩ Q , and let ε = ε/6c q . We invoke SplitReduce to construct an ε -approximate membership data structure for K Q . (More formally, we first scale Q into standard form, and we scale ε by the same factor. We then apply SplitReduce with the scaled value of ε . Since Q is of constant diameter, the scale factor will also be a constant, and therefore only the constant factors in the analysis will be affected. We then apply an inverse scaling to obtain the desired ε -approximating polytope for K Q .)

We simulate the ray shooting process by a binary search to locate the contact point approximately. Consider the vertical segment formed by intersecting Q with the vertical line passing through q ↑ . The upper endpoint of this segment is clearly inside K Q and its lower endpoint is outside. We repeatedly split the segment at its midpoint, perform an approximate polytope membership query, and retain the subsegment whose upper endpoint is (approximately) inside K Q and whose lower endpoint is (approximately) outside. We terminate the search when the length of the segment falls below ε . Since Q is of constant diameter, the search terminates after O(log 1 ε ) membership queries. Let us denote the endpoints of this final segment as q + (upper) and q -(lower).

Recall our assumption that cells are labeled by SplitReduce as "inside" or "outside" only if they lie entirely inside or outside K Q , respectively. It follows that as we traverse the cells that intersect the segment q + q -from top to bottom, we cannot transition directly from an "inside" cell to an "outside" cell. Therefore, at least one of these cells must contain a set of representative hyperplanes. Let h(r) denote the hyperplane having the topmost intersection with the vertical ray. We return r as the approximate nearest neighbor (see Figure 18). It is easy to see that this algorithm satisfies the desired time and space bounds. All that remains is to establish correctness, by showing that r is indeed an ε-approximate nearest neighbor of q. In order to do this, let p be q's true nearest neighbor in R Q . Due to the nature of the binary search, q + lies within distance ε of K Q . (Note that it might lie within K Q .) Thus, the distance from q + to the upper halfspace bounded by h(p) is at most ε . By the triangle inequality, the distance from q -to this halfspace is at most ε + ε = 2ε . Since p is q's true nearest neighbor, q [p] lies on ∂K Q , and so the hyperplane h(p) separates q -from K Q . This implies that the distance from q -to h(p) is also not greater than 2ε .

p q r x d+1 r ↑ p ↑ q ↑ q [r] q + q - ε q [p]
We claim that the vertical distance from q -to q [p] is at most ε. To see why, recall that p lies within a ball of radius 2c q centered at the origin. This implies that h(p) cannot be too steep, that is, the angle formed between h(p)'s normal vector and the vertical axis can be bounded away from π/2 by a constant. By basic linear algebra, it can be shown that the ratio of the vertical and orthogonal distances of any point to h(p) is bounded above by 4c 2 q + 1 < 3c q . Therefore, we have q [p] q -≤ 3c q (2ε ) = ε, as desired.

Because r is the witness produced by the algorithm, h(r) separates q -from K Q , which implies that q [r] lies above q -. Thus, we have q [p] q [r] ≤ q [p] q -≤ ε. Therefore,

qr 2 = q ↑ q [r] = q ↑ q [p] + q [p] q [r] ≤ q ↑ q [p] + ε.
By the lifting transformation, we have q ↑ q [p] = qp 2 , and combining this with the fact that qp ≥ 1, we have

qr 2 ≤ qp 2 + ε ≤ qp 2 + qp 2 ε = qp 2 (1 + ε) ≤ ( qp (1 + ε)) 2 .
Therefore, r is an ε-approximate nearest neighbor of p, which completes the proof.

The above lemma shows how to apply approximate polytope membership to efficiently answer approximate nearest neighbor queries within each cell of the AVD. To obtain a complete data structure for approximate nearest neighbor searching we apply this to every leaf cell of the AVD. Lemma 9.3. Let 0 < ε ≤ 1/2 be a real parameter and X be a set of n points in R d . Given a data structure for approximate polytope membership in d-dimensional space with query time at most t d (ε) and storage s d (ε), it is possible to preprocess X into an ANN data structure with query time O(log n + t d+1 (ε) • log 1 ε ) and space

O n log 1 ε + n s d+1 (ε) t d+1 (ε) .
Proof : Following Lemma 9.1, construct a BBD-tree T , and for each leaf cell Q of T , construct the set of representative points R Q . For each leaf cell such that |R Q | ≤ t d+1 (ε) • lg 1 ε , store the set R Q and answer the corresponding queries by brute force. For the nodes with

|R Q | > t d+1 (ε) • lg 1
ε , use the construction from Lemma 9.2.

To answer an ANN query we search the AVD of Lemma 9.1 to find the leaf cell containing the query point and then apply Lemma 9.2. Thus, the query time is

O log n + log log 1 ε + t d+1 (ε) • log 1 ε = O log n + t d+1 (ε) • log 1 ε .
To bound the total space, observe from Lemma 9.1(iii) that the total number of representative points is O(n log 1 ε ). Thus, by a simple counting argument, the number of leaf cells with more than t d+1 (ε) • lg 1 ε representatives is O(n/t d+1 (ε)). Therefore, the total space of the data structure is

O(n log 1 ε + n(s d+1 (ε)/t d+1 (ε))).
Because of its reliance on binary search, the generic reduction given in Lemmas 9.2 and 9.3 is not formally in the AVD model. Recall that the AVD model is important because lower bounds have been established in this model [START_REF] Arya | Space-time tradeoffs for approximate nearest neighbor searching[END_REF], and thus these lower bounds do not apply here. However, by sacrificing generality and a factor of O(log 1 ε ) in the space bound, we can exploit the properties of SplitReduce to obtain a data structure that is in the AVD model. Lemma 9.4. Let 0 < ε ≤ 1/2 be a real parameter and X be a set of n points in R d . Given a split-reduce data structure for approximate polytope membership in d-dimensional space with query time at most t d (ε) and storage s d (ε), it is possible to preprocess X into an ANN data structure in the AVD model with query time O(log n + t d+1 (ε) • log 1 ε ) and space

O n 1 + s d+1 (ε) t d+1 (ε) log 1 ε .
Proof : As in Lemma 9.3, construct a BBD-tree T , and for each leaf cell Q of T , construct the set of representative points R Q . We may assume that |R Q | > t d+1 (ε) • lg 1 ε , since otherwise we just use the points of R Q as the representatives. In order to handle query points lying within Q, we apply Lemma 9.2, where queries are answered using the tree produced by SplitReduce. Let T Q denote the resulting tree. We exploit the fact that the SplitReduce data structure associates a collection of hyperplanes with each leaf cell of T Q , and by the nature of our reduction, each of these hyperplanes corresponds to a lifted point of R Q . These lifted points will play the role of nearest neighbor representatives. Intuitively, our approach is to "undo" the lifting transformation by projecting the leaf cells of T Q vertically from R d+1 down to R d and then building a d-dimensional AVD structure based on this projection.

The projection of the cells of T Q onto R d naturally defines a quadtree subdivision of R d , which we denote by T Q (see Figure 19(a)). For each leaf cell Q of T Q , let C Q denote the infinite vertical cylinder in R d+1 whose cross section is Q (see Figure 19(b)). Because Q is a leaf, any leaf cell of T Q that intersects this cylinder projects onto a hypercube that contains Q .

x d+1 Q C Q contribute to R Q T Q ∂K Q T Q T Q T Q x d+1 (a) (b)
Figure 19: Producing an ANN data structure in the AVD model.

Recall the lifted polytope K Q of Lemma 9.2. For each leaf cell of T Q that contains a point whose vertical distance from ∂K Q is at most ε, we create a representative point corresponding to each of the hyperplanes that SplitReduce associates with this leaf cell. We denote the resulting collection of representatives by R Q . These are the only hyperplanes that are relevant to the binary search of Lemma 9.2, and therefore one of them will provide the final witness in the binary search (the point r in the proof of Lemma 9.2). This implies that R Q constitutes a valid representative set for ε-approximate nearest neighbor searching for any query point that lies in Q . Thus, the resulting data structure is a valid AVD structure.

In order to bound the query time we recall some of the observations made in the proof of Lemma 9.2. Since K Q is contained within a hypercube of constant diameter centered at the origin, the absolute slopes of the hyperplanes of the approximating polytope are bounded above by some constant. Recall that the leaf cells of T Q that contribute a point to R Q have side lengths at least as large as that of Q . By the same reasoning used in Lemma 3 of [START_REF] Arya | Approximate range searching[END_REF], the number of such quadtree leaf cells that can intersect ∂K Q is bounded by a constant, which we denote by c . (This constant depends on the dimension d and the largest possible slope.) Therefore, the total number of cells contributing a representative to R Q is at most c . Since each cell contributes at most t d+1 (ε) representatives, the total number of representatives associated with any leaf cell of

T Q is at most c • t d+1 (ε) = O(t d+1 (ε)).
The bound on the total space is complicated by the fact that a large cell that intersects ∂K Q may overlap the columns of many small leaf cells, and hence a large cell's representatives may be replicated many times. Let M denote the set of internal nodes of T Q all of whose children are leaves. We encountered this set earlier in the proof of Lemma 3.1. As we saw in that earlier lemma, because each node of M was split by SplitReduce, it follows that each such cell requires more than t d+1 (ε) halfspaces to approximate K(Q), and thus, the children of M together require at least as many representatives. Therefore we have |M | • t d+1 (ε) ≤ s d+1 (ε). Reasoning as we did in Lemma 3.1, every internal node of T Q is either in M or is an ancestor of a node in M . Thus, the number of internal nodes is at most |M | • height(T Q ). Since every internal node has 2 d children, the total number of nodes in

T Q is at most 2 d • |M | • height(T Q ).
Clearly, the number of leaf cells of T Q can be no larger. As we saw in the previous paragraph, each leaf cell of T Q is associated with at most c • t d+1 (ε) representatives. Since the tree is of height O(log 1 ε ), the total number of representatives over all these cells is at most

(2 d • |M | • height(T Q ))(c • t d+1 (ε)) = c • 2 d • height(T Q ) • (|M | • t d+1 (ε)) ≤ (c • 2 d • log 1 ε ) • s d+1 (ε) = O(s d+1 (ε) • log 1 ε ). By Lemma 9.1(iii), the total number of representatives in T Q is O(n log 1 ε )
. By a counting argument, the number of leaf cells with more than t d+1 (ε) • log 1 ε representatives is O(n/t d+1 (ε)). Therefore, the total space is

O n log 1 ε + n t d+1 (ε) • s d+1 (ε) • log 1 ε = O n 1 + s d+1 (ε) t d+1 (ε) log 1 ε as desired.
By combining this with Theorem 2 (applying the more accurate space bounds from Lemma 6.4) we obtain the main result of this section. Lemma 9.5. Let 0 < ε ≤ 1 be a real parameter, α ≥ 1 be a real constant, and X be a set of n points in R d . There is a data structure in the AVD model for approximate nearest neighbor searching that achieves Query time:

O log n + (1/ε d/2α ) • log 2 1 ε Space: O n • max log 1 ε , 1/ε d( 1 2 -1 2α ) , for 1 ≤ α < 2 and, O n/ε d 1- lg α α -1 2 lg α + 1 2α
, for α ≥ 2.

The constant factors in the space and query time depend only on d and α (not on ε). At the expense of increasing the query time and space by a factor of O(log 1 ε ) it is possible to construct the data structure in time O(n(log n + 1/ε c d ) log 1 ε ), for some constant c (that does not depend on d or α). Proof : Given X and ε, we first observe that if 1/16 < ε ≤ 1, we may set ε = 1/16, since this will only affect the constant factors in the asymptotic bounds. We consider two cases based on the value of α.

If 1 ≤ α < 2, we will apply Theorem 2 with the values of d and α of the theorem set to d = d + 1 and α = 4, respectively. The theorem states that there is a data structure that achieves query time

O (log 1 ε )/ε d -1 α = O (1/ε d/4 ) • log 1 ε = O (1/ε d/2α ) • log 1 ε ( 10
)
and space

O 1/ε (d -1) 1- 2 lg α -2 α = O 1/ε d/2 . ( 11
)
Letting t d+1 (ε) and s d+1 (ε) denote the quantities of Eqs. [START_REF] Arya | Approximate range searching[END_REF] and [START_REF] Ball | An elementary introduction to modern convex geometry[END_REF], respectively, we apply Lemma 9.4 to obtain a data structure in the AVD-model with query time O log n + (1/ε d/2α ) • log2 1 ε and space

O n 1 + 1/ε d/2 (1/ε d/2α ) • log 1 ε log 1 ε = O n • max log 1 ε , 1/ε d( 1 as desired.
Otherwise, if α ≥ 2, we apply Theorem 2 (but using the more accurate space bounds from Lemma 6.4) in dimension d = d + 1 and with trade-off parameter α = 2α. (Observe that α ≥ 4, as required by Theorem 2 and Lemma 6.4.) This yields an approximate polytope membership data structure with query time t d+1 (ε) = O (1/ε d/2α ) • log 1 ε and space

s d+1 (ε) = O 1/ε d 1-2 lg(2α) -2 2α + 1 2 lg(2α) = O 1/ε d 1- lg α -1 α -1 2 lg α
.

By Lemma 9.4 this implies the existence of a data structure in the AVD-model with the desired query time of

O log n + (1/ε d/2α ) • log 2 1 ε and space O   n   1 + 1/ε d 1- lg α -1 α -1 2 lg α (log 1 ε )/ε d/2α   log 1 ε   .
Since α ≥ 2, we may ignore the "1+" term in the inner parenthetical factor. After some simplification we obtain the desired space bound of

O n/ε d 1- lg α α -1 2 lg α + 1 2α
.

The preprocessing involves first computing the AVD, which by Lemma 9.1 takes O(n • log n • log 1 ε ) time. For each of the O(n log 1 ε ) leaf cells Q of the AVD, we apply SplitReduce in dimension d + 1 to its associated set R Q of representatives. By Lemma 7.6 this takes O(n Q +1/ε cp(d+1) ) time, where n Q = |R Q |, and c p is a constant that does not depend on d. Summing over all the leaf cells of the AVD and recalling that the total number of representatives is O(n • log 1 ε ), it follows that the total preprocessing time is on the order of

n • log n • log 1 ε + Q n Q + 1/ε cp(d+1) = n • log n • log 1 ε + n • log 1 ε • 1 ε cp(d+1) = n log n + 1 ε c d log 1 ε ,
where c = c p (d + 1)/d, as desired. Because of the reliance on approximate set cover in the processing of Lemma 7.6, the query time and space are larger by a factor of O(log 1 ε ).

Note that the above proof uses the AVD-based reduction given in Lemma 9.4. If instead we had used Lemma 9.3, we would obtain a slight improvement in the space, by a factor of Θ(log 1 ε ), at the loss of having a data structure in the AVD model. By the simple observation that 1/2 lg α ≥ 1/α, the above space bound for the α ≥ 2 case simplifies to O n/ε d(1-lg α α -1 2α ) , and this establishes Theorem 4.

Proof of the Area-Product Bound

In this section, we present lower bounds for the product of the area of (restricted) ε-dual caps and the associated Voronoi patches, and in particular, we present a proof of Lemma 5.2, which appeared at the end of Section 5.

We begin by recalling some notation. We are given a convex body K in R d , and a pair (p, h(p)) where p ∈ ∂K and h(p) is a supporting hyperplane passing through p, such that p lies within a unit ball centered at the origin. Also recall that p ε denotes the point lying at distance ε from p in the direction of the outward normal orthogonal to h(p) at p. S denotes the Dudley hypersphere, which is centered at the origin and is of radius 3. For y ≥ 1, let H (y) (p) be any hyperplane that is parallel to h(p) and translated away from K by distance y. (This is illustrated in Figure 20. Note that the figures of this section are not drawn to scale.) To simplify our descriptions, we consider the directed line segment from p to p ε to be "vertically downwards," so that the hyperplanes h(p) and H (y) (p) are "horizontal" with h(p) above H (y) (p). Recall that the ε-dual cap defined by p, denoted D(p), is the portion of ∂K that is visible from p ε (see Figure 21(a)). Also, recall that Vor(D(p)) consists of the points that are exterior to K whose closest point on ∂K lies within D(p). Define the base of D(p), denoted Γ(p), to be the intersection of h(p) with the convex hull of K ∪ {p ε }.

For δ > 0, recall that the δ-restricted ε-dual cap defined by p, denoted D δ (p), is D(p) ∩ B δ (p), where B δ (p) is the Euclidean ball of radius δ centered at p (see Figure 21(b)). As before, Vor(D δ (p)) is the set of points that are exterior to K whose closest point on ∂K lies within D δ (p). Also, the δ-restricted base, denoted Γ δ (p) is Γ(p) ∩ B δ (p).

Our objective in this section is to establish bounds on the product of the area of a √ ε-restricted ε-dual cap and its Voronoi patch on the Dudley hypersphere. It will be easier to start with hyperplane patches on H (y) (p) and then generalize to spherical patches on S. The main result of this section is given in the following lemma. Part (ii) is equivalent to Lemma 5.2, which is our main objective. Part (i) is a useful intermediate result.

Lemma 10.1. Let K be a convex body in R d , and let 0 < ε ≤ 1/8 and δ = √ ε. There are constants c a and c a (depending only on d) such that for any point p ∈ ∂K:

(i) Given any y ≥ 1, area(D δ (p)) • area(Vor(D δ (p)) ∩ H (y) (p)) ≥ c a • ε d-1 .
(ii) If K is fat and has diameter at least 2ε, and p lies within a unit ball centered at the origin, then area

(D δ (p)) • area(Vor(D δ (p)) ∩ S) ≥ c a • ε d-1 .
triangles, it is easy to see that the length of p q is • ε/ pv . Since v ∈ Γ, q lies within polar r (Γ), where r = √ • ε. Because y ≥ 1 and ε ≤ 1/8, we have r = Ω( √ ε). This observation generalizes readily to higher dimensions, and it follows that polar r (Γ) ⊆ Vor(D) ∩ H. We will show how to generalize this intuition to higher dimensions and the δ-restricted setting. For any z ∈ H let w denote its nearest neighbor on ∂K. In order to prove Lemma 10.2, it suffices to show that if w / ∈ D δ (implying that z / ∈ Vor(D δ ) ∩ H), then z / ∈ polar r (Γ δ ). By our assumption that H lies below K it follows that w lies on the "lower surface" of ∂K (meaning that a vertical ray directed downwards from w does not intersect the interior of K). Since w is not in the restricted cap, we know that either w / ∈ D or w / ∈ B δ . It will simplify the analysis to reduce the problem to a 2-dimensional setting. Consider the plane Φ that contains the points p, p ε , and w. (Note that these points are not collinear.) Let t be the point of tangency on ∂K ∩ Φ with respect to p ε that lies on the same side as w (see Figure 23(a)). Let v be the intersection of the line segment p ε t with h. We may identify Φ with R 2 by imposing a coordinate system on Φ where the origin is at p, the y-axis is directed upwards away from p ε and the x-axis is parallel to the vector from p to v. Given a point u ∈ Φ, let u x and u y denote its coordinates relative to this coordinate system. Further, if u ∈ ∂K ∩ Φ, let u θ denote the slope of the (unique) supporting line on Φ passing through u. Note that z need not lie on Φ. Let z be the orthogonal projection of z onto Φ. Observe that t θ = ε/ pv , and therefore pv = ε/t θ . By our choice of coordinate system and assumptions about orientations, the coordinates of w, t, and the slopes w θ and t θ are all nonnegative quantities. The point v lies on the base Γ of p's unrestricted dual cap. By employing our coordinate system on h, we can identify v with a vector in R d-1 (emanating from p). If pv ≤ δ, then v contributes a bounding halfspace to polar r (Γ δ ). This halfspace is bounded by a hyperplane that is orthogonal to v and lies at distance r 2 / pv from the origin. Let us think of this halfspace, which we denote by h v , as lying on H (see Figure 23(a)). Recalling that r = ε/8, the distance of h v 's bounding hyperplane to the origin p is (ε/8)/ pv = t θ /8. On the other hand, if pv > δ, then v lies outside the restricted base. In this case v's subvector of length δ lies on the boundary of the restricted base and contributes to polar r (Γ δ ) a halfspace whose bounding hyperplane is at distance (ε/8)/δ from the origin. Recalling that δ = √ ε, this is equal to δ/8. Thus, in either case, polar r (Γ δ ) is bounded by a halfspace whose defining hyperplane is orthogonal to v and lies at distance max(δ, t θ )/8 from the origin. This hyperplane intersects the horizontal line H ∩ Φ at some point v that lies to the right of p at distance v x = max(δ, t θ )/8 (see Figure 23(b)).

p ε t K p • ε v p h H ε v q q
p ε t v K ∩ Φ p B δ w z ≥ w x + w θ p max(δ, t θ ) 8 h H v (a) v p p H h h v z z p ε polar r (Γ δ ) (b) Φ t K ∩ Φ w v
Because the hyperplane passing through v is orthogonal to v, in order to show that z / ∈ polar r (Γ δ ), it suffices to show that z does not lie within h v , which is equivalent to showing that z x > v x . We have thus reduced the problem to a two-dimensional setting.

Recall that w is the closest point to z on ∂K. We assert that w is also the closest point to z on ∂K ∩ Φ. The reason is that the squared distance from z to any point on ∂K ∩ Φ can be expressed as the sum of the squared distance from z to this point and the squared distance from z to z . Since the latter quantity is the same for all points on Φ, the closest point to z is also the closest point to z . From basic properties of convexity, it follows that the line wz is orthogonal to the support line passing through w on ∂K ∩ Φ. Therefore, the slope of wz (in Φ's coordinate system) is -1/w θ , and in particular we have (z xw x )/(z yw y ) = -w θ . Since h and H are separated by at least unit distance (with h above H), we have w yz y ≥ 1, and so z x ≥ w x + w θ .

Thus, to complete the proof of Lemma 10.2, it suffices to show that if w / ∈ D δ then v x < w x + w θ . We first establish two useful technical results. These results will be applied in a context where w lies within the unrestricted dual cap but outside the restricted dual cap. That is, when w x ≤ t x but w / ∈ B δ . The first result shows that if t θ is sufficiently small, the slope of the line pw is at most unity. The second shows that if t θ is sufficiently large, the slope of pw is not much smaller than the slope of t's supporting line.

Lemma 10.3. Given the preconditions of Lemma 10.1 and the aforementioned 2-dimensional reduction, and given w and t as introduced above, where w x ≤ t x and w / ∈ B δ :

(i) if t θ ≤ δ √ 8, then w y /w x ≤ 1, and (
ii) if t θ > δ √ 8, then w y /w x ≥ t θ /2.
The proof involves simple geometry and is given in the appendix.

We are now in position to complete the proof of Lemma 10.2. Recall that our objective is to show that if w / ∈ D δ then v x < w x + w θ , where v x = max(δ, t θ )/8. We consider two cases, depending on by the conditions of Lemma 10.1(ii), p lies within unit distance of the origin, and so by the triangle inequality p lies within distance 1 + ε of the origin. The points of D δ and D δ lie within distances δ and δ of p and p , respectively. Therefore, the distance of any point of D δ or D δ from the origin is at most 1 + max(δ, ε + δ ). As shown in the proof of Lemma 10.5, δ + ε ≤ δ, and therefore this distance is at most 1 + δ ≤ 1 + 1/ √ 8 < 3. Therefore, both caps lie within S. Consider any point q ∈ Vor(D δ ) ∩ S. It suffices to show that q ∈ Vor(D δ ) ∩ S. Let q be the closest point to q on ∂K . By convexity, q is the closest point of q on ∂K if and only if the supporting hyperplane at q , denoted h(q ), is orthogonal to the line q q . Let q be the closest point to q on ∂K. By basic properties of Minkowski sums, the segment qq is orthogonal to both the supporting hyperplanes h(q) and h(q ) at q and q , respectively (see Figure 25). It follows that all three points q, q and q are collinear, and h(q) is orthogonal to the segment qq . Therefore, q is the closest point to q on ∂K. Since q ∈ Vor(D δ ) ∩ S, we have q ∈ D δ , which means that q is visible from p ε and q lies within distance δ of p . Because h(q) and h(q ) are parallel, it follows that q is also visible from p ε . Therefore, q lies in p's unrestricted dual cap D. To prove that q lies within the restricted cap D δ , it suffices to show that pq ≤ δ. We apply a standard result from convexity theory which states that for any convex body K and two points p and q that are exterior to K, if p and q are their respective nearest neighbors on ∂K, then pq ≤ p q (see, e.g., Lemma 4.3 in [31]). Clearly, this applies in our situation, and so pq ≤ p q ≤ δ < δ, which implies that q ∈ D δ . In summary, the closest point to q on ∂K lies within D δ , implying that q ∈ Vor(D δ ) ∩ S, as desired.

t θ . First, if t θ ≤ δ √ 8, then v x ≤ max(δ, δ √
q p ε K ε K = K ⊕ ε ε q p q S h(q ) h(q) p
Before completing the proof of Lemma 10.1(ii), we exploit the smoothness of K to establish a relationship between the areas of Vor(D δ ) ∩ S and polar r (Γ δ ), where the polar radius r is suitably modified for the smoothed context. This is given in the next lemma. The proof involves basic geometric reasoning and is given in the appendix. .

Selecting any c a ≤ (c m /c )(1/32) d-1 establishes Lemma 10.1(ii). This concludes our proof of the area bounds.

Concluding Remarks

In this paper we have presented an efficient data structure for determining approximately whether a given query point lies within a convex body. Our solution is based on a simple and natural quadtreebased algorithm, called SplitReduce. Our principal technical contribution has been an analysis of the space-time trade-offs for this algorithm. These are the first nontrivial space-time trade-offs for this problem. We do not know whether this analysis is tight, but we presented a lower bound example that demonstrates the limits of possible improvements. We also demonstrated the value of approximate polytope membership by showing that our data structure can be combined with an AVD data structure to produce significant improvements to the space-time trade-offs of approximate nearest neighbor searching in Euclidean space. Our analysis of the trade-offs involved a combination of a number of novel techniques, which may be of broader interest. One notable example is the application of the Mahler volume as a means of analyzing the local structure of a convex body through consideration of both its primal and dual representations. This resulted in an efficient two-pronged sampling strategy for computing hitting sets of low cardinality for ε-dual caps. The Mahler volume has also been applied in [START_REF] Arya | Optimal area-sensitive bounds for polytope approximation[END_REF] to derive an optimal area-sensitive bound on the number of facets needed to approximate a convex body.

This work provokes a number of questions for further research. The first involves extending approximate polytope membership queries to other approximate query problems involving convex bodies. For example, in Section 9 we showed how to reduce approximate nearest neighbor searching in dimension d to vertical ray shooting queries in dimension d + 1. However, the polytope involved had a very restricted structure. It would be interesting to know whether there is a data structure exhibiting similar trade-offs for answering approximate ray-shooting queries for general convex bodies. Another example is answering approximate linear-programming queries, where a convex body is preprocessed, and the problem is to determine an extreme point of the body approximately in a given query direction. A further generalization of this would be to extend the work of Barba and Langerman [START_REF] Barba | Optimal detection of intersections between convex polyhedra[END_REF] to an approximate setting. It particular, is it possible to preprocess convex bodies so that given two such bodies that have been translated and rotated, it can be decided efficiently whether they intersect each other approximately.

Our result on approximate nearest neighbor searching relies on the lifting transformation to reduce the problem to approximate polytope membership. As a consequence, this approach is applicable only to Euclidean distances. This raises the question of whether there exists a more direct route to approximate nearest neighbor searching that achieves similar space-time improvements and yet avoids reliance on lifting. For example, Arya and Chan [START_REF] Arya | Better ε-dependencies for offline approximate nearest neighbor search, Euclidean minimum spanning trees, and ε-kernels[END_REF] have presented improvements to approximate nearest-neighbor searching that do not involve lifting. This raises the hope that generalizations to other norms may be possible. While their focus was different from ours (for example, space-time trade-offs are not considered), their results are inferior to our best bounds. These better bounds arise explicitly from concepts like the Mahler volume, which are only applicable in the context of convex approximation, and hence they rely crucially on lifting. A major challenge is whether it is possible to bypass this intermediate step in order to obtain analogous improvements for approximate nearest neighbor searching.

Acknowledgments

The authors would like to thank the anonymous reviewers for the journal version of the paper for their many insightful comments.

Note Added in Proof

After the original submission of this paper, the authors have discovered a new approach to polytope membership that achieves query time O(log 1 ε ) with storage of only O(1/ε (d-1)/2 ) [START_REF] Arya | Optimal approximate polytope membership[END_REF]. As a consequence, it is possible to answer ε-approximate nearest neighbor queries for a set of n points in O(log n ε ) time with storage of only O(n/ε d/2 ). While these new results surpass the results of this paper theoretically, the data structure presented there involves significantly larger constant factors and lacks the simplicity and practicality of the approach described here. To establish (2), consider the function that maps each point q ∈ S to its closest augmented point (p, h) ∈ ∂K, where h is chosen to be orthogonal to the line segment pq. This function is a bijection (in fact, a homeomorphism) from the points of S to the augmented points of ∂K. This function induces a 1-1 correspondence between the set of ε-dual caps of K (in fact, any set of surface patches) and the Voronoi patches associated with these dual caps. Therefore, (X 2 , R 2 ) and (X 1 , R 1 ) have the same VC-dimension.

To establish (3) and ( 4), observe that each range from (X 3 , R 3 ) (resp., (X 4 , R 4 )) results from intersecting a range of (X 1 , R 1 ) (resp., (X 2 , R 2 )) and a Euclidean ball. It is well known (see, e.g., [START_REF] Matoušek | Lectures on Discrete Geometry[END_REF]) that a range space that results by taking the intersection of ranges from two range spaces of constant VC-dimension has itself constant VC-dimension. Proof : Consider a d-dimensional ball B of radius ∆/4, and let P be any polytope that is an outer εapproximation of B, that is, B ⊆ P ⊆ B ⊕ε. Since ε ≤ ∆/4, P is of diameter at most diam(B)+2ε ≤ ∆. We will show that P satisfies the conditions of the lemma.

Since the Hausdorff distance is a metric, it follows from the triangle inequality that any polytope P that is an ε-approximation of P is a 2ε-approximation of B. To complete the proof, it suffices to show that any 2ε-approximation of B has at least the desired number of facets. To do this, define δ = 4 √ ∆ε, and let Σ denote a set of points on ∂B such that the distance between any two points of Σ is at least δ. By a simple packing argument, for a suitable constant c b there exists such a set of size at least c b ∆/ √ ∆ε d-1 = c b (∆/ε) (d-1)/2 . It is easy to see that the function that maps each point of ∂P to its closest point on ∂B induces a 1-1 correspondence between these two sets. Let Σ be the points corresponding to Σ on ∂P . We assert that the points of Σ lie on distinct facets of P . To see this, suppose to the contrary that two points x, y ∈ Σ were on the same facet of P (see Figure 27). Then the line segment xy lies on ∂P . Because P is a (2ε)-approximation of B, x and y are both within distance ∆/4 + 2ε of B's center. Therefore, by the Pythagorean theorem and the fact that ε ≤ ∆/4, it follows that the distance from the midpoint of the line segment xy to B's center is at most Since q = q + u and by definition of ε , we have T (q ) = T (q + u) = ε q d + u d (q + u) = q d 2(q d + u d )

ε q d • q + ε q d + u d • u = 1 2(1 + u d /q d ) T (q) + ε q d + u d • u.
Since u = ε , we have -ε ≤ u d ≤ ε , and since q ∈ ∂K, we have q d ≥ ε. It follows that

1 3 ≤ 1 2(1 + u d /q d ) ≤ 1 and 0 ≤ ε q d + u d ≤ 1.
Therefore, for some scalars 1 3 ≤ α ≤ 1 and 0 ≤ α ≤ 1, we have v = T (q ) = α T (q) + α u = α v + α u.

Since u ≤ ε and α ≤ 1, it follows that v lies within distance ε of α v, which establishes claim (i).

To establish claim (ii), observe that because v ∈ Γ δ it lies within distance δ of the origin on h (namely, p ). Therefore, α v lies within distance δ + ε of the origin on h (namely, p). Since ε = ε/2 ≤ 1/16 and δ = δ/ √ 2 = ε/2, it is easy to verify that δ + ε ≤ δ. Since p is the origin, this implies that α v ≤ δ which establishes claim (ii) and completes the proof. Lemma 10.7. Given the preconditions of Lemma 10.1(ii) and r = ε /8, we have area(Vor(D δ )∩S) ≥ area(polar r (Γ δ )).

Proof : We begin by showing that Γ δ contains a (d -1)-dimensional Euclidean ball (centered at p ) of radius ε / √ 3. To see this, observe that because K = K ⊕ ε , K contains a ball B of radius ε that has p on its boundary (see Figure 31(a)). By similar triangles it is easy to show that the hyperplane h intersects the "ice cream cone" shaped structure conv(B ∪ {p ε }) in a (d -1)-dimensional Euclidean ball of radius ε / √ 3. This ball clearly lies within the unrestricted dual base, and since δ = √ ε < 1, we have ε / √ 3 < (δ ) 2 < δ , and so this ball also lies within the restricted dual base, Γ δ . For any y ≥ 1, recall that H (y) is the hyperplane that is parallel to h and at distance y below h. Let H = H (1+ε ) denote the hyperplane that is at unit distance below p . Let p denote the vertical projection of p onto H . Recall that we endow h and H with parallel coordinate frames with origins at p and p , respectively. As a consequence of the above observation, for each vector v of length ε / √ 3 in R d-1 , there is a halfspace bounding polar r (Γ δ ) that is orthogonal to v and lies at distance (ε /8)/ v = (ε /8)/(ε / √ 3) = √ 3/8 < 1 from the origin. Thus, polar r (Γ δ ) (when viewed as a subset of H ) is contained within a (d -1)-dimensional unit ball centered at p (see Figure 31(b)).

Let C denote the semi-infinite generalized cylinder whose horizontal cross section is polar r (Γ δ ), whose upper surface lies on H , and which extends vertically downwards (see Figure 31(b)). Lemma 10.2 (applied now to K , ε , polar r (Γ δ ) and Vor(D δ ) ∩ H ) implies that polar r (Γ δ ) ⊆ Vor(D δ ) ∩ H . Since this applies not only to H but to any hyperplane lying below H , it follows that C ⊆ Vor(D δ ).

We will show that the orthogonal projection of S ∩ C onto H is equal to polar r (Γ δ ). It suffices to show that the base of C (which lies on H ) lies entirely within S. We can express any point q on C's base as the sum of two perpendicular vectors q x + q y , where q x is horizontal and q y is vertical. Since p lies within unit distance of the origin, p lies below p at distance ε = ε 2 ≤ 1 16 , and H lies at unit distance below p , we have q y ≤ 1 + 1 16 + 1 = 2 + 1 16 . As observed above, every point of polar r (Γ δ ) lies within unit distance of p , and since p lies within unit distance of the origin, we have q x ≤ 1 + 1 = 2. Therefore, the squared distance from q to the origin is

q x 2 + q y 2 ≤ 2 + 1 16 2 + 2 2 < 9,
which implies that q lies within the sphere S of radius 3. Therefore, C's base lies entirely within S.

Since S ∩ C ⊆ Vor(D δ ) ∩ S, and since the area of the orthogonal projection of a set cannot be larger than the area of the original set, we have area(Vor(D δ ) ∩ S) ≥ area(S ∩ C) ≥ area(polar r (Γ δ )), as desired.

Figure 1 :

 1 Figure 1: Approximate polytope membership: (a) problem formulation, (b) outer ε-approximation.

Figure 2 :

 2 Figure 2: The multiplicative factors in the exponent of the 1/ε terms for (a) polytope membership queries and (b) approximate nearest neighbor (ANN) queries. Each point (x, y) represents a term of 1/ε x(d ± O(1)) for storage and 1/ε y(d ± O(1)) for query time, where the O(1) term does not depend on d.

Figure 5 :

 5 Figure 5: The ε-approximations of (a) Dudley and (b) Bentley et al., and (c) the simple trade-off. (Not drawn to scale.)

Figure 6 :

 6 Figure 6: (a) Cases arising in SplitReduce for t = 2 and (b) the final subdivision.

SFigure 7 :

 7 Figure 7: Lemma 4.2.

Figure 8 :

 8 Figure 8: Lemma 4.3. (Not drawn to scale.)

Figure 9 :

 9 Figure 9: (a) Dual caps, (b) restricted dual caps, and (c) the Voronoi patch of a dual cap.

Figure 11 :Lemma 7 . 1 .

 1171 Figure 11: A polytope in γ-canonical position.

Figure 12 :

 12 Figure 12: (a) The extent measure w u (S) and (b) a coreset.

Figure 13 :

 13 Figure 13: Proof of Lemma 7.2. (Not drawn to scale.)Clearly, T (K) ⊆ K and |H | = O 1/ε (d-1)/2. We assert that the Hausdorff distance between T (K) and K is at most ε/2d √ d. To prove this, we apply an observation due to Chan[START_REF] Chan | Faster core-set constructions and data-stream algorithms in fixed dimensions[END_REF]. Define the one-sided extent measure, denoted w u (S) to be max p∈S p, u . (This is the distance from the origin to S's closest supporting hyperplane orthogonal to and on the same side as u.) In Observation 1.4 of[START_REF] Chan | Faster core-set constructions and data-stream algorithms in fixed dimensions[END_REF] Chan shows that if S is an ε -coreset for the extent measure, then w u (S ) ≥ w u (S)ε • w u (S). Given the nesting properties of S and the fact that u is a unit vector we have

Figure 14 :

 14 Figure 14: Proof of Lemma 7.3.

Figure 15 :

 15 Figure 15: Proof of Lemma 7.5.

  the resulting set is of size O(1/ε d ), and hence it can be computed in time O(1/ε d ) • |H| = O(n/ε d ), by testing each grid point against each halfspace of H. Because γ ≤ 1, we have δ ≤ ε/4.

Figure 16 :

 16 Figure 16: Lemma 8.2 for d = 3 and k = 2.

Figure 17 :

 17 Figure 17: Approximate nearest neighbor searching: (a) Lemma 9.1 (black points are members of R Q ), (b) the lifting transformation. (Note that the figure is not drawn to scale, and the paraboloid in (b) has been translated to aid legibility.)

Figure 18 :

 18 Figure 18: Proof of Lemma 9.2. (Not drawn to scale.)

Figure 20 :

 20 Figure 20: Definitions of h(p), H (y) (p) and S.

Figure 22 :

 22 Figure 22: The relationship between Vor(D δ ) ∩ H and the polar of Γ δ .

Figure 23 :

 23 Figure 23: The reduction to the plane Φ.

Figure 25 :

 25 Figure 25: Proof of Lemma 10.6.

Lemma 10 . 7 . 16 d- 1 • 2 d- 1 . 16 d- 1 •

 10716121161 Given the preconditions of Lemma 10.1(ii) and r = ε /8, we have area(Vor(D δ )∩S) ≥ area(polar r (Γ δ )).We are now ready to prove Lemma 10.1(ii). Recall that r = ε /8. By Lemmas 10.6 and 10.7, we have area(Vor(D δ ) ∩ S) ≥ area(Vor(D δ ) ∩ S) ≥ area(polar r (Γ δ )).As observed earlier, polar r (Γ δ ) is a scaled copy of polar(Γ δ ) by a factor of (r ) 2 = ε /8 = ε/16, and therefore (since these are (d -1)-dimensional bodies) we have area(Vor(D δ ) ∩ S) ≥ ε area(polar(Γ δ )).By Lemma 10.4, area(D δ ) ≥ area(Γ δ )/2 d-1 . Also, by Lemma 10.5 there is a constant c (depending on the fatness parameter γ and d) such that area(Γ δ ) ≤ c • area(Γ δ ). Therefore, we havearea(D δ ) ≥ area(Γ δ ) 2 d-1 ≥ area(Γ δ ) c •Combining these, we obtainarea(D δ ) • area(Vor(D δ ) ∩ S) ≥ area(Γ δ ) c • 2 d-1 • ε area(polar(Γ δ )) δ ) • area(polar(Γ δ )).By applying Lemma 2.2 (in R d-1 ) to Γ δ , there exists a constant c m (depending on d) such that area(Γ δ ) • area(polar(Γ δ )) ≥ c m .Therefore, we have area(D δ ) • area(Vor(D δ ) ∩ S)

Figure 26 :

 26 Figure 26: Proof of Lemma 5.3.

Lemma 8 . 1 .

 81 Let ε and ∆ be real parameters, where 0 < ε ≤ ∆/4. There exists a constant c b and a polytope P in R d of diameter at most ∆ such that any outer ε-approximation of P requires at least c b (∆/ε) (d-1)/2 facets.

  4) 2 + ∆ε + 4ε 2 -4∆ε ≤ (∆/4) 2 -2∆ε < ∆/4.

Figure 31 :

 31 Figure 31: Proof of Lemma 10.7.

  Consider a pair (p, h(p)), where p ∈ ∂K and h(p) is a supporting hyperplane passing through p. Let D denote the √ ε-restricted ε-dual cap whose defining point is p. If K is fat and of diameter at least 2ε, there exists a constant c a (depending only on d) such that if p lies within a unit ball centered at the origin, then area

  Since the line p ε t has slope t θ and t y ≥ 0, we have t x = (t y + ε)/t θ ≥ ε/t θ ≥ δ/ √ 8. We consider two subcases. If w x > t x , then we havew x + w θ > t x ≥ δ/ √ 8 ≥ v x ,as desired. On the other hand, if w x ≤ t x , then w is inside the unrestricted cap D. Since by our hypothesis, w is not in the restricted cap, it must be that w / ∈ B δ , that is, w 2

	8)/8 = δ/ √ 8.

x + w 2 y > δ

2

. By Lemma 10.3(i), we have w x ≥ w y . Therefore, 2w 2

x ≥ w 2 x + w 2 y > δ 2 , which implies that w x > δ/ √ 2. Therefore, w x + w θ ≥ w x > δ/ √ 2 > v x , as desired.

Throughout, we use O(•) and Ω(•) as variants of O(•) and Ω(•), respectively, that ignore logarithmic factors. We use "lg" to denote base-2 logarithm.

If we wished to we could implement access primitive (i) in linear time by linear programming. Also, by testing the membership of each of Q's vertices in K, we could implement a stronger version of access primitive (ii), namely that of determining whether Q ⊆ K (as opposed to K ⊕ ε).

-1 2α ) ,

This lemma holds generally for any δ ≥ √ ε, but it suffices for our purposes to consider the restricted case of δ = √ ε. Note that the additional assumptions on fatness and diameter of part (ii) are necessary for establishing a lower bound. If K is not fat or not of sufficiently large diameter, then area(D δ (p)) can

† Research supported by the Research Grants Council of Hong Kong, China under project numbers 610108 and 16200014. ‡ Research supported by CNPq and FAPERJ grants. § Research supported by NSF grant CCF-1618866.

1

be arbitrarily small. Since the Dudley hypersphere is bounded, it would not be possible to establish any lower bound on the product of their areas. The remainder of this section is devoted to proving this lemma. Because p will be fixed throughout, in order to simplify the notation, we will drop references to p. For example, we will use h, H (y) , D δ , Γ δ , and B δ in place of h(p), H (y) (p), D δ (p), Γ δ (p), and B δ (p), respectively.

Since it will be useful to relate sets on h with sets on H (y) , we observe that each of these hyperplanes can be consistently identified with R d-1 by endowing them with parallel coordinate frames, one centered at p (for h) and one centered at p's orthogonal projection onto H (y) . Thus, a point on h and its vertical projection onto H (y) have the same coordinates.

We start by proving Lemma 10.1(i). Since the value of y will be fixed throughout this part of the proof, we refer to H (y) simply as H. Let p denote the origin of H's coordinate system (the vertical projection of p onto H). (See Figure 20.) In order to exploit Lemma 2.2 on the Mahler volume, rather than considering Vor(D δ ) ∩ H directly, we will find it convenient to instead analyze the polar dual of the base Γ δ . Using the aforementioned coordinate frame, we can think of Γ δ as a body in R d-1 . For r = ε/8, consider the generalized polar of the dual base, polar r (Γ δ ), which we can think of as a convex subset of H. Because Γ δ contains the origin of h (namely, p), it follows directly that polar r (Γ δ ) is bounded, convex, and also contains the origin of H (namely, p ). In order to obtain a lower bound on area(Vor(D δ ) ∩ H), we will first show that polar r (Γ δ ) is a subset of Vor(D δ ) ∩ H and then derive a lower bound on area(polar r (Γ δ )). The first assertion is established by the following lemma. Lemma 10.2. Given the preconditions of Lemma 10.1 and r = ε/8, we have polar

The proof is rather technical and involves a reduction to the problem in 2-dimensional space. Before giving the proof, it will help to provide some intuition regarding the relationship between Vor(D δ ) ∩ H and the polar of Γ δ .

For the sake of simplicity, let us consider just the 2-dimensional setting. Let t denote a point of tangency on ∂K with respect to p ε (see Figure 22), and let v be the intersection of the line segment p ε t with h. Shoot a ray from t perpendicular to ∂K until it intersects H. Let q denote this intersection point. Since K is convex, all the points on the segment p q have their nearest neighbor on the portion of ∂K between p and t, that is, they all lie within Vor(D). Observe that if we translate this perpendicular line so that it emanates from p ε instead of t, it will hit H at a point q that is closer to p . Therefore, the segment p q also lies within Vor(D). Let denote the distance between p ε and p . By similar For the second case, assume that t θ > δ √ 8. In this case v x = t θ /8. As before, we consider two subcases. If w x > t x , then by convexity w θ ≥ t θ , and so w x + w θ ≥ t θ > v x , as desired. On the other hand, if w x ≤ t x , then since w lies within the unrestricted cap, we may infer that w / ∈ B δ . By Lemma 10.3(ii), we have w y /w x ≥ t θ /2. Because the support line at w passes below the origin, we also have w θ ≥ w y /w x . Therefore w x + w θ ≥ w y /w x ≥ t θ /2 > v x . This completes the proof of Lemma 10.2.

Because it is easier to deal with flat objects than curved ones, before returning to the proof of Lemma 10.1(i), we show that the area of the restricted dual cap is, up to a constant factor, bounded below by the area of its base. This result is straightforward for unrestricted caps, since it is easy to show that the base is contained within the orthogonal projection of the dual cap onto h. However, restriction complicates the analysis. The proof involves a technical geometric argument and is presented in the appendix.

Lemma 10.4. Given the preconditions of Lemma 10.1, it follows that area(D δ ) ≥ area(Γ δ )/2 d-1 .

We are now ready to prove Lemma 10.1(i). Recall that r = ε/8. As observed earlier, polar r (Γ δ ) is a scaled copy of polar(Γ δ ) by a factor of r 2 , and therefore (since these are (d -1)-dimensional bodies) we have area(polar r (Γ δ )) = r 2(d-1) • area(polar(Γ δ )). By applying Lemma 10.2, we have

By Lemma 10.4, area(D δ ) ≥ area(Γ δ )/2 d-1 , and therefore

area(Γ δ ) • area(polar(Γ δ )).

We now apply the Mahler-volume bound. By Lemma 2.2 (in R d-1 ), there exists a constant c m (depending only on d) such that area

.

Selecting any c a ≤ c m /16 d-1 establishes Lemma 10.1(i).

Next, let us establish Lemma 10.1(ii). Recall that we assume that K is fat and of diameter at least 2ε. In particular, let us assume that K is γ-fat, where γ is a constant independent of n and ε that lies in the interval (0, 1]. (As a result of Lemma 2.1, we may assume that γ is 1/d when applying this result.)

It is natural to try to generalize the approach used in part (i). First, we would show that

and then we would apply the Mahler-volume bound to yield a lower bound on the product area(Γ δ ) • area(polar(Γ δ )). A problem arises, however, if K is not smooth. In particular, if some portion of the boundary of K in p's vicinity is nearly vertical, then the boundary of Γ δ can be arbitrarily close to the origin (namely p), implying that polar(Γ δ ) cannot be bounded, and hence its area can be arbitrarily large. This was not an issue in part (i), because H is also unbounded. But since S is bounded, area(Vor(D δ )∩S) cannot be arbitrarily large. We will remedy this by smoothing K by taking its Minkowski sum with a small Euclidean ball of radius O(ε). We shall see (in the proof of Lemma 10.7) that this allows us to constrain the area of polar(Γ δ ). This smoothing operation requires us to adapt many of the prior results of this section to this new context.

To construct the smoothed body, for the remainder of this section define ε = ε/2, and let K = K ⊕ε (see Figure 24(a)). Recall that h denotes the supporting hyperplane at p and p ε is the point at distance ε from p in the direction orthogonal to h. As before, for the sake of illustration, let us assume that p ε is vertically below p. Let p be the midpoint of the segment pp ε . Clearly, p ∈ ∂K , and the parallel hyperplane h passing through p is a supporting hyperplane for K .

(a) Let us also define the dual base in this smoothed context. Define Γ to be the intersection of h and conv(K ∪ {p ε }). Let δ = √ ε = δ/ √ 2, and define the restricted base Γ δ to be the intersection of Γ and a ball of radius δ centered at p (see Figure 24(b)). Our analysis will be based on K and Γ δ , as opposed to K and Γ δ . Our first objective will be to show that the area of Γ δ is not significantly larger than that of Γ δ . As before, we endow h and h with parallel coordinate frames whose origins are located at p and p , respectively. Then we can think of Γ δ and Γ δ as convex sets in R d-1 . The following lemma relates these two bodies. Lemma 10.5. Given a convex body K that is γ-fat and of diameter at least 2ε and given Γ δ and Γ δ as defined above, there exists a constant c (depending on γ and the dimension d)

The proof is rather technical, but it involves simple geometric reasoning. It is given in the appendix. Recall that Vor(D δ ) ∩ S consists of the set of points on the sphere S whose closest point on ∂K lies within the restricted dual cap D δ . Let D δ denote the corresponding restricted dual cap for K , that is, the set of points of ∂K that are visible from p ε and lie within the ball B δ (p ). Our analysis will be based on establishing a lower bound on the area of Vor(D δ ) ∩ S. The following lemma shows that this will provide a lower bound on the area of Vor(D δ ) ∩ S.

Lemma 10.6. Given the preconditions of Lemma 10.1(ii), area(Vor(D δ ) ∩ S) ≤ area(Vor(D δ ) ∩ S).

Proof : We will prove the stronger result that Vor(D δ ) ∩ S ⊆ Vor(D δ ) ∩ S. We begin by observing that both D δ and D δ lie within the ball bounded by the Dudley hypersphere S. To see this, recall that A Omitted Proofs Lemma 5.3. Let K be a convex body in R d that lies within Q 0 , and let ε and δ be positive real parameters. The following range spaces (X i , R i ) have constant VC-dimension (where the constant depends only on d):

(1) X 1 = ∂K and R 1 is the set of ε-dual caps.

(2) X 2 = S and R 2 is the set of Voronoi patches of the ε-dual caps.

(3) X 3 = ∂K and R 3 is the set of δ-restricted ε-dual caps. (4) X 4 = S and R 4 is the set of Voronoi patches of the δ-restricted ε-dual caps.

Proof : We may assume that K contains the origin, since this clearly does not affect the VC-dimension of these range spaces. To prove (1), consider the set of augmented points (p, h) ∈ ∂K (recalling that h is any supporting hyperplane passing through p). Under the polar transformation (recall Section 2.3), these supporting hyperplanes are mapped to a set of points that form the boundary of polar(K), which is a convex body. Consider any point q that is external to K (see Figure 26(a)). If we treat q as a vector, polar(q) is a hyperplane that intersects polar(K) (see Figure 26(b)).

Consider the cap of polar(K) induced by polar(q), which we define to be the points of the boundary of polar(K) that are separated from the origin by polar(q). By the inclusion-reversing properties of the polar, the points of this cap are in 1-1 correspondence with the supporting hyperplanes of K that separate q from K. It follows that the set of dual caps of K is equivalent, through polarity, to the set of caps of polar(K). The range space of caps is equivalent to the range space of halfspaces, which is known to have constant VC-dimension, and therefore the VC-dimension of dual caps is equal. This implies that the line segment xy intersects B's interior, which contradicts the hypothesis that P is an outer approximation. Therefore, P must have at least |Σ | ≥ c b (∆/ε) (d-1)/2 facets, and this completes the proof.

Lemma 10.3. Given the preconditions of Lemma 10.1 and the aforementioned 2-dimensional reduction, and given w and t as introduced above, where w x ≤ t x and w / ∈ B δ :

Proof : To prove part (i), observe first that, by the preconditions of Lemma 10.1, δ = √ ε and ε ≤ 1/8, and so δ √ 8 ≤ 1. Since the supporting line passing through t passes on or below the origin, we have t y /t x ≤ t θ . (It may be helpful to refer to Figure 23.) Since w x ≤ t x , by convexity we have w y /w x ≤ t y /t x . Combining this, we have w y /w x ≤ t θ ≤ δ √ 8 ≤ 1, as desired. To prove part (ii), observe that because t is a point of tangency with respect to p ε , w lies on or above the line p ε t. This implies that w y ≥ -ε + t θ w x . Since t θ is positive, w x ≤ (w y + ε)/t θ . Because w / ∈ B δ , we know that w 2

x + w 2 y > δ 2 , which implies that max(w x , w y )

By our bound on t θ , we have δ √ 2 < t θ /2, implying that w y /w x > t θt θ /2 = t θ /2, as desired. On the other hand, if w y > δ/ √ 2, then

The definition of δ and our bounds on ε imply that 1 + δ √ 2 < 2, and so w y /w x ≥ t θ /2, which completes the proof of (ii).

Lemma 10.4. Given the preconditions of Lemma 10.1, it follows that area(D δ ) ≥ area(Γ δ )/2 d-1 .

Proof : Let D ↓ δ denote the orthogonal projection of D δ onto h. Since the area of the orthogonal projection of a set cannot exceed the area of the original set, area(D ↓ δ ) ≤ area(D δ ). Given a set X in real space, let 1 2 X denote the set {v/2 : v ∈ X}. We assert that 1 2 Γ δ ⊆ D ↓ δ (using the aforementioned coordinate system on h whose origin is at p). Since Γ δ lies in R d-1 , from this assertion we will have

from which the result will follow. It remains to prove the assertion. Consider any v ∈ Γ δ , and recall that B δ denotes the ball of radius δ = √ ε centered at p. By definition of Γ δ , v ∈ B δ , and so v x ≤ δ. It suffices to show that v/2 ∈ D ↓ δ , that is, there exists a point w ∈ D δ whose projection onto h is v/2. Note that this is trivially true if v = p, and so we may assume that v = p. Under this assumption, consider the unique plane Φ defined by the points p, p ε , and v. We will impose the same coordinate system on Φ as in the proof of Lemma 10.2, with p as origin and p ε on the negative y-axis. Henceforth, we restrict our attention to this plane.

We may assume by symmetry that v lies in the positive x-halfplane. By definition of Γ δ , there exists a point t on the lower surface of ∂K such that the line segment p ε t passes through v. Let w be the point of ∂K whose orthogonal projection onto h equals v (see Figure 28). Note that w exists along the portion of ∂K ∩ Φ between p and t, and therefore 0 < w x ≤ t x . Recall that w θ and t θ denote the slopes of the support lines at w and t, respectively. By basic properties of convexity, we have w y /w x ≤ w θ ≤ t θ . We consider two cases, based on the location of w. First, if w B δ , then w ∈ D δ (see Figure 28(a)). This implies that v ∈ D ↓ δ . Clearly, D ↓ δ is star-shaped with respect to p, and therefore v/2 ∈ D ↓ δ . On the other hand, if w / ∈ B δ , then w 2 x + w 2 y > δ 2 (see Figure 28(b)). Because v lies on the line p ε t, we have v y = -ε + t θ v x . Also, since v x = w x and v y = 0, we have t θ w x = ε. Combined with the fact that w y /w x ≤ t θ , this yields w y ≤ ε. Let w be the point of ∂K whose orthogonal projection onto h is v/2. By convexity, we have w y ≤ w y ≤ ε and w

8 , we also have ε 2 ≤ δ 2 /8. Thus, we obtain

and therefore w ∈ B δ , which implies that v/2 ∈ D ↓ δ , as desired.

Lemma 10.5. Given a convex body K that is γ-fat and of diameter at least 2ε and given Γ δ and Γ δ as defined above, there exists a constant c (depending on γ and the dimension d) such that area(Γ δ ) ≤ c • area(Γ δ ).

Proof : Recall that ε = ε/2. The proof is based on two assertions:

(1) Γ δ contains a (d -1)-dimensional Euclidean ball of radius ε γ/2.

(2) Γ δ ⊆ Γ δ ⊕ ε (treating Γ δ and Γ δ as subsets of R d-1 ).

To see why this suffices, observe that by ( 1), if we scale Γ δ by a factor of 1 + 2/γ about the center of this ball, the scaled copy contains Γ δ ⊕ ε . (To see why, observe that each supporting hyperplane of the original body is at distance at least ε γ/2 from the ball's center, and so the scaled body has a parallel supporting hyperplane at distance at least (ε γ/2)(2/γ) = ε from the original supporting hyperplane.) Scaling increases Γ δ 's area by a factor of (1 + 2/γ) d-1 . By (2), Γ δ is contained within this scaled copy, and therefore its area cannot be larger. The result follows by setting c = (1 + 2/γ) d-1 . We first prove assertion [START_REF] Agarwal | Approximating extent measures of points[END_REF]. Our approach will be to show that K contains a ball that is sufficiently large and sufficiently close to p that it contributes a ball of the desired radius to Γ δ . Since K is γ-fat, there exist two concentric balls, B -and B + , whose radii differ by a factor of γ such that B -⊆ K ⊆ B + (see Figure 29(a)). Let r and r/γ denote the radii of B -and B + , respectively, and let y denote the distance of their common center to h. B -is the natural candidate for the desired ball, but it may be too far from p to contribute to Γ δ (due to restriction). Since diam(K) ≥ 2ε, K does not lie entirely within a ball of radius ε centered at p. Let us scale space uniformly about p so that K just barely fits within this ball. Call the scaled body K 0 , and let B - 0 and B + 0 denote the scaled copies of B -and B + , respectively (see Figure 29(b)). We will show that B - 0 is the desired ball. Since the scale factor is not greater than unity, B - 0 ⊆ K 0 ⊆ K. Let r 0 denote the radius of B - 0 , and let y 0 denote its center's distance to h. Because the center of B -lies within K, we have

which implies that y/r ≤ 2/γ. Because the scaling is uniform, it follows that y 0 /r 0 = y/r ≤ 2/γ.

Another consequence of scaling is that

which implies that ε/r 0 ≤ 2/γ. Let Z denote the (d-1)-dimensional horizontal diametrical disk of radius r 0 that lies within B - 0 (see Figure 29(b)). It is easy to verify that if we project Z centrally towards p ε onto h, the result is a (d -1)-dimensional ball of radius r = r 0 ε/(y 0 + ε), which we denote by Z . Clearly Z lies within the unrestricted dual-cap base. As a result of scaling, both Z and Z lie within a ball of radius ε centered at p. Since ε < 1, we have δ > ε, and therefore Z lies within the restricted base, that is Z ⊆ Γ δ . By the above inequalities, the radius of Z is

which establishes assertion (1). Next, we prove assertion (2). Consider any point v ∈ Γ δ . By definition of Γ δ (and thinking of v as a vector in R d ), v is naturally associated with a point q ∈ ∂K by shooting a ray from p ε through v until it hits ∂K (see Figure 30). Since K = K ⊕ ε , there exists a unique point q ∈ ∂K that is at distance ε from q . Let u ∈ R d denote the vector qq. Similarly, q is associated with a point v located where the line segment qp ε intersects h. (The point v lies on the base of the unrestricted dual cap Γ, but not necessarily on the restricted base Γ δ .)

Now, thinking of v and v as vectors in R d-1 , we claim (i) that there exists a scalar 0 ≤ α ≤ 1 such that v lies within distance ε of α v, and (ii) α v is of length at most δ. From (i) and the fact that Γ is star-shaped with respect to the origin (namely p) it follows that α v ∈ Γ. From (ii), we have α v ∈ Γ δ . From these two claims we conclude that each point v ∈ Γ δ is within distance ε of a point in Γ δ , which implies assertion [START_REF] Agarwal | Geometric approximation via coresets[END_REF]. The remainder of the proof involves proving these two claims. To establish claim (i), let us consider a coordinate frame whose origin is p ε , whose dth coordinate axis points vertically upwards, and whose d -1 coordinate vectors are taken from h's coordinate frame. We may express any point q ∈ R d as a pair (q, q d ), where q ∈ R d-1 and q d is the vertical distance from p ε to q. Define the transformation T : R d → R d-1 that projects a point q ∈ R d centrally towards p ε until it intersects h. Also define an analogous transformation T that projects a point q onto h . It is easy to verify that T (q) = ε q d • q and T (q ) = ε q d • q .