We study various nearest-neighbor searching problems involving points, lines, segments and triangles in ℝ³. Among many results, we present a linear-size data structure for answering nearest-neighbor queries with lines amid n points in ℝ³, in O^*(n^{1/2}) time per query (where the O^*(⋅) notation hides subpolynomial factors). Our solution is based on parametric search, where the problem is reduced to range emptiness queries amid points in ℝ³ with cylindrical queries. For the latter problem we show that reporting all k points lying inside a cylinder query costs an additional term of O(k). We also study setups where both data and query objects are lines, segments, or triangles, and obtain improved solutions for the two extreme regimes of (near-)linear storage and of fast query time. These results also yield tradeoff bounds, where the cost of a query depends on the storage allocated to the structure. This work is a continuation of a recent work by the authors [Pankaj K. Agarwal et al., 2024].

We present an algorithm that, given \(m\) points and \(n\) disks in \(\mathbb{R}^2\), computes the disk that contains the maximum number of points. The algorithm runs in \(O^*(m^{2/3} n^{2/3} + m^{32/59} n^{145/177} + m + n)\) expected time, where the \(O^*(\cdot)\) notation hides factors of the form \(n^\varepsilon\), for an arbitrarily small \(\varepsilon \gt 0\), and coefficients that depend on \(\varepsilon\). The algorithm is faster than existing algorithms for \(m \lt n^{5/4}\), and it has similar performance bounds for \(m \ge n^{5/4}\). As a matter of fact, except for disks that are fully contained in other disks, the algorithm counts the number of input points in each disk.

We derive an improved upper bound for the number of incidences between the n vertices of a uniform grid and m convex or concave curves, each pair of which intersect in at most s points, for some integer parameter s ≥ 1. For a square grid, our bound is O(n^{2/3}m^{2/3} + m^{1-1/(3s)} n^{(s+1)/3s} + m + n) . This improves a general bound of O(m n^{1/3}) on the number of incidences with respect to vertices of a grid and convex or concave curves. For a rectangular grid, which fits inside a 1×K rectangle, for some integer K > 1 (which generally may depend on n), the bound also depends on how large K is. The precise result is stated in Theorem 2, but, roughly, we get the same bound as above when K is not too large. Our analysis competes with a celebrated result of Bombieri and Pila [E. Bombieri and J. Pila, 1989], which gives (usually) a sharper bound if we assume that the input curves are algebraic of constant degree and the input points are vertices of the square grid. However, the analysis in [E. Bombieri and J. Pila, 1989] strongly relies on these assumptions, and cannot be extended to handle the more general setup considered here. As a main application, of independent interest, we present a variant of our technique for semi-algebraic range reporting on sets of points of "bounded spread" in the plane.

Let $$\mathscr {B}$$ be a set of n unit balls in $${\mathbb {R}}^3$$ . We present a linear-size data structure for storing $$\mathscr {B}$$ that can determine in $$O^*(\sqrt{n})$$ time whether a query line intersects any ball of $$\mathscr {B}$$ and report all k such balls in additional O(k) time. The data structure can be constructed in $$O(n\log n)$$ time. (The $$O^*(\cdot )$$ notation hides subpolynomial factors, e.g., of the form $$O(n^{{\varepsilon }})$$ , for arbitrarily small $${\varepsilon }> 0$$ , and their coefficients which depend on $${\varepsilon }$$ .) We also consider the dual problem: Let $$\mathscr {L}$$ be a set of n lines in $${\mathbb {R}}^3$$ . We preprocess $$\mathscr {L}$$ , in $$O^*(n^2)$$ time, into a data structure of size $$O^*(n^2)$$ that can determine in $$O(\log {n})$$ time whether a query unit ball intersects any line of $$\mathscr {L}$$ , or report all k such lines in additional O(k) time.

Let \(\mathcal{T}\) be a set of \(n\) flat (planar) semi-algebraic regions in \(\mathbb{R}^{3}\) of constant complexity (e.g., triangles, disks), which we call plates . We wish to preprocess \(\mathcal{T}\) into a data structure so that for a query object \(\gamma\) , which is also a plate, we can quickly answer various intersection queries , such as detecting whether \(\gamma\) intersects any plate of \(\mathcal{T}\) , reporting all the plates intersected by \(\gamma\) , or counting them. We also consider two simpler cases of this general setting: (i) the input objects are plates and the query objects are constant-degree parametrized algebraic arcs in \(\mathbb{R}^{3}\) ( arcs , for short), or (ii) the input objects are arcs and the query objects are plates in \(\mathbb{R}^{3}\) . Besides being interesting in their own right, the data structures for these two special cases form the building blocks for handling the general case. By combining the polynomial-partitioning technique with additional tools from real algebraic geometry, we present many different data structures for intersection queries, which also provide trade-offs between their size and query time. For example, if \(\mathcal{T}\) is a set of plates and the query objects are algebraic arcs, we obtain a data structure that uses \(O^{*}(n^{4/3})\) storage (where the \(O^{*}(\cdot)\) notation hides factors of the form \(n^{\varepsilon}\) , for an arbitrarily small \(\varepsilon>0\) ) and answers an arc-intersection query in \(O^{*}(n^{2/3})\) time. This result is significant since the exponents do not depend on the specific shape of the input and query objects. We generalize and slightly improve this result: for a parameter \(s\in[n^{4/3},n^{t_{q}}]\) , where \({t_{q}}\geq 3\) is the number of real parameters needed to specify a query arc, the query time can be decreased to \(O^{*}((n/s^{1/{t_{q}}})^{\tfrac{2/3}{1-1/{t_{q}}}})\) by increasing the storage to \(O^{*}(s)\) . Our approach can be extended to many additional intersection-searching problems in three dimensions, even when the input or query objects are not flat.

Let $P$ be a set of $m$ points in ${\mathbb R}^2$, let $Σ$ be a set of $n$ semi-algebraic sets of constant complexity in ${\mathbb R}^2$, let $(S,+)$ be a semigroup, and let $w: P \rightarrow S$ be a weight function on the points of $P$. We describe a randomized algorithm for computing $w(P\capσ)$ for every $σ\inΣ$ in overall expected time $O^*\bigl( m^{\frac{2s}{5s-4}}n^{\frac{5s-6}{5s-4}} + m^{2/3}n^{2/3} + m + n \bigr)$, where $s>0$ is a constant that bounds the maximum complexity of the regions of $Σ$, and where the $O^*(\cdot)$ notation hides subpolynomial factors. For $s\ge 3$, surprisingly, this bound is smaller than the best-known bound for answering $m$ such queries in an on-line manner. The latter takes $O^*(m^{\frac{s}{2s-1}}n^{\frac{2s-2}{2s-1}}+m+n)$ time. Let $Φ: Σ\times P \rightarrow \{0,1\}$ be the Boolean predicate (of constant complexity) such that $Φ(σ,p) = 1$ if $p\inσ$ and $0$ otherwise, and let $Σ\mathopΦ P = \{ (σ,p) \in Σ\times P \mid Φ(σ,p)=1\}$. Our algorithm actually computes a partition ${\mathcal B}_Φ$ of $Σ\mathopΦ P$ into bipartite cliques (bicliques) of size (i.e., sum of the sizes of the vertex sets of its bicliques) $O^*\bigl( m^{\frac{2s}{5s-4}}n^{\frac{5s-6}{5s-4}} + m^{2/3}n^{2/3} + m + n \bigr)$. It is straightforward to compute $w(P\capσ)$ for all $σ\in Σ$ from ${\mathcal B}_Φ$. Similarly, if $η: Σ\rightarrow S$ is a weight function on the regions of $Σ$, $\sum_{σ\in Σ: p \in σ} η(σ)$, for every point $p\in P$, can be computed from ${\mathcal B}_Φ$ in a straightforward manner. A recent work of Chan et al. solves the online version of this dual point enclosure problem within the same performance bound as our off-line solution. We also mention a few other applications of computing ${\mathcal B}_Φ$.

Vertical decomposition is a widely used general technique for decomposing the cells of arrangements of semi-algebraic sets in ℝd into constant-complexity subcells. In this paper, we settle in the affirmative a few long-standing open problems involving the vertical decomposition of substructures of arrangements for d = 3,4: (i) Let S be a collection of n semi-algebraic sets of constant complexity in ℝ3, and let U(m) be an upper bound on the complexity of the union U(S‘) of any subset S’ ⊆ S of size at most m. We prove that the complexity of the vertical decomposition of the complement of U(S) is O* (n2 + U(n)) (where the O* (·) notation hides subpolynomial factors). We also show that the complexity of the vertical decomposition of the entire arrangement A(S) is O*(n2 + X), where X is the number of vertices in A(S). (ii) Let F be a collection of n trivariate functions whose graphs are semi-algebraic sets of constant complexity. We show that the complexity of the vertical decomposition of the portion of the arrangement A(F) in ℝ4 lying below the lower envelope of F is O*(n3).

We present subquadratic algorithms in the algebraic decision-tree model for several 3Sum-hard geometric problems, all of which can be reduced to the following question: Given two sets A, B, each consisting of n pairwise disjoint segments in the plane, and a set C of n triangles in the plane, we want to count, for each triangle Δ∈C, the number of intersection points between the segments of A and those of B that lie in Δ. We present solutions in the algebraic decision-tree model whose cost is O(n60/31+ε), for any ε>0. Our approach is based on a primal-dual range searching mechanism, which exploits the multi-level polynomial partitioning machinery recently developed by Agarwal et al. (2021) [3]. A key step in the procedure is a variant of point location in arrangements, say of lines in the plane, which is based solely on the order type of the lines, a “handicap” that turns out to be beneficial for speeding up our algorithm.

Let $\mathcal{T}$ be a set of $n$ flat (planar) semi-algebraic regions in $\mathbb{R}^3$ of constant complexity (e.g., triangles, disks), which we call plates. We wish to preprocess $\mathcal{T}$ into a data structure so that for a query object $γ$, which is also a plate, we can quickly answer various intersection queries, such as detecting whether $γ$ intersects any plate of $\mathcal{T}$, reporting all the plates intersected by $γ$, or counting them. We also consider two simpler cases of this general setting: (i) the input objects are plates and the query objects are constant-degree parametrized algebraic arcs in $\mathbb{R}^3$ (arcs, for short), or (ii) the input objects are arcs and the query objects are plates in $\mathbb{R}^3$. Besides being interesting in their own right, the data structures for these two special cases form the building blocks for handling the general case. By combining the polynomial-partitioning technique with additional tools from real algebraic geometry, we present many different data structures for intersection queries, which also provide trade-offs between their size and query time. For example, if $\mathcal{T}$ is a set of plates and the query objects are algebraic arcs, we obtain a data structure that uses $O^*(n^{4/3})$ storage (where the $O^*(\cdot)$ notation hides factors of the form $n^ε$, for an arbitrarily small $ε>0$) and answers an arc-intersection query in $O^*(n^{2/3})$ time. This result is significant since the exponents do not depend on the specific shape of the input and query objects. We generalize and slightly improve this result: for a parameter $s\in [n^{4/3}, n^{t_q}]$, where ${t_q}\ge 3$ is the number of real parameters needed to specify a query arc, the query time can be decreased to $O^*((n/s^{1/{t_q}})^{\tfrac{2/3}{1-1/{t_q}}})$ by increasing the storage to $O^*(s)$.

We develop data structures for intersection detection queries in four dimensions that involve segments, triangles and tetrahedra. Specifically, we study two main problems: (i) Preprocess a set of n tetrahedra in {ℝ}⁴ into a data structure for answering segment-intersection queries amid the given tetrahedra (referred to as segment-tetrahedron intersection queries), and (ii) Preprocess a set of n triangles in {ℝ}⁴ into a data structure that supports triangle-intersection queries amid the input triangles (referred to as triangle-triangle intersection queries). As far as we can tell, these problems have not been previously studied. For problem (i), we first present a "standard" solution which, for any prespecified value n ≤ s ≤ n⁶ of a so-called storage parameter s, yields a data structure with O^*(s) storage and expected preprocessing, which answers an intersection query in O^*(n/s^{1/6}) time (here and in what follows, the O^*(⋅) notation hides subpolynomial factors). For problem (ii), using similar arguments, we present a solution that has the same asymptotic performance bounds. We then improve the solution for problem (i), and present a more intricate data structure that uses O^*(n²) storage and expected preprocessing, and answers a segment-tetrahedron intersection query in O^*(n^{1/2}) time. Using the parametric search technique of Agarwal and Matoušek [P. K. Agarwal and J. Matoušek, 1993], we can obtain data structures with similar performance bounds for the ray-shooting problem amid tetrahedra in {ℝ}⁴. Unfortunately, so far we do not know how to obtain a similar improvement for problem (ii). Our algorithms are based on a primal-dual technique for range searching with semi-algebraic sets, based on recent advances in this area [P. K. Agarwal et al., 2021; J. Matoušek and Z. Patáková, 2015]. As this is a result of independent interest, we spell out the details of this technique. As an application, we present a solution to the problem of "continuous collision detection" amid moving tetrahedra in 3-space. That is, the workspace consists of n tetrahedra, each moving at its own fixed velocity, and the goal is to detect a collision between some pair of moving tetrahedra. Using our solutions to problems (i) and (ii), we obtain an algorithm that detects a collision in O^*(n^{12/7}) expected time. We also present further applications, including an output-sensitive algorithm for constructing the arrangement of n tetrahedra in ℝ⁴ and an output-sensitive algorithm for constructing the intersection or union of two or several nonconvex polyhedra in ℝ⁴.

We consider several intersection searching problems that involve lines in ${\mathbb R}^3$ and present improved algorithms for solving them. The problems include (i) ray shooting amid triangles in ${\mathbb R}^3$, (ii) reporting intersections between query lines (segments, or rays) and input triangles in ${\mathbb R}^3$, as well as approximately counting the number of such intersections, (iii) computing the intersection of two nonconvex polyhedra in ${\mathbb R}^3$, (iv) detecting, counting, or reporting intersections in a set of lines in ${\mathbb R}^3$, and (v) output-sensitive construction of an arrangement of triangles in ${\mathbb R}^3$. Our approach is based on the polynomial partitioning technique. Our ray-shooting algorithm processes a set of $n$ triangles in ${\mathbb R}^3$ into a data structure for answering ray-shooting queries amid the given triangles, which uses $O(n^{3/2+{\varepsilon}})$ storage and expected preprocessing time, and answers a query in $O(n^{1/2+{\varepsilon}})$ time, for any ${\varepsilon}>0$. This is a significant improvement over known results, obtained more than 25 years ago, in which, with this amount of storage, the query time bound is roughly $n^{5/8}$. The algorithms for the other problems have similar performance bounds, with similar improvements over previous results. We also derive a nontrivial improved tradeoff between storage and query time. Using it, we obtain algorithms that answer $m$ queries on $n$ objects in $\max \left\{ O(m^{2/3}n^{5/6+{\varepsilon}} + n^{1+{\varepsilon}}),\; O(m^{5/6+{\varepsilon}}n^{2/3} + m^{1+{\varepsilon}}) \right\}$ expected time for any ${\varepsilon}>0$.

We show that the maximum number of pairwise nonoverlapping $k$-rich lenses (lenses formed by at least $k$ circles) in an arrangement of $n$ circles in the plane is $O(n^{3/2}\log(n / k^3)/k^{5/2} + n/k)$, and the sum of the degrees of the lenses of such a family (where the degree of a lens is the number of circles that form it) is $O(n^{3/2}\log(n/k^3)/k^{3/2} + n)$. Two independent proofs of these bounds are given, each interesting in its own right (so we believe). The second proof gives a bound that is weaker by a polylogarithmic factor. We then show that these bounds lead to the known bound of Agarwal et al. [ J. ACM, 51 (2004), pp. 139--186] and Marcus and Tardos [ J. Combin. Theory Ser. A, 113 (2006), pp. 675--691] on the number of point-circle incidences in the plane. Extensions to families of more general algebraic curves and some other related problems are also considered.

We show that the maximum number of pairwise non-overlapping k-rich lenses (lenses formed by at least k circles) in an arrangement of n circles in the plane is O(n^{3/2}log(n / k^3) k^{-5/2} + n/k), and the sum of the degrees of the lenses of such a family (where the degree of a lens is the number of circles that form it) is O(n^{3/2}log(n/k^3) k^{-3/2} + n). Two independent proofs of these bounds are given, each interesting in its own right (so we believe). We then show that these bounds lead to the known bound of Agarwal et al. (JACM 2004) and Marcus and Tardos (JCTA 2006) on the number of point-circle incidences in the plane. Extensions to families of more general algebraic curves and some other related problems are also considered.

We consider several problems that involve lines in three dimensions, and present improved algorithms for solving them. The problems include (i) ray shooting amid triangles in ℝ³, (ii) reporting intersections between query lines (segments, or rays) and input triangles, as well as approximately counting the number of such intersections, (iii) computing the intersection of two nonconvex polyhedra, (iv) detecting, counting, or reporting intersections in a set of lines in ℝ³, and (v) output-sensitive construction of an arrangement of triangles in three dimensions. Our approach is based on the polynomial partitioning technique. For example, our ray-shooting algorithm processes a set of n triangles in ℝ³ into a data structure for answering ray shooting queries amid the given triangles, which uses O(n^{3/2+ε}) storage and preprocessing, and answers a query in O(n^{1/2+ε}) time, for any ε > 0. This is a significant improvement over known results, obtained more than 25 years ago, in which, with this amount of storage, the query time bound is roughly n^{5/8}. The algorithms for the other problems have similar performance bounds, with similar improvements over previous results. We also derive a nontrivial improved tradeoff between storage and query time. Using it, we obtain algorithms that answer m queries on n objects in max{O(m^{2/3}n^{5/6+{ε}} + n^{1+ε}), O(m^{5/6+ε}n^{2/3} + m^{1+ε})} time, for any ε > 0, again an improvement over the earlier bounds.

We present subquadratic algorithms in the algebraic decision-tree model for several \textsc{3Sum}-hard geometric problems, all of which can be reduced to the following question: Given two sets $A$, $B$, each consisting of $n$ pairwise disjoint segments in the plane, and a set $C$ of $n$ triangles in the plane, we want to count, for each triangle $Δ\in C$, the number of intersection points between the segments of $A$ and those of $B$ that lie in $Δ$. The problems considered in this paper have been studied by Chan~(2020), who gave algorithms that solve them, in the standard real-RAM model, in $O((n^2/\log^2n)\log^{O(1)}\log n)$ time. We present solutions in the algebraic decision-tree model whose cost is $O(n^{60/31+\varepsilon})$, for any $\varepsilon>0$. Our approach is based on a primal-dual range searching mechanism, which exploits the multi-level polynomial partitioning machinery recently developed by Agarwal, Aronov, Ezra, and Zahl~(2020). A key step in the procedure is a variant of point location in arrangements, say of lines in the plane, which is based solely on the \emph{order type} of the lines, a "handicap" that turns out to be beneficial for speeding up our algorithm.

In 2015, Guth proved that if $\EuScript{S}$ is a collection of $n$ $g$-dimensional semialgebraic sets in ${\mathbb{R}}^d$ and if $D\geq 1$ is an integer, then there is a $d$-variate polynomial $P$ of degree at most $D$ so that each connected component of $\mathbb{R}^d\setminus Z(P)$ intersects $O(n/D^{d-g})$ sets from $\EuScript{S}$. Such a polynomial is called a generalized partitioning polynomial. We present a randomized algorithm that computes such polynomials efficiently---the expected running time of our algorithm is linear in $\lvert \EuScript{S}\rvert$. Our approach exploits the technique of quantifier elimination combined with that of $\eps$-samples. We also present an extension of our construction to multilevel polynomial partitioning for semialgebraic sets in $\mathbb{R}^d$. We present five applications of our result. The first is a data structure for answering point-enclosure queries among a family of semialgebraic sets in $\mathbb{R}^d$ in $O(\log n)$ time, with storage complexity and expected preprocessing time of $O(n^{d+\eps})$. The second is a data structure for answering range-searching queries with semialgebraic ranges in $\mathbb{R}^d$ in $O(\log n)$ time, with $O(n^{t+\eps})$ storage and expected preprocessing time, where $t > 0$ is an integer that depends on $d$ and the description complexity of the ranges. The third is a data structure for answering vertical ray-shooting queries among semialgebraic sets in $\mathbb{R}^{d}$ in $O(\log^2 n)$ time, with $O(n^{d+\eps})$ storage and expected preprocessing time. The fourth is an efficient algorithm for cutting algebraic curves in $\mathbb{R}^2$ into pseudosegments. The fifth application is for eliminating depth cycles among triangles in $\mathbb{R}^3$, where we show a nearly optimal algorithm to cut $n$ pairwise disjoint nonvertical triangles in ${\mathbb{R}}^3$ into pieces that form a depth order.

We present subquadratic algorithms, in the algebraic decision-tree model of computation, for detecting whether there exists a triple of points, belonging to three respective sets A, B, and C of points in the plane, that satisfy a certain polynomial equation or two equations. The best known instance of such a problem is testing for the existence of a collinear triple of points in A×B×C, a classical 3SUM-hard problem that has so far defied any attempt to obtain a subquadratic solution, whether in the (uniform) real RAM model, or in the algebraic decision-tree model. While we are still unable to solve this problem, in full generality, in subquadratic time, we obtain such a solution, in the algebraic decision-tree model, that uses only roughly O(n^(28/15)) constant-degree polynomial sign tests, for the special case where two of the sets lie on one-dimensional curves and the third is placed arbitrarily in the plane. Our technique is fairly general, and applies to any other problem where we seek a triple that satisfies a single polynomial equation, e.g., determining whether A× B× C contains a triple spanning a unit-area triangle. This result extends recent work by Barba et al. [Luis Barba et al., 2019] and by Chan [Timothy M. Chan, 2020], where all three sets A, B, and C are assumed to be one-dimensional. While there are common features in the high-level approaches, here and in [Luis Barba et al., 2019], the actual analysis in this work becomes more involved and requires new methods and techniques, involving polynomial partitions and other related tools. As a second application of our technique, we again have three n-point sets A, B, and C in the plane, and we want to determine whether there exists a triple (a,b,c) ∈ A×B×C that simultaneously satisfies two real polynomial equations. For example, this is the setup when testing for the existence of pairs of similar triangles spanned by the input points, in various contexts discussed later in the paper. We show that problems of this kind can be solved with roughly O(n^(24/13)) constant-degree polynomial sign tests. These problems can be extended to higher dimensions in various ways, and we present subquadratic solutions to some of these extensions, in the algebraic decision-tree model.

In 2015, Guth [ Math. Proc. Cambridge Philos. Soc., 159 (2015), pp. 459--469] proved that for any set of $k$-dimensional bounded complexity varieties in ${\mathbb R}^d$ and for any positive integer $D$, there exists a polynomial of degree at most $D$ whose zero set divides ${\mathbb R}^d$ into open connected sets so that only a small fraction of the given varieties intersect each of these sets. Guth's result generalized an earlier result of Guth and Katz [ Ann. Math., 181 (2015), pp. 155--190] for points. Guth's proof relies on a variant of the Borsuk--Ulam theorem, and for $k>0$, it is unknown how to obtain an explicit representation of such a partitioning polynomial and how to construct it efficiently. In particular, it is unknown how to effectively construct such a polynomial for bounded-degree algebraic curves (or even lines) in ${{\mathbb R}}^3$. We present an efficient algorithmic construction for this setting. Given a set of $n$ input algebraic curves and a positive integer $D$, we efficiently construct a decomposition of space into $O(D^3\log^3{D})$ open “cells,” each of which meets $O(n/D^2)$ curves from the input. The construction time is $O(n^2)$. For the case of lines in 3-space, we present an improved implementation whose running time is $O(n^{4/3} { polylog }{n})$. The constant of proportionality in both time bounds depends on $D$ and the maximum degree of the polynomials defining the input curves. As an application, we revisit the problem of eliminating depth cycles among nonvertical lines in 3-space, recently studied by Aronov and Sharir [ Discrete Comput. Geom., 59 (2018), pp. 725--741] and show an algorithm that cuts $n$ such lines into $O(n^{3/2+\varepsilon})$ pieces that are depth-cycle free for any $\varepsilon > 0$. The algorithm runs in $O(n^{3/2+\varepsilon})$ time, which is a considerable improvement over the previously known algorithms.

In 2015, Guth proved that if S is a collection of n g-dimensional semi-algebraic sets in R^d and if D >= 1 is an integer, then there is a d-variate polynomial P of degree at most D so that each connected component of R^d \ Z(P) intersects O(n/D^{d-g}) sets from S. Such a polynomial is called a generalized partitioning polynomial. We present a randomized algorithm that computes such polynomials efficiently - the expected running time of our algorithm is linear in |S|. Our approach exploits the technique of quantifier elimination combined with that of epsilon-samples. We present four applications of our result. The first is a data structure for answering point-enclosure queries among a family of semi-algebraic sets in R^d in O(log n) time, with storage complexity and expected preprocessing time of O(n^{d+epsilon}). The second is a data structure for answering range search queries with semi-algebraic ranges in O(log n) time, with O(n^{t+epsilon}) storage and expected preprocessing time, where t > 0 is an integer that depends on d and the description complexity of the ranges. The third is a data structure for answering vertical ray-shooting queries among semi-algebraic sets in R^{d} in O(log^2 n) time, with O(n^{d+epsilon}) storage and expected preprocessing time. The fourth is an efficient algorithm for cutting algebraic planar curves into pseudo-segments.

In 2015, Guth proved that, for any set of k-dimensional varieties in ℝ3 and for any positive integer D, there exists a polynomial of degree at most D whose zero-set divides ℝ3 into open connected “cells,” so that only a small fraction of the given varieties intersect each cell. Guth's result generalized an earlier result of Guth and Katz for points. Guth's proof relies on a variant of the Borsuk-Ulam theorem, and for k > 0, it is unknown how to obtain an explicit representation of such a partitioning polynomial and how to construct it efficiently. In particular, it is unknown how to effectively construct such a polynomial for curves (or even lines) in ℝ3. We present an efficient algorithmic construction for this setting. Given a set of n input curves and a positive integer D, we efficiently construct a decomposition of space into O(D3 log3 D) open cells, each of which meets at most O(n/D2) curves from the input. The construction time is O(n2), where the constant of proportionality depends on D and the maximum degree of the polynomials defining the input curves. For the case of lines in 3-space we present an improved implementation, whose running time is O(n4/3 polylog n). As an application, we revisit the problem of eliminating depth cycles among non-vertical pairwise disjoint triangles in 3-space, recently studied by Aronov et al. (2017) and De Berg (2017). Our main result is an algorithm that cuts n triangles into O(n3/2+ε) pieces that are depth cycle free, for any ε > 0. The algorithm runs in O(n3/2+ε) time, which is nearly worst-case optimal. We also sketch several other applications of our effective partitioning for curves in ℝ3.

We show that the k-SUM problem can be solved by a linear decision tree of depth O(n^2 log^2 n),improving the recent bound O(n^3 log^3 n) of Cardinal et al. Our bound depends linearly on k, and allows us to conclude that the number of linear queries required to decide the n-dimensional Knapsack or SubsetSum problems is only O(n^3 log n), improving the currently best known bounds by a factor of n. Our algorithm extends to the RAM model, showing that the k-SUM problem can be solved in expected polynomial time, for any fixed k, with the above bound on the number of linear queries. Our approach relies on a new point-location mechanism, exploiting "Epsilon-cuttings" that are based on vertical decompositions in hyperplane arrangements in high dimensions. A major side result of the analysis in this paper is a sharper bound on the complexity of the vertical decomposition of such an arrangement (in terms of its dependence on the dimension). We hope that this study will reveal further structural properties of vertical decompositions in hyperplane arrangements.

Let $(X,\EuScript{S})$ be a set system on an $n$-point set $X$. The discrepancy of $\EuScript{S}$ is defined as the minimum of the largest deviation from an even split, over all subsets of $S \in \EuScript{S}$ and two-colorings $\chi$ on $X$. We consider the scenario where, for any subset $X' \subseteq X$ of size $m \le n$ and for any parameter $1 \le k \le m$, the number of restrictions of the sets of $\EuScript{S}$ to $X'$ of size at most $k$ is only $O(m^{d_1} k^{d-d_1})$ for fixed integers $d > 0$ and $1 \le d_1 \le d$ (this generalizes the standard notion of bounded primal shatter dimension when $d_1 = d$). In this case we show that there exists a coloring $\chi$ with discrepancy bound $O^{*}(|S|^{1/2 - d_1/(2d)} n^{(d_1 - 1)/(2d)})$, for each $S \in \EuScript{S}$, where $O^{*}(\cdot)$ hides a polylogarithmic factor in $n$. This bound is tight up to a polylogarithmic factor [J. Matoušek, Discrete Comput. Geom., 13 (1995), pp. 593--601, Geometric Discrepancy, Algorithms Combin. 18, Springer-Verlag, Heidelberg, 1999], and the corresponding coloring $\chi$ can be computed in expected polynomial time using the very recent machinery of Lovett and Meka [Proceedings of the 53 rd Annual IEEE Symposium on Foundations of Computer Science, 2012, pp. 61--67] for constructive discrepancy minimization. Our bound improves and generalizes the bounds obtained from the machinery of Har-Peled and Sharir [Discrete Comput. Geom, 45 (2011), pp. 462--496] (and the follow-up work in [M. Sharir and S. Zaban, Output-Sensitive Tools for Range Searching in Higher Dimensions, unpublished manuscript, 2011; available online from www.cs.tau.ac.il/thesis/thesis/zaban.pdf]) for points and halfspaces in $d$-space for $d \ge 3$. Last but not least, we show that our bound yields improved bounds for the size of relative $(\varepsilon, \delta)$-approximations for set systems of the above kind.

We refine the bound on the packing number, originally shown by Haussler, for shallow geometric set systems. Specifically, let V be a finite set system defined over an n-point set X; we view V as a set of indicator vectors over the n-dimensional unit cube. A delta-separated set of V is a subcollection W, s.t. the Hamming distance between each pair u, v in W is greater than delta, where delta > 0 is an integer parameter. The delta-packing number is then defined as the cardinality of the largest delta-separated subcollection of V. Haussler showed an asymptotically tight bound of Theta((n / delta)^d) on the delta-packing number if V has VC-dimension (or primal shatter dimension) d. We refine this bound for the scenario where, for any subset, X' of X of size m <= n and for any parameter 1 <= k <= m, the number of vectors of length at most k in the restriction of V to X' is only O(m^{d_1} k^{d-d_1}), for a fixed integer d > 0 and a real parameter 1 <= d_1 <= d (this generalizes the standard notion of bounded primal shatter dimension when d_1 = d). In this case when V is "k-shallow" (all vector lengths are at most k), we show that its delta-packing number is O(n^{d_1} k^{d-d_1} / delta^d), matching Haussler's bound for the special cases where d_1=d or k=n. We present two proofs, the first is an extension of Haussler's approach, and the second extends the proof of Chazelle, originally presented as a simplification for Haussler's proof.

Let (X, S) be a set system on an n-point set X.The discrepancy of S is defined as the minimum of the largest deviation from an even split, over all subsets of S ∈ S and two-colorings χ on X.We consider the scenario where, for any subset X ′ ⊆ X of size m ≤ n and for any parameter 1 ≤ k ≤ m, the number of restrictions of the sets of S to X ′ of size at most k is only O(m d1 k d-d1 ), for fixed integers d > 0 and 1 ≤ d 1 ≤ d (this generalizes the standard notion of bounded primal shatter dimension when d 1 = d).In this case we show that there exists a coloring χ with discrepancy bound O * (|S| 1/2-d1/(2d) n (d1-1)/( 2d) ), for each S ∈ S, where O * (•) hides a polylogarithmic factor in n.This bound is tight up to a polylogarithmic factor [21,23] and the corresponding coloring χ can be computed in expected polynomial time using the very recent machinery of Lovett and Meka for constructive discrepancy minimization [20].Our bound improves and generalizes the bounds obtained from the machinery of (and the follow-up work in [27]) for points and halfspaces in dspace for d ≥ 3.Last but not least, we show that our bound yields improved bounds for the size of relative (ε, δ)approximations for set systems of the above kind.

We show that, for any $\gamma > 0$, the combinatorial complexity of the union of $n$ locally $\gamma$-fat objects of constant complexity in the plane is $\frac{n}{\gamma^4} 2^{O(\log^*n)}$. For the special case of $\gamma$-fat triangles, the bound improves to $O(n \log^*{n} + \frac{n}{\gamma}\log^2{\frac{1}{\gamma}})$.

We present improved upper bounds for the size of relative (p,ε)-approximation for range spaces with the following property: For any (finite) range space projected onto (that is, restricted to) a ground set of size n and for any parameter 1 ≤ k ≤ n, the number of ranges of size at most k is only nearly-linear in n and polynomial in k. Such range spaces are called "well behaved". Our bound is an improvement over the bound O(log(1/p)/ε2 p) introduced by Li et. al. [17] for the general case (where this bound has been shown to be tight in the worst case), when p l ε. We also show that such small size relative (p,ε)-approximations can be constructed in expected polynomial time.

Motivated by the desire to cope with data imprecision, we study methods for preprocessing a set of line-segments (or just lines) in the plane such that whenever we are given a set of points, each of which lies on a distinct object, we can compute their convex hull more efficiently than in "standard settings" (that is, without preprocessing).

We show that, for any fixed δ > 0, the combinatorial complexity of the union of n triangles in the plane, each of whose angles is at least δ, is O(n2α(n) log* n), with the constant of proportionality depending on δ. This considerably improves the twenty-year-old bound O(n log log n), due to Matousek et al. [24, 25].

We show the existence of $\varepsilon$-nets of size $O\left(\frac{1}{\varepsilon}\log\log\frac{1}{\varepsilon}\right)$ for planar point sets and axis-parallel rectangular ranges. The same bound holds for points in the plane and “fat” triangular ranges and for point sets in $\boldsymbol{R}^3$ and axis-parallel boxes; these are the first known nontrivial bounds for these range spaces. Our technique also yields improved bounds on the size of $\varepsilon$-nets in the more general context considered by Clarkson and Varadarajan. For example, we show the existence of $\varepsilon$-nets of size $O\left(\frac{1}{\varepsilon}\log\log\log\frac{1}{\varepsilon}\right)$ for the dual range space of “fat” regions and planar point sets (where the regions are the ground objects and the ranges are subsets stabbed by points). Plugging our bounds into the technique of Brönnimann and Goodrich or of Even, Rawitz, and Shahar, we obtain improved approximation factors (computable in expected polynomial time by a randomized algorithm) for the hitting set or the set cover problems associated with the corresponding range spaces.

Given a set system (X,R), the hitting set problem is to find a smallest-cardinality subset H ⊆ X, with the property that each range R ∈ R has a non-empty intersection with H. We present near-linear time approximation algorithms for the hitting set problem, under the following geometric settings: (i) R is a set of planar regions with small union complexity. (ii) R is a set of axis-parallel d-rectangles in d-space. In both cases X is either the entire d-dimensional space or a finite set of points in d-space. The approximation factors yielded by the algorithm are small; they are either the same as or within an O(log n) factor of the best factors known to be computable in polynomial time.

We show the existence of ε-nets of size O(1/ε log log 1/ε) for planar point sets and axis-parallel rectangular ranges. The same bound holds for points in the plane with "fat" triangular ranges, and for point sets in reals3 and axis-parallel boxes; these are the first known non-trivial bounds for these range spaces. Our technique also yields improved bounds on the size of ε-nets in the more general context considered by Clarkson and Varadarajan. For example, we show the existence of ε-nets of size

We show that the combinatorial complexity of the union of n “fat” tetrahedra in 3-space (i.e., tetrahedra all of whose solid angles are at least some fixed constant) of arbitrary sizes, is O ( n 2+ε ), for any ε > 0;the bound is almost tight in the worst case, thus almost settling a conjecture of Pach et al. [2003]. Our result extends, in a significant way, the result of Pach et al. [2003] for the restricted case of nearly congruent cubes . The analysis uses cuttings, combined with the Dobkin-Kirkpatrick hierarchical decomposition of convex polytopes, in order to partition space into subcells, so that, on average, the overwhelming majority of the tetrahedra intersecting a subcell Δ behave as fat dihedral wedges in Δ. As an immediate corollary, we obtain that the combinatorial complexity of the union of n cubes in R 3 , having arbitrary side lengths, is O ( n 2+ε ), for any ε > 0 (again, significantly extending the result of Pach et al. [2003]). Finally, our analysis can easily be extended to yield a nearly quadratic bound on the complexity of the union of arbitrarily oriented fat triangular prisms (whose cross-sections have arbitrary sizes) in R 3 .

We show that the combinatorial complexity of the union of n infinite cylinders in R3, having arbitrary radii, is O(n2+epsiv), for any epsiv >0; the bound is almost tight in the worst case, thus settling a conjecture of Agarwal and Sharir, who established a nearly-quadratic bound for the restricted case of nearly congruent cylinders. Our result extends, in a significant way, the result of Agarwal and Sharir, in particular, a simple specialization of our analysis to the case of nearly congruent cylinders yields a nearly-quadratic bound on the complexity of the union in that case, thus significantly simplifying the analysis in. Finally, we extend our technique to the case of "cigars'' of arbitrary radii (that is, Minkowski sums of line-segments and balls), and show that the combinatorial complexity of the union in this case is nearly-quadratic as well. This problem has been studied in for the restricted case where all cigars are (nearly) equal-radii. Based on our new approach, the proof follows almost verbatim from the analysis for infinite cylinders, and is significantly simpler than the proof presented in [3].

Let C be a collection of n compact convex sets in the plane, such that the boundaries of any pair of sets in C intersect in at most s points, for some constant s. We show that the maximum number of regular vertices (intersection points of two boundaries that intersect twice) on the boundary of the union U of C is O*(n4/3), which improves earlier bounds due to Aronov et.al.The bound is nearly tight in the worst case.

We show that the combinatorial complexity of the. union of n "fat" tetrahedra in 3-space (i.e., tetrahedra all of whose solid angles are at least .some fixed constant) of arbitrary sizes, is O(n2+epsiv),for any epsiv > 0: the bound is almost tight in the worst case, thus almost settling a conjecture of Pach el al. [24]. Our result extends, in a significant way, the result of Pach et al. [24] for the restricted case of nearly congruent cubes. The analysis uses cuttings, combined with the Dobkin-K'irkpatrick hierarchical decomposition of convex polytopes, in order to partition space into subcells, so that, on average, the overwhelming majority of the tetrahedra intersecting a subcell Delta behave as fat dihedral wedges in Delta. As an immediate corollary, we obtain that the combinatorial complexity of the union of n cubes in R3having arbitrary side lengths, is O(n2+epsiv), for any epsiv > 0 again, significantly extending the result of [24]. Our analysis can easily he extended to yield a nearly-quadratic bound on the complexity of the union of arbitrarily oriented fat triangular prisms (whose cross-sections have, arbitrary sizes) in R3. Finally, we show that a simple variant of our analysis implies a nearly-linear bound on the complexity of the union of fat triangles in the plane.

We present upper and lower bounds for the number of iterations performed by the Iterative Closest Point (ICP) algorithm. This algorithm has been proposed by Besl and McKay [4] as a successful heuristics for pattern matching under translation, where the input consists of two point sets in d-space, for d≥1, but so far it seems not to have been rigorously analyzed. We consider two standard measures of resemblance that the algorithm attempts to optimize: The RMS (root mean squared distance) and the (one-directional) Hausdorff distance. We show that in both cases the number of iterations performed by the algorithm is polynomial in the number of input points. In particular, this bound is quadratic in the one-dimensional problem, for which we present a lower bound construction of Ω(n logn) iterations under the RMS measure, where n is the overall size of the input. Under the Hausdorff measure, this bound is only O(n) for input point sets whose spread is polynomial in n, and this is tight in the worst case.We also present several structural geometric properties of the algorithm under both measures. For the RMS measure, we show that at each iteration of the algorithm the cost function monotonically and strictly decreases along the vector Δt of the relative translation. As a result, we conclude that the polygonal path π, obtained by concatenating all the relative translations that are computed during the execution of the algorithm, does not intersect itself. In particular, in the one-dimensional problem all the relative translations of the ICP algorithm are in the same (left or right) direction. For the Hausdorff measure, some of these properties continue to hold (such as monotonicity in one dimension), whereas others do not.

We consider the problem of bounding the combinatorial complexity of a single cell in an arrangement of k convex polyhedra in 3-space having n facets in total. We use a variant of the technique of Halperin and Sharir [17], and show that this complexity is O(nk1+ε), for any ε > 0, thus almost settling a conjecture of Aronov et. el. [5]. We then extend our analysis and show that the overall complexity of the zone of a low-degree algebraic surface, or of the boundary of an arbitrary convex set, in an arrangement of k convex polyhedra in 3-space with n facets in total, is also O(nk1+ε), for any ε > 0. Finally, we present a deterministic algorithm that constructs a single cell in an arrangement of this kind, in time O(nk1+ε log2n), for any ε 0.

We present an efficient algorithm for the following problem: Given a collection $T =\{\Delta_1, \ldots, \Delta_n\}$ of n triangles in the plane, such that there exists a subset $S \subset T$ (unknown to us) of $\xi \ll n$ triangles, such that $\bigcup_{\Delta \in S} \Delta = \bigcup_{\Delta \in T} \Delta$, construct efficiently the union of the triangles in T. We show that this problem can be solved in randomized expected time $O(n^{4/3}\log{n} + n\xi\log^2{n})$, which is subquadratic for $\xi=o(n/\log^2{n})$. In our solution, we use a variant of the method of Brönnimann and Goodrich [{\it Discrete Comput. Geom.}, 14 (1995), pp. 463--479] for finding a set cover in a set system of finite VC-dimension. We present a detailed implementation of this variant, which makes it run within the asserted time bound. Our approach is fairly general, and we show that it can be extended to compute efficiently the union of simply shaped bodies of constant description complexity in ${\reals}^d$, when the union is determined by a small subset of the bodies.

We present an algorithm that efficiently counts all intersecting triples among a collection T of triangles in R3 in nearly-quadratic time. This solves a problem posed by Pellegrini, [18]. Using a variant of the technique, one can represent the set of all κ triple intersections, in compact form, as the disjoint union of complete tripartite hypergraphs, which requires nearly-quadratic construction time and storage. Our approach also applies to any collection of convex planar objects of constant description complexity in R3$, with the same performance bounds. We also prove that this counting problem belongs to the 3SUM-hard family, and thus our algorithm is likely to be nearly optimal (since it is believed that 3SUM-hard problems cannot be solved in subquadratic time).