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.

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.

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 establish an improved upper bound for the number of incidences between m points and n arbitrary circles in three dimensions. The previous best known bound, originally established for the planar case and later extended to any dimension ≥ 2, is O*(m2/3n2/3 + m6/11n9/11+m+n) (where the O*() notation hides sub-polynomial factors). Since all the points and circles may lie on a common plane or sphere, it is impossible to improve the bound in R^3 without first improving it in the plane.