Let \(0 \lt \alpha \le 1/2\). We say that a finite point set \(P\) in \(\mathbb R^d\) is \(\alpha\)-split by a hyperplane \(h\) if each of the closed half-spaces determined by \(h\), contains at least \(\alpha|P|\) of the points of \(P\). We further say \(P\) is \(\alpha\)-split by a \(k\)-dimensional flat \(\tau\) if \(P\) is \(\alpha\)-split by any hyperplane through \(\tau\). In the standard notation (which coincides with Tukey depth for \(k = 0\)), the \(k\)-flat \(\tau\) has depth \(\alpha\) with respect to \(P\).

The 1913 Helly’s theorem states that any family \(\mathcal{K}\) of \(n \ge d+1\) convex sets in \(\mathbb{R}^d\) can be pierced by a single point if and only if any \(d+1\) of \(\mathcal{K}\)’s elements can. In 2002 Alon, Kalai, Matoušek and Meshulam ruled out the possibility of similar criteria for the existence of lines crossing multiple convex sets in dimension \(d \ge 3\) – for any \(k \ge 3\), they described arbitrary large families \(\mathcal{K}\) of convex sets in \(\mathbb{R}^3\) so that any \(k\) elements of \(\mathcal{K}\) can be crossed by a line yet no \(k+4\) of them can.

The vast majority of hypergraphs that arise in discrete and computational geometry, describe semi-algebraic relations between elementary geometric objects. We use the polynomial method of Guth and Katz to establish stronger and more efficient regularity and density theorems for such k-uniform hypergraphs H = (P, E ), where P is a finite point set in ℝd, and the edge set E is determined by a semi-algebraic relation of bounded description complexity.

Let (P, E) be a (d + 1)-uniform geometric hypergraph, where P is an n-point set in general position in ℝd and is a collection of d-dimensional simplices with vertices in P, for 0 < ɛ ≤ 1. We show that there is a point x ∈ ℝd that piercessimplices in E, for any fixed δ > 0. This is a dramatic improvement in all dimensions d ≥ 3, over the previous lower bounds of the general form ɛ(cd)d+1nd+1, which date back to the seminal 1991 work of Alon, Bárány, Füredi and Kleitman.

We show that for any finite point set P in the plane and ϵ > 0 there exist \( O(\tfrac{1}{{\epsilon }^{3/2+\gamma }}) \) points in ℝ 2 , for arbitrary small γ > 0, that pierce every convex set K with | K ∩ P |> ϵ | P |. This is the first improvement of the bound of \( O(\tfrac{1}{{\epsilon }^2}) \) that was obtained in 1992 by Alon, Bárány, Füredi, and Kleitman for general point sets in the plane.

Given a finite point set P in ℝd, and >0 we say that N⊆ ℝd is a weak -net if it pierces every convex set K with |K∩ P|≥ є |P|.

Let $$\mathcal {F}$$ F be a family of convex sets in $${\mathbb {R}}^d,$$ R d , which are colored with $$d+1$$ d + 1 colors. We say that $$\mathcal {F}$$ F satisfies the Colorful Helly Property if every rainbow selection of $$d+1$$ d + 1 sets, one set from each color class, has a non-empty common intersection. The Colorful Helly Theorem of Lovász states that for any such colorful family $$\mathcal {F}$$ F there is a color class $$\mathcal {F}_i\subset \mathcal {F},$$ F i ⊂ F , for $$1\le i\le d+1,$$ 1 ≤ i ≤ d + 1 , whose sets have a non-empty intersection. We establish further consequences of the Colorful Helly hypothesis. In particular, we show that for each dimension $$d\ge 2$$ d ≥ 2 there exist numbers f(d) and g(d) with the following property: either one can find an additional color class whose sets can be pierced by f(d) points, or all the sets in $$\mathcal {F}$$ F can be crossed by g(d) lines.

We show that for any finite point set P in the plane and ε>0 there exist O(1/ε3/2+γ) points, for arbitrary small γ>0, that pierce every convex set K with |K∩ P|≥ ε |P|. This is the first improvement of the bound of O(1)ε2) that was obtained in 1992 by Alon, Bárány, Füredi and Kleitman for general point sets in the plane.

We consider the Approximate Nearest Neighbor (ANN) problem where the input set consists of n k-flats in the Euclidean Rd, for any fixed parameters k 0 is another prespecified parameter. We present an algorithm that achieves this task with n^{k+1}(log(n)/epsilon)^O(1) storage and preprocessing (where the constant of proportionality in the big-O notation depends on d), and can answer a query in O(polylog(n)) time (where the power of the logarithm depends on d and k). In particular, we need only near-quadratic storage to answer ANN queries amidst a set of n lines in any fixed-dimensional Euclidean space. As a by-product, our approach also yields an algorithm, with similar performance bounds, for answering exact nearest neighbor queries amidst k-flats with respect to any polyhedral distance function. Our results are more general, in that they also provide a tradeoff between storage and query time.

If two closed Jordan curves in the plane have precisely one point in common, then it is called a touching point. All other intersection points are called crossing points. The main result of this paper is a Crossing Lemma for closed curves: In any family of n pairwise intersecting simple closed curves in the plane, no three of which pass through the same point, the number of crossing points exceeds the number of touching points by a factor of Ω((log log n)1/8). As a corollary, we prove the following long-standing conjecture of Richter and Thomassen: The total number of intersection points between any n pairwise intersecting simple closed curves in the plane, no three of which pass through the same point, is at least (1 – o(1))n2.

A long standing conjecture of Richter and Thomassen states that the total number of intersection points between any n simple closed Jordan curves in the plane, so that any two of them intersect and no three curves pass through the same point, is at least (1 – o(1))n2. We confirm the above conjecture in several important cases, including the case (1) when all curves are convex, and (2) when the family of curves can be partitioned into two equal classes such that each curve from the first class is touching every curve from the second class. (Two curves are said to be touching if they have precisely one point in common, at which they do not properly cross.) An important ingredient of our proofs is the following statement: Let S be a family of the graphs of n continuous real functions defined on ℝ, no three of which pass through the same point. If there are nt pairs of touching curves in S, then the number of crossing points is .

Let P be a collection of n points in the plane, each moving along some straight line at unit speed. We obtain an almost tight upper bound of O ( n 2+ϵ ), for any ϵ > 0, on the maximum number of discrete changes that the Delaunay triangulation DT( P ) of P experiences during this motion. Our analysis is cast in a purely topological setting, where we only assume that (i) any four points can be co-circular at most three times, and (ii) no triple of points can be collinear more than twice; these assumptions hold for unit speed motions.

Let P be a collection of n points in the plane, each moving along some straight line at unit speed. We obtain an almost tight upper bound of O(n2+ε), for any ε > 0, on the maximum number of discrete changes that the Delaunay triangulation DT(P) of P experiences during this motion. Our analysis is cast in a purely topological setting, where we only assume that (i) any four points can be co-circular at most three times, and (ii) no triple of points can be collinear more than twice; these assumptions hold for unit speed motions.

Let P be a collection of n points moving along pseudo-algebraic trajectories in the plane. One of the hardest open problems in combinatorial and computational geometry is to obtain a nearly quadratic upper bound, or at least a subcubic bound, on the maximum number of discrete changes that the Delaunay triangulation DT(P) of P experiences during the motion of the points of P. In this paper we obtain an upper bound of O(n2+ε), for any ε>0, under the assumptions that (i) any four points can be co-circular at most twice, and (ii) either no ordered triple of points can be collinear more than once, or no triple of points can be collinear more than twice.

We show that the number of geometric permutations of an arbitrary collection of n pairwise disjoint convex sets in ${\mathbb R}^d$, for $d\geq 3$, is $O(n^{2d-3}\log n)$, improving Wenger's 20-year-old bound of $O(n^{2d-2})$.

The best known upper bound on the number of topological changes in the Delaunay triangulation of a set of moving points in ℜ2 is (nearly) cubic, even if each point is moving with a fixed velocity. We introduce the notion of a stable Delaunay graph (SDG in short), a dynamic subgraph of the Delaunay triangulation, that is less volatile in the sense that it undergoes fewer topological changes and yet retains many useful properties of the full Delaunay triangulation. SDG is defined in terms of a parameter ± > 0, and consists of Delaunay edges pq for which the (equal) angles at which p and q see the corresponding Voronoi edge epq are at least ±. We prove several interesting properties of SDG and describe two kinetic data structures for maintaining it. Both structures use O*(n) storage. They process O*(n2) events during the motion, each in O*(1) time, provided that the points of P move along algebraic trajectories of bounded degree; the O*(·) notation hides multiplicative factors that are polynomial in 1/± and polylogarithmic in n. The first structure is simpler but the dependency on 1/± in its performance is higher.

We present a simple randomized scheme for triangulating a set P of n points in the plane, and construct a kinetic data structure which maintains the triangulation as the points of P move continuously along piecewise algebraic trajectories of constant description complexity. Our triangulation scheme experiences an expected number of O(n2βs+2(n) log2 n) discrete changes, and handles them in a manner that satisfies all the standard requirements from a kinetic data structure: compactness, efficiency, locality and responsiveness. Here s is the maximum number of times where any specific triple of points of P can become collinear, βs+2(q) = λs+2(q)/q, and λs+2(q) is the maximum length of Davenport-Schinzel sequences of order s + 2 on n symbols. Thus, compared to the previous solution of Agarwal et al. [4], we achieve a (slightly) improved bound on the number of discrete changes in the triangulation. In addition, we believe that our scheme is simpler to implement and analyze.

Let B be a collection of n arbitrary balls in ℜ3. We establish an almost-tight upper bound of O(n3+ε), for any ε > 0, on the complexity of the space F(B) of all the lines that avoid all the members of B. In particular, we prove that the balls of B admit O(n3+ε) free isolated tangents, for any ε > 0. This generalizes the result of Agarwal et al. [1], who established this bound only for congruent balls, and solves an open problem posed in that paper. Our bound almost meets the recent lower bound of Ω(n3) of Glisse and Lazard [6].

We show that the number of geometric permutations of an arbitrary collection of n pairwise disjoint convex sets in Rd, for d ≥ 3, is O(n2d-3log n), improving Wenger's 20 years old bound of O(n2d-2).

We establish a bound of $O(n^2k^{1+\varepsilon})$, for any $\varepsilon>0$, on the combinatorial complexity of the set $\mathcal{T}$ of line transversals of a collection $\mathcal{P}$ of k convex polyhedra in $\mathbb{R}^3$ with a total of n facets, and we present a randomized algorithm which computes the boundary of $\mathcal{T}$ in comparable expected time. Thus, when $k\ll n$, the new bounds on the complexity (and construction cost) of $\mathcal{T}$ improve upon the previously best known bounds, which are nearly cubic in n. To obtain the above result, we study the set $\mathcal{T}_{\ell_0}$ of line transversals which emanate from a fixed line $\ell_0$, establish an almost tight bound of $O(nk^{1+\varepsilon})$ on the complexity of $\mathcal{T}_{\ell_0}$, and provide a randomized algorithm which computes $\mathcal{T}_{\ell_0}$ in comparable expected time. Slightly improved combinatorial bounds for the complexity of $\mathcal{T}_{\ell_0}$ and comparable improvements in the cost of constructing this set are established for two special cases, both assuming that the polyhedra of $\mathcal{P}$ are pairwise disjoint: the case where $\ell_0$ is disjoint from the polyhedra of $\mathcal{P}$, and the case where the polyhedra of $\mathcal{P}$ are unbounded in a direction parallel to $\ell_0$. Our result is related to the problem of bounding the number of geometric permutations of a collection $\mathcal{C}$ of k pairwise-disjoint convex sets in $\mathbb{R}^3$, namely, the number of distinct orders in which the line transversals of $\mathcal{C}$ visit its members. We obtain a new partial result on this problem.

We establish a bound of O(n2k1+∊), for any ∊ > 0, on the combinatorial complexity of the set Ƭ of line transversals of a collection of k convex polyhedra in ℝ3 with a total of n facets, and present a randomized algorithm which computes the boundary of Ƭ in comparable expected time. Thus, when k ≪ n, the new bounds on the complexity (and construction cost) of Ƭ improve upon the previously best known bounds, which are nearly cubic in n. To obtain the above result, we study the set Ƭℓ0 of line transversals which emanate from a fixed line ℓ0, establish an almost tight bound of O(nk1+∊) on the complexity of Ƭℓ0, and provide a randomized algorithm which computes Ƭℓ0 in comparable expected time. Slightly improved combinatorial bounds for the complexity of Ƭℓ0, and comparable improvements in the cost of constructing this set, are established for two special cases, both assuming that the polyhedra of are pairwise disjoint: the case where ℓ0 is disjoint from the polyhedra of , and the case where the polyhedra of are unbounded in a direction parallel to ℓ0.

Let P be a set of n points in $\mathbb{R}^d$, so that each point is colored by one of C given colors. We present algorithms for preprocessing P into a data structure that efficiently supports queries of the following form: Given an axis-parallel box Q, count the number of distinct colors of the points of $P\cap Q$. We present a general and relatively simple solution that has a polylogarithmic query time and worst-case storage about $O(n^d)$. It is based on several interesting structural properties of the problem, which we establish here. We also show that for random inputs, the data structure requires almost linear expected storage. We then present several techniques for achieving space-time tradeoff. In $\mathbb{R}^2$, the most efficient solution uses fast matrix multiplication in the preprocessing stage. In higher dimensions we use simpler tradeoff mechanisms, which behave just as well. We give a reduction from matrix multiplication to the off-line version of problem, which shows that in $\mathbb{R}^2$ our time-space tradeoffs are reasonably sharp, in the sense that improving them substantially would improve the best exponent of matrix multiplication. Finally, we present a generalized matrix multiplication problem and show its intimate relation to counting colors in boxes in higher dimension.