Abstract Let P be a set of n points in R d . A point p ∈ P is k-shallow if it lies in a halfspace which contains at most k points of P (including p). We show that if all points of P are k-shallow, then P can be partitioned into Θ(n/k) subsets, so that any hyperplane crosses at most O((n/k) Abstract Given such a partition, we can apply the standard construction of a spanning tree with small crossing number within each subset, to obtain a spanning tree for the point set P , with crossing number Abstract . This allows us to extend the construction of Har-Peled and Sharir [HS11] to three and higher dimensions, to obtain, for any set of n points in R d (without the shallowness assumption), a spanning tree T with small relative crossing number. That is, any hyperplane which contains w ≤ n/2 points of P on one side, crosses O( Abstract Using a similar mechanism, we also obtain a data structure for halfspace range counting, which uses O(n log log n) space (and somewhat higher preprocessing cost), and answers a query in time O(n 1−1/(d−1) k 1/d(d−1) (log(n/k)) O(1) ), where k is the output size. Introduction Background One of the central themes in computational geometry is the design of efficient range searching algorithms. Typically, in such a problem one is given an input set P of n points in d dimensions, and the goal is to preprocess P into a data structure, so that for any query range of some type (say, a halfspace H), one can efficiently count, report, or test for emptiness the set P ∩ H. A significant component of most of these algorithms involves space decomposition techniques, which partition the input set into subsets with some useful structure. Background Apart from range searching, partitions are also used in constructions of spanning trees with small crossing number, approximations, ε-nets, and in several other computational geometry problems. Background In a typical approach (see, e.g., [Mat92a] ), given a point set P in R d , one partitions P into subsets of approximately equal sizes, so that each of them is contained within some region of constant description complexity (e.g., simplices). We remark that the subsets are pairwise disjoint, while the containing regions might have nonempty intersections. We seek partitions with small crossing number, meaning that the maximum number of enclosing regions crossed by the boundary of a range (typically, a hyperplane) is small. Background In this paper, we consider a variant of the partition paradigm, referred to as a partition of a shallow point set, which is applied to a set P of shallow points in R d , where a point p ∈ P is k-shallow if there exists a hyperplane h that contains at most k points of P , including p, on one of its sides. We will construct a partition whose crossing number, namely, the maximum number of its simplices that can be crossed by a hyperplane, depends, in addition to n, also on the shallowness of P , i.e., on the maximum shallowness k of its points. Background As is typical in computational geometry, we consider the dimension d as a fixed (small) constant, thus factors depending only on d will be regarded as constants. Background Cuttings. One of the major ingredients of our partitioning technique is cuttings of arrangements of hyperplanes. A cutting is a collection of (possibly unbounded) d-dimensional closed cells with constant description complexity (e.g., simplices) with pairwise disjoint interiors, which cover the entire R d (or some specified portion thereof). Let H be a collection of n hyperplanes in R d and let Ξ be a cutting of the arrangement A(H). For each simplex ∆ ∈ Ξ, let H ∆ denote the collection of hyperplanes intersecting the interior of ∆. The cutting Ξ is called a (1/r)-cutting for H if |H ∆ | ≤ n/r for every simplex ∆ ∈ Ξ. Background It will sometimes be convenient to work with weighted collections of hyperplanes, where such a collection is a pair (H, w), where H is a collection of hyperplanes, and w : H → R + is a weight function on H. For each L ⊆ H, we write w(L) for h∈L w(h). The notions introduced for unweighted collections of hyperplanes can usually be generalized for weighted collections in an obvious way. For example, a cutting Ξ is a (1/r)-cutting for (H, w) if for every simplex ∆ ∈ Ξ, the collection H ∆ has total weight at most w(H)/r. Background Partitions: related work. Our study extends to higher dimensions the planar construction of a partition of a set of shallow points, recently developed by Har-Peled and Sharir [HS11] . This technique partitions P into O(n/k) subsets, each containing O(k) points and enclosed in a (possible unbounded) triangle, so that the triangles are pairwise disjoint, and the crossing number of this partition (by any line) is only O(log(n/k)). Background Har-Peled and Sharir also constructed a set P of n k-shallow points in R 3 (in fact, P is a set in convex position, so all its points are 1-shallow), so that the (maximum) crossing number of any partition of P into subsets of size Θ(k) is Ω( n/k). See below for a further discussion of this phenomenon, which was the starting point and the motivation for the study presented in this paper. Background We next review the more standard partitioning techniques of Matoušek [Mat92a, Mat92b] . There P is a set of n points in R d , d ≥ 2, which do not have to be shallow. Again, we par-tition P into Θ(n/k) pairwise disjoint subsets, each having between k and 2k points (here 1 < k < n is an arbitrary parameter), enclosed by some simplex, where these simplices might have a nonempty intersection 1 . The partition, referred to as a simplicial partition, has the property, that any hyperplane h crosses at most O((n/k) 1−1/d ) simplices. Background Let P , n and k be as above. Matoušek [Mat92b] has also developed a variant of the partitioning scheme described above, yielding a partition of Θ(n/k) subsets of size between k and 2k, such that any k-shallow hyperplane h (that is, a hyperplane which contains at most k points of P on one side) crosses at most O((n/k) 1−1/⌊d/2⌋ ) simplices of the partition. Background (In contrast, the construction in [HS11] , and the one presented in this paper, deal with sets whose points are shallow, but we seek a small crossing number with respect to every hyperplane.) Background Applications: related work. Let us now review some applications based on the various kinds of partitions mentioned above. Background Halfspace range searching. Matoušek [Mat92a] uses the standard partition recursively to construct an efficient partition tree, whose root stores the entire input set P and a simplicial partition thereof. Each node v of the tree stores a subset P v of P , and a simplicial partition of P v , and each subset of the partition corresponds to a distinct child of v. Overall, the resulting partition tree has linear size, can be constructed in O(n log n) deterministic time, such that, given a query halfspace γ, one can count the number of points in P ∩ γ in O(n 1−1/d log O(1) n) time. Background In a variant of this approach, Matoušek [Mat92b] exploits the partition machinery with respect to shallow hyperplanes to efficiently solve the halfspace range reporting (or emptiness) problem. More specifically, one can construct a data structure of size O(n log log n), in O(n log n) time, such that, given a query halfspace γ, one can report the points in P ∩ γ in O(n 1−1/⌊d/2⌋ log O(1) n + k) time, where k = |P ∩ γ|. Background Another useful application of partitions of sets of shallow points, as described above, is the construction of spanning trees with small relative crossing number. We recall the standard result, due to Chazelle and Welzl [CW89] (see also [Wel92] ), on the existence of spanning trees with small crossing number. That is, given a set P of n points in R d , there exists a straight-edge spanning tree T on P , such any hyperplane crosses at most O(n 1−1/d ) edges of T. Har-Peled and Sharir have refined this construction in the plane, to obtain a spanning tree T that has the following property. Define the weight w l ≤ n/2 of a line l to be the smaller of the two numbers of points of P on each side of l. Then l crosses only O( √ w l log(n/w l )) edges of T; see [HS11] for more details. In this paper, we follow the same machinery to extend the above construction to higher dimensions. Background Relative (p, ε)-approximations. The existence of a spanning tree with small relative crossing number, for a point set P in the plane, as just reviewed, facilitates the construction of relative (p, ε)-approximations for P , with respect to halfplane ranges, whose size is smaller than the one guaranteed by the general theory of Li et al. [LLS01] (see [HS11] ). For given 0 < p, ε < 1, a relative (p, ε)-approximation for P is a subset A ⊆ P with the property that, for each halfspace γ, Background provided that |P ∩ γ|/|P | ≥ p. Given such a spanning tree, we convert it into a spanning path with the same asymptotic crossing number, and generate a matching out of this path by selecting every other edge along it, and apply a "halving technique" on the resulting matching, in which one point of each pair of the matching is drawn independently at random, thus getting rid of half of the points. By the standard theory of discrepancy (see [Cha01] ), the small crossing number of the matching implies a correspondingly low discrepancy of the halving. We repeat this halving procedure until the combined discrepancy first exceeds a given prescribed parameter, and then return the remaining points as the desired approximation. Har-Peled and Sharir [HS11] apply this construction to a planar point set P , and obtain a relative (p, ε)-approximation for P , of size Background For most values of ε and p, this is better than the general bound O( Background . See Section 1.2 below for more details. In this paper, we extend this construction to higher dimensions, using the extension of spanning trees with small relative crossing number to higher dimensions, as mentioned above. Background Our results. We introduce a new variant of the partitioning machinery, based on the general approach that was introduced in [Mat92a] and [Mat92b] , and obtain a partition of a set P of n k-shallow points in R d into Θ(n/k) subsets, each of size between k and 2k, so that each subset is contained within a d-dimensional simplex and so that the crossing number of the partition (the maximum number of simplices crossed by a hyperplane) is at Background , where α(·) is the near-constant inverse Ackermann function. Note that the size of the sets in the partition is roughly the same as the shallowness parameter k, and that the exponent in the bound on the crossing number is smaller than the one provided for the general setup in [Mat92a] . Background We use this partition, as in [HS11] , to construct a spanning tree with small relative, output-sensitive, crossing number. Specifically, any hyperplane h of weight w h (the number of input points on its "lighter" side) crosses at most Background (n/w h )) edges of the resulting spanning tree for d ≥ 3, and O( Background We then extend the planar construction of relative (p, ε)-approximations for points and halfplanes introduced in [HS11] to higher dimensions. We again follow a similar machinery as the one in [HS11] , based on the classical halving technique, to convert a spanning tree with small relative crossing number to a relative (p, ε)-approximation. The properties of the relative (p, ε)-approximation and the exact result are detailed in Section 1.2 below. Background Another application of the shallow-points partition is an exact output-sensitive range counting algorithm for point sets and halfspace ranges in R d . We combine the range reporting algorithm of Matoušek [Mat92b] with our shallow-points partition and the standard simplex range counting algorithm of Matoušek [Mat92a] , to obtain an improved, outputsensitive range counting algorithm, whose running time is Background , where k is the output size. This is an improvement over the previous bound O(n 1−1/d (log n) O(1) ) of [Mat92a] when k ≪ n (although when k is very small, the range reporting of [Mat92b] will be faster). See Section 5.2 for a more precise statement of this result. (One weak aspect of our structure is that, for d ≥ 4 we do not know how to construct it in near-linear time. The current bound on the preprocessing cost is roughly n c d for some exponent c d that depends on d and satisfies 1 < c d < 3/2. See Theorem 5.7 for the precise statement.) Known notions of approximations We recall the result of Li et al. [LLS01] , and two useful extensions of ε-approximations and ε-nets derived from it, which we will exploit later in this paper. Known notions of approximations Let (X, R) be a range space, where X is a set of n objects and R is a collection of subsets of X, called ranges. The measure of a range r ∈ R in X is the quantity Known notions of approximations Assume that (X, R) has finite VC-dimension δ, which is a constant independent of n; see [Mat02] for more details. Known notions of approximations Let 0 < α, ν < 1 be two given parameters. Consider the distance function Known notions of approximations A subset N ⊆ X is called a (ν, α)-sample for (X, R), if for each r ∈ R we have Known notions of approximations is a (ν, α)-sample for (X, R) with probability at least 1 − q, with an appropriate choice of an absolute constant of proportionality. Known notions of approximations Har-Peled and Sharir [HS11] show that, by appropriately choosing α and ν, various standard constructs, such as ε-nets and ε-approximations, are special cases of (ν, α)-samples; thus bounds on the sample sizes that guarantee that the sample will be one of these constructs with high probability are immediately obtained from Theorem 1.1. Two other, less standard special cases of (ν, α)-samples are relative (p, ε)-approximations [HS11] and shallow ε-nets [ShSh11]; we review them next. Known notions of approximations Relative (p, ε)-approximations. Definition 1.2 (Relative (p, ε)-Approximation). Let (X, R) be a range space of finite VCdimension δ. For given parameters 0 < p, ε < 1, a subset N ⊆ X is a relative (p, ε)-approximation for (X, R) if, for each r ∈ R, we have Known notions of approximations The following result shows that a relative (p, ε)-approximation is a special case of a (ν, α)-sample. δ log 1 p + log 1 q elements of X, for an appropriate absolute constant c 1 , is a relative (p, ε)-approximation for (X, R) with probability at least 1 − q. Known notions of approximations Shallow ε-nets. Let (X, R) be a range space of finite VC-dimension δ, and let 0 < ε < 1 be a given parameter. A subset N ⊆ X is a shallow ε-net if it satisfies the following two properties, for some constant c that depends on δ. Known notions of approximations (i) For each r ∈ R and for any parameter t ≥ 0, if |N ∩r| ≤ t log 1 ε then |X∩r| ≤ c(t+1)ε|X|. (ii) For each r ∈ R and for any parameter t ≥ 0, if |X∩r| ≤ tε|X| then |N ∩r| ≤ c(t+1) log 1 ε . Known notions of approximations Note the difference between shallow and standard ε-nets: Property (i) (with t = 0) implies that a shallow ε-net is also a standard ε-net (possibly with a re-calibration of ε). Property (ii) has no parallel in the case of standard ε-nets -there is no guarantee how a standard ε-net interacts with small ranges. δ log 1 ε + log 1 q elements of X, for an appropriate absolute constant c ′ 1 , is a shallow ε-net with probability at least 1 − q. Known notions of approximations A brief overview of the analysis. The paper is structured as follows. In Section 2 we derive a technical result that shows that, informally, a random sample Z of Θ(n/k) points from a k-shallow n-point set in R d has, with some constant positive probability, the property that at least some fixed fraction of its points are vertices of its convex hull. (Curiously, this fraction cannot exceed 1/e ≈ 0.368 in the worst case.) We plug this result into the analysis in Section 3, which presents a construction of a (1/r)-cutting of the zone of the boundary of a convex set in an arrangement of hyperplanes in R d . This construction is an easy adaption of standard constructions of cuttings, but seems not to have been presented so far in the literature. Armed with this construct, we present in Section 4 the main technical contribution of the paper, which is a construction of a simplicial partition of a set of shallow points in R d that has a small crossing number (with respect to any hyperplane). The construction is not general, in the sense that the size of the subsets in the partition has to be equal to (or proportional to) the shallowness parameter k. Still, this provides the key tool for the applications in Section 5, which, as mentioned above, are (i) a construction of a spanning tree with small relative crossing number, (ii) a construction of relative (p, ε)-approximations for halfspace ranges in R d , whose size (in many cases) is smaller than the halfspace general bound in [LLS01, HS11] , and (iii) an output-sensitive halfspace range searching data structure. Known notions of approximations 2 Sampling from a k-shallow set Let P be a set of n points in R d , for d ≥ 2, so that all its points are k-shallow, for some fixed parameter 1 ≤ k ≤ n. Known notions of approximations Let Z be a random sample of P where each point of P is chosen in Z independently with probability p = 1/k. Let Y ⊆ Z be the set of 1-shallow points of Z (with respect to Z), i.e., Y is the set of vertices of the convex hull Conv(Z). Let us assume from now on that k ≥ 2, unless explicitly noted otherwise. Known notions of approximations In what follows, we assume that P is in general position. In particular, no d+ 1 points of P lie in a common hyperplane, and no d lie in a common vertical hyperplane (i.e., parallel to the x d -axis). Consequently, considering the dual set of hyperplanes H = D(P ) (using the duality that preserves the above/below relationship; see, e.g., [Ed87]), we get that H is in general position too, which means that every d hyperplanes of H intersect in a single point, and no d + 1 have a common point. Known notions of approximations The following proposition, although its proof is technical and somewhat involved, asserts a fairly intuitive property of k-shallow sets. That is, if we take a random sample of about n/k points of such a set, at least some fixed fraction of the points of the sample are vertices of its convex hull. As a partial explanation of why the proof is complicated, we observe, after the proof, that the fraction of convex hull vertices of the sample cannot in general be made arbitrarily close to 1. Known notions of approximations Proposition 2.1 Let P , Z, and Y be as above, and assume that k ≤ n 256 . Then, with probability > 0.22, Known notions of approximations Before getting into the proof, let us recall Chernoff's bound (see, e.g., [AS92] , Appendix A, Theorems A.12 and A.13) for a binomial random variable X with parameters n, p, which we denote by X ∼ B(n, p). That is, X = n i=1 X i , where X 1 , X 2 , . . . , X n are independent random indicator variables, and Pr {X i = 1} = p for each i. Put E[X] = µ = np. Then, for any δ > 0, we have Known notions of approximations Alternatively, we can write it as Known notions of approximations for any t > µ. Another variant of Chernoff's bound, for large deviations below the mean, is Known notions of approximations for any δ > 0. Using (1) and (2), we get the following proposition: Known notions of approximations k ), and let 1 < β ≤ k be a parameter. For y ∈ R, define Known notions of approximations Proof. We have, for t 0 ∈ N, Known notions of approximations We note, that for any y ∈ R, S >y = S ≥⌊y+1⌋ . Hence, substituting t 0 = ⌊ βn k + 1⌋ into the equality above, and using the bound (1), with µ = n k and 1 + δ = β, we get +1⌋ Pr {X > t} . +1⌋ It remains to estimate the second expression. We note that (e 1−a/x )/x is monotonically decreasing in x for 0 < a ≤ x. Hence, using (2), we obtain, for any y > µ, Pr {X > t} ≤ ε(n/k, β) · β β − e 1−1/β , which completes the proof. ✷ Proof of Proposition 2.1. We separately bound from below the probabilities that (i) |Y | ≥ αn k , and (ii) n νk ≤ |Z| ≤ γn k , in terms of α, ν, γ, n and k; the concrete values of α, ν and γ, as given in the proposition, will be substituted later. The probability for both conditions to hold is then estimated using the union bound (on the complementary events). +1⌋ (i) Bounding from below the probability that |Y | ≥ αn k . Put q = Pr |Y | < αn k , and let 1 < β ≤ k be a parameter. We need to bound from below the value of 1 − q. +1⌋ Recalling that Y is the subset of 1-shallow points within Z, and that all the points in the ground set P are k-shallow, we have, for each point a ∈ P , +1⌋ Indeed, as a is a k-shallow point, there exists a hyperplane through a which bounds a halfspace h containing at most k − 1 points of P , excluding a. The lower bound above is the probability that a is chosen in Z and none of the other points in h is chosen. Using linearity of expectation, we thus have +1⌋ We now proceed to estimate q. Note that we cannot apply Chernoff's bound directly, because the events a ∈ Y , for a ∈ P , are not independent. Instead we proceed as follows. Put ε = ε(n/k, β), and s = S > βn k . We then have (assuming that β > α, which will hold for specific values that we will later use) +1⌋ Hence, by applying Proposition 2.2, we have +1⌋ By choosing (somewhat arbitrarily) α = 1 8 , β = 1.2, recalling that we have required that k ≤ n 256 , and using Chernoff's bound (1) to bound ε = ε(n/k, β), we get that Pr |Y | ≥ n 8k > 0.221. +1⌋ (ii) Bounding from below the probability that n νk ≤ |Z| ≤ γn k . Since |Z| ∼ B(n, 1 k ), estimating this probability can be done by a direct application of Chernoff's bounds. As in (4), +1⌋ and by applying (3), we have +1⌋ Choosing γ = 2, ν = 2, and using the assumption that k ≤ n 256 , we get that From (i) and (ii) we obtain that Upper bounds on the probability of a sample with many hull vertices. We can increase the lower bound given in (6), on the probability 1 − q of getting a sample with at least αn k hull vertices, by choosing β close enough to 1 and α close to 0. We then have From (i) and (ii) we obtain that By requiring that n/k is at least some sufficiently large constant (which depends on the choice of β; we need it to "neutralize" the denominator β − e 1−1/β , which tends to 0 as β → 1), we can make this probability arbitrarily close to From (i) and (ii) we obtain that The following construction shows that the bound 1/e is fairly close to being worst-case tight. This construction was provided by Adam Sheffer, and we are grateful to him for this observation. From (i) and (ii) we obtain that The construction is depicted in Figure 1 . It consists of a set A of n points on the unit circle C, sufficiently closely clustered together near the top point of C, and of 2c + 1 sets T , L 1 , . . . , L c , and R 1 , . . . , R c , so that (i) each of these sets consists of points lying on a ray emanating from the center of C, outside C and sufficiently close to it, (ii) each of these sets consists of k points, except for T which consists of k − 1 points, and (iii) the ray containing T points upwards, the rays containing L 1 , . . . , L c point into the third quadrant, and the rays containing R 1 , . . . , R c point into the fourth quadrant. Here c is an additional parameter that we will fix later. (The points are not in convex position but a sufficiently small perturbation of them will place them in general position without affecting the analysis.) From (i) and (ii) we obtain that Altogether, the resulting set P has n ′ = n + (2c + 1)k − 1 points. It is easily verified that the points can be arranged in such a way that each of them is k-shallow. Moreover, with an appropriate layout, the convex hull of a sample Z will have at most 2c + 1 vertices if we choose at least one point of T , at least one point of L 1 ∪ · · · ∪ L c , and at least one point of R 1 ∪ · · · ∪ R c . The probability of this latter event is From (i) and (ii) we obtain that Assuming that n ≫ (2c + 1)k, so that 2c + 1 ≪ n ′ /k, the probability of getting a sample with Θ(n ′ /k) hull vertices, with an appropriate constant of proportionality ensuring that this bound is larger than 2c + 1, is From (i) and (ii) we obtain that which we can make arbitrarily close to From (i) and (ii) we obtain that by choosing c sufficiently large. This shows that e −1 is an upper bound on the probability that we can guarantee for getting a sample with Θ(n/k) hull vertices from a set of n kshallow points (when n is sufficiently large). As noted above, we can get arbitrarily close to this bound by requiring k/n to be sufficiently small. From (i) and (ii) we obtain that Figure 1: Construction of a k-shallow point set with large probability for a sample with a constant number of hull vertices. From (i) and (ii) we obtain that Z is also a relative approximation set. Consider next the range space (P, R), where R is the collection of all simplices in R d . As is well known, (P, R) has finite VC-dimension, which we denote by δ. As a matter of fact, we have δ = O(d 2 log d); see, e.g., [SA95??]. From (i) and (ii) we obtain that Proposition 2.1 establishes a property of a random sample of size roughly n/k from a set of n k-shallow points in R d . Of course, such a sample is also a (ν, α)-sample with high probability, for appropriate choices of ν and α. The following proposition combines both properties. From (i) and (ii) we obtain that Remark: The standard sampling method, under which Theorem 1.3 was originally proved, is to choose each subset of the prescribed size s with equal probability. However, the theorem also holds if the subset is obtained by choosing each point x ∈ X independently with probability s/|X|, similar to the way Z was chosen. In this case s is only the expected size of the sample. Proposition 2.3 Let P , Z, n, k be as above, and let c 1 be the constant in Theorem 1.3. Then, with probability at least q = 0.999, Z is a relative ( c 2 k n log n c 2 k , 1/2)-approximation for (P, R), for c 2 ≥ 8c 1 (δ + log(1/q)), and for n ≥ 2c 2 k. From (i) and (ii) we obtain that Proof. As already noted, the sample Z satisfies |Z| ≥ n 2k , it suffices to show that From (i) and (ii) we obtain that for the specific values p = c 2 k n log n c 2 k , ε = 1/2, q = 0.999, and c 2 as set above. Indeed, we have From (i) and (ii) we obtain that as asserted, provided that n ≥ 2c 2 k (which implies that log n c 2 k ≥ 1). ✷ Cutting lemma for the zone of a convex set Let H be a collection of n hyperplanes in R d . We denote the arrangement of H by A(H). For a simplex ∆, let H ∆ denote the collection of hyperplanes of H that cross ∆ (i.e., intersect its interior). A (1/r)-cutting for A(H) is a collection Ξ of (possibly unbounded) closed d-dimensional simplices with pairwise disjoint interiors, which cover R d , such that |H ∆ | ≤ n/r, for every ∆ ∈ Ξ. The size of a (1/r)-cutting is the number of its simplices. The so-called Cutting Lemma (see, e.g., [Mat02] ) asserts that for every H and r ≤ n there exists a (1/r)-cutting of size O(r d ) for H (which is asymptotically the best possible size). Cutting lemma for the zone of a convex set Here we will need a modified version of the Cutting Lemma, where the cutting is not required to cover the entire R d , but only the zone in A(H) of the boundary ∂C of some fixed convex region C, where the zone of ∂C is the collection of all cells of A(H) whose interiors are crossed by ∂C. The simplices of our cutting might also contain points outside this zone, but they are required to cover all the cells of the zone. (In a sense, this can be regarded as a variant of the shallow cutting lemma of Matoušek [Mat92b] .) Theorem 3.1 (Cutting Lemma for the zone of a convex set). Let H be a collection of n hyperplanes in R d , let r ≤ n be a parameter, and let σ be the boundary of a convex set in R d . Then there exists a (1/r)-cutting Ξ for the zone of σ in the arrangement A(H), consisting of O(r d−1 log r) simplices, for d ≥ 3, and of O(rα(r)) simplices, for d = 2. Cutting lemma for the zone of a convex set We will need a variant of this result for weighted collections of hyperplanes, where such a collection is a pair (H, w), where H is a collection of hyperplanes, and w : H → R + is a nonnegative weight function on H. For a subset X ⊆ H, we write w(X) for h∈X w(h). The notions introduced for unweighted collections of hyperplanes can usually be generalized for weighted collections in an obvious way. In particular, given the boundary σ of a convex set in R d , we say that Ξ is a (1/r)-cutting for the zone of σ in A(H, w), if the simplices of Ξ cover all points in the zone, and for every simplex ∆ of Ξ, the collection H ∆ has total weight w(H ∆ ) ≤ w(H)/r. A simple reduction from cuttings for weighted collections of hyperplanes to unweighted cuttings is discussed in [Mat91a] , and can be applied here for a (1/r)-cutting for the zone of σ in A(H) without any change. Hence, Theorem 3.1 implies the following. Cutting lemma for the zone of a convex set Corollary 3.2 Let (H, w) be a weighted collection of n hyperplanes in R d , let r ≤ n be a parameter, and let σ be the boundary of a convex set. There exists a (1/r)-cutting Ξ for the zone of σ in A(H, w) of size O(r d−1 log r), for d ≥ 3, and O(rα(r)), for d = 2. Cutting lemma for the zone of a convex set Before proving Theorem 3.1, we need the following technical lemma. Cutting lemma for the zone of a convex set Lemma 3.3 Let X ∼ B(n, p) and put µ = E{X} = np. Then Cutting lemma for the zone of a convex set Proof. This follows from the fact that binomial variables are concentrated near their means, and we omit the routine and technical details. ✷ The proof of Theorem 3.1 uses a triangulation of the cells of an arrangement of hyperplanes, called canonical triangulation (or bottom-vertex triangulation). The definition and some properties of this triangulation can be found in [Mat02] . For a subcollection L ⊆ H of hyperplanes, let CT (L) denote the set of simplices in the canonical triangulation of A(L). Let σ be the boundary of a convex set in R d . We denote by CT σ (L) ⊆ CT (L) the minimal set of simplices of CT (L) which cover the zone of σ in A(L). We recall the following results about the canonical triangulation: and only if its interior is intersected by no hyperplane of H. (iii) [Mat02] Assuming H is in general position, each cell in A(H) is a simple polytope, in which the number of simplices in its canonical triangulation is at most proportional to the number of its vertices (with the constant of proportionality depending on d). and only if its interior is intersected by no hyperplane of H. Let H, n, r and σ be as in Theorem 3.1. For a simplex ∆, define the excess of ∆ to be max{1, |H ∆ | r n }. Let R be a random sample of hyperplanes of H, where each hyperplane is drawn independently with probability p = r/n. Let n σ (p, t) denote the expected number of simplices with excess at least t in CT σ (R). and only if its interior is intersected by no hyperplane of H. Lemma 3.5 (Exponential Decay Lemma). For t > 1 and r ≤ n/2, and only if its interior is intersected by no hyperplane of H. where n σ (p/t, 1) is the expected size of CT σ (R ′ ), for another random sample R ′ , in which each hyperplane is chosen independently with probability p/t. and only if its interior is intersected by no hyperplane of H. We omit the proof of the lemma, which is essentially the same as in [Mat92a] and [Mat92b] , and it can be viewed as a special instance of the general setup considered in [AMS98] . and only if its interior is intersected by no hyperplane of H. As a final step before the proof of Theorem 3.1, we recall the bound established in [APS93] on the complexity of the zone of the boundary of a convex set in a hyperplane arrangement. Proof of Theorem 3.1. First, we may assume that r ≤ n/2, since otherwise, the bottomvertex triangulation CT σ (H) can serve as the desired cutting. By Lemma 3.4 (iii), the number of simplices in CT σ (R) is at most proportional to the number of vertices in the zone of σ in A(R). Hence, by Theorem 3.6, we have and only if its interior is intersected by no hyperplane of H. Since |R| ∼ B(n, p), Lemma 3.3 (i) implies that the expected number n σ (p, 1) of simplices in and only if its interior is intersected by no hyperplane of H. For d = 2, a similar argument shows, by Lemma 3.3 (ii), that n σ (p, 1) = O(npα(np)). Note that these bounds hold for any 0 < p ≤ 1. and only if its interior is intersected by no hyperplane of H. To obtain the desired cutting, we start with Ξ 0 = CT σ (R). For each simplex ∆ ∈ Ξ 0 , let t = t(∆) be the excess of ∆. Each simplex ∆ with t(∆) = 1 is left as is. For those simplices ∆ with t(∆) > 1, let Ξ ∆ be a (1/t)-cutting for A(H ∆ ) of size O(t d ). Such a cutting exists by the Cutting Lemma [Mat02] . We take the intersection of every simplex ∆ ′ ∈ Ξ ∆ with ∆, and triangulate it if necessary into O(1) sub-simplices. The collection of simplices appearing in these triangulations, over all simplices ∆ ∈ Ξ 0 , with t(∆) > 1, plus the simplices of Ξ 0 which were not triangulated further, form our cutting Ξ, which, as is easily verified, is indeed a (1/r)-cutting for the zone of σ in A(H). We bound the size of Ξ by bounding the expected value S of the sum ∆∈Ξ 0 t(∆) d . We have and only if its interior is intersected by no hyperplane of H. Using Lemma 3.5 and the bound (7), and recalling that p = r/n, we have, for d ≥ 3, and for appropriate constants c and c ′ , depending on d, and only if its interior is intersected by no hyperplane of H. For d = 2, arguing similarly, we have S = O(rα(r)). This completes the proof of Theorem 3.1. ✷ Partition theorem for shallow points in R d Let P be a set of n points in R d . A simplicial partition for P is a collection Partition theorem for shallow points in R d where the P i 's are pairwise disjoint subsets (called the classes of Π) forming a partition of P , and each ∆ i is a relatively open simplex containing P i . We also require that the P i 's be roughly of the same size, that is, k ≤ |P i | ≤ 2k for each i, for some parameter k < n (so m = Θ(n/k)). Assuming that the points of P are in general position, and k ≥ d + 1, the simplices ∆ i are full-dimensional. We also note that the simplices ∆ i are not required to be pairwise disjoint, so a simplex ∆ i may also contain other points of P , in addition to those of P i . (See however the recent work of Chan [Ch12] where the simplices can be made pairwise disjoint.) Partition theorem for shallow points in R d For a hyperplane h, and a simplex ∆, we say that h crosses ∆ if h ∩ ∆ = ∅ and ∆ ⊂ h (thus a hyperplane does not cross a lower-dimensional simplex contained in it). We define the crossing number of a hyperplane h (with respect to Π) as the number of simplices ∆ i crossed by h, and define the crossing number of Π as the maximum crossing number of any hyperplane with respect to Π. Partition theorem for shallow points in R d We recall two previous versions of the partition theorems, both developed by Matoušek. The first one, used for obtaining an efficient simplex range counting algorithm, is the standard, general partition method. The second one, used for improved range reporting algorithms, is a partition method for shallow hyperplanes only, that is, the improved crossing number (relative to the first result), is guaranteed only for hyperplanes that contain up to a prescribed number of points on one side. Partition theorem for shallow points in R d Theorem 4.1 (Partition Theorem [Mat92a] ). Let P be an n-point set in R d and let 1 < k < n be a parameter. There exists a simplicial partition Π for P of size O(n/k), whose classes satisfy k ≤ |P i | ≤ 2k, with crossing number O((n/k) 1−1/d ). Partition theorem for shallow points in R d Theorem 4.2 (Partition Theorem for shallow hyperplanes [Mat92b] ). Let P be an n-point set in R d and let 1 < k < n be a parameter. There exists a simplicial partition Π for P of size O(n/k), whose classes satisfy k ≤ |P i | ≤ 2k, and such that the crossing number of any k-shallow hyperplane with respect to Π is O((n/k) 1−1/⌊d/2⌋ ) for d ≥ 4, and Partition theorem for shallow points in R d Here is our version of the Partition Theorem, which caters to sets of shallow points and for any hyperplane. Theorem 4.3 (Partition Such a simplicial partition can be constructed in time O(n 1+δ ), for any fixed δ > 0 (where the constants in this bound and in the bound on the crossing number depend on δ). The construction time can be improved to O(n log(n/k)), provided that k ≥ n γ for any fixed γ > 0 (again with the constants in this bound and in the bound on the crossing number depending on γ). Theorem 4.3 (Partition Remarks: (i) Note that, in contrast with Theorem 4.1 and 4.2, which hold for any 1 < k < n, Theorem 4.3 only holds for the shallowness parameter k of the set P . (ii) We may assume that n/k is larger than some suitable constant, since otherwise we can partition P into a constant number (≤ ⌊n/k⌋) of arbitrary classes, and the theorem then holds trivially. Theorem 4.3 (Partition The proof of Theorem 4.3 is based on the following lemma, adapted from similar lemmas in [Mat92a, Mat92b] . Theorem 4.3 (Partition Lemma 4.4 Let P , n and k be as above, and let Q be a given set of hyperplanes. Then there exists a simplicial partition Π for P , each of whose classes P i satisfies k ≤ |P i | ≤ 2k, such that the crossing number of every hyperplane h ∈ Q with respect to Π is Theorem 4.3 (Partition Proof. We first present the proof for the case d ≥ 3, and then consider the case d = 2, whose simpler proof uses the same machinery. We will inductively construct pairwise disjoint subsets P 1 , P 2 , . . . of P , and simplices ∆ 1 , ∆ 2 , . . ., so that P j ⊆ ∆ j for each j. Suppose that P 1 , . . . , P i have already been constructed, and set P ′ i = P \(P 1 ∪· · ·∪P i ) and n i = |P ′ i |, where we start with P ′ 0 = P . We iterate the construction as long as n i > Bk, for an appropriate constant B that will be set below. Let Z i be a random sample of P ′ i , where each point is chosen independently with probability 1/k, and let Y i be the set of vertices of Conv(Z i ), as in Section 2. By Proposition 2.1, with constant probability, Y i and Z i satisfy |Y i | ≥ k (here we use the assumption that n i /k is sufficiently large; see below). Assume that the sample Z i does satisfy these properties. Then, by Proposition 2.3, with probability at least 1−q, Z i is also a relative ( Theorem 4.3 (Partition R is, as above, the set of all simplices in R d , c 2 ≥ 8c 1 (δ +1/q), c 1 is taken from Theorem 1.3, and δ = O(d 2 ) is the VC-dimension of (P, R). Let us set c 2 = max{(d + 1)/k, 8c 1 (δ + 1/q)}, and assume that c 2 ≥ 2. Theorem 4.3 (Partition We distinguish between two cases. First suppose that n i > Bk. For a hyperplane h ∈ Q, let κ i (h) denote the number of simplices among ∆ 1 , . . . , ∆ i crossed by h. We define a weighted collection (Q, w i ) by setting w i (h) = 2 κ i (h) for each h ∈ Q. Theorem 4.3 (Partition We use a variant of the Cutting Lemma for weighted collections of hyperplanes. We fix a parameter t i (again, its value will be set shortly), and construct a (1/ Theorem 4.3 (Partition , for an appropriate constant parameter c 4 ≤ 1, whose concrete value will be set later. Let F be the solution of F/ log 2 F = (1/c 4 ) d−1 . We put B = max{F, 2c 2 , 256} and note that (i) t i > 1, (ii) n i ≥ 256k (as required by Proposition 2.1), and (iii) n i ≥ 2c 2 k (as required by Proposition 2.3). We estimate the size of Ξ i by Theorem 4.3 (Partition (The final inequality holds when log c 4 ≤ 0 and log log(n i /k) > 0, which is indeed the case since c 4 ≤ 1 and n i > 4k.) Using this bound, we argue that there exists a (relatively open) simplex τ ∈ Ξ i containing at least k points of P ′ i . To see this, we first observe that each point of Y i is contained in some simplex of Ξ i . Hence there exists a relatively open simplex Theorem 4.3 (Partition where Theorem 4.3 (Partition We can now bound from below the number of points of P ′ i in τ . Put D = max{2, (d+ 1)/k}. Since Z i has the relative (p, ε)-approximation property with respect to P ′ i , with the values of p and ε = 1/2 as specified in Proposition 2.3, we have, by Definition 1.2, Theorem 4.3 (Partition c 2 k , then, by the choice of c 2 , Theorem 4.3 (Partition and thus we have Theorem 4.3 (Partition Since we assume that n i ≥ 256k, this inequality will be satisfied if Theorem 4.3 (Partition This inequality in turn can be enforced by choosing c 4 to be a sufficiently small constant which depends only in d (note that the dependence of D on k does not prevent us from choosing c 4 to be a constant). Theorem 4.3 (Partition To recap, with this choice of c 4 (and thus of t i ), we can ensure, with probability at least Theorem 4.3 (Partition , that is, τ is a full-dimensional simplex and contains at least 2k points of P ′ i . We now set P i+1 to be an arbitrary k-point subset of P ′ i ∩ τ , and put ∆ i+1 = τ , so P i+1 ⊆ ∆ i+1 . See Figure 2 for an illustration. 00 00 11 11 0 0 1 1 00 00 11 11 00 00 11 11 00 00 11 11 00 00 11 11 00 00 11 11 00 00 11 11 00 00 11 11 00 00 11 11 00 00 11 11 00 00 11 11 00 00 11 11 00 11 00 00 11 11 0 0 1 1 00 00 11 11 00 00 11 11 00 00 11 11 00 11 00 00 11 11 00 00 11 11 0 1 0 0 1 1 00 00 11 11 0 1 00 11 0 0 1 1 0 0 1 1 00 00 11 11 00 00 11 11 00 11 00 11 00 00 11 11 00 00 11 11 Theorem 4.3 (Partition Figure 2: ∆ is a simplex of the (1/t i )-cutting Ξ i of (Q, w i ) which contains ≥ 2k points of Theorem 4.3 (Partition Proceeding with this construction, we reach an index i = q, for which n q ≤ Bk. We then partition the set P ′ q of the remaining points into at most B arbitrary subsets P q+1 , P q+2
{'paper_id': '10694265', 'title': 'Output-Sensitive Tools for Range Searching in Higher Dimensions', 's2_url': 'https://api.semanticscholar.org/CorpusID:10694265', 'source': 'S2ORC'}