Micha Sharir

We study the reverse shortest path problem on disk graphs in the plane. In this problem, we consider the proximity graph of a set of \( n \) disks in the plane of arbitrary radii: In this graph, two disks are connected if the distance between them is at most some threshold parameter \( r \) . The case of intersection graphs is a special case with \(r=0\) . We give an algorithm that, given a target length \( k \) , computes the smallest value of \( r \) for which there is a path of length at most \( k \) between some given pair of disks in the proximity graph. Our algorithm runs in \(O^{*}(n^{5/4})\) randomized expected time, which improves to \(O^{*}(n^{6/5})\) for unit disk graphs, where all the disks have the same radius. (In this article, the \(O^{*}(\cdot)\) notation hides subpolynomial factors.) Our technique is robust and can be applied to many variants of the problem. One significant variant is the case of weighted proximity graphs, where edges are assigned real weights equal to the distance between the disks or between their centers, and \( k \) is replaced by a target weight \( w \) ; that is, we seek a path whose length is at most \( w \) . In other variants, we want to optimize a parameter different from \( r \) , such as a scale factor of the radii of the disks. The main technique for the decision version of the problem (determining whether the graph with a given \( r \) has the desired property) is based on efficient implementations of BFS (for the unweighted case) and of Dijkstra’s algorithm (for the weighted case), using efficient data structures for maintaining the bichromatic closest pair for certain bicliques and several distance functions. The optimization problem is then solved by combining the resulting decision procedure with enhanced variants of the interval shrinking and bifurcation technique.

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.

For a set $P$ of $n$ points in $\mathbb R^d$, for any $d\ge 2$, a hyperplane $h$ is called $k$-rich with respect to $P$ if it contains at least $k$ points of $P$. Answering and generalizing a question asked by Peyman Afshani, we show that if the number of $k$-rich hyperplanes in $\mathbb R^d$, $d \geq 3$, is at least $Ω(n^d/k^α+ n/k)$, with a sufficiently large constant of proportionality and with $d\le α< 2d-1$, then there exists a $(d-2)$-flat that contains $Ω(k^{(2d-1-α)/(d-1)})$ points of $P$. We also present upper bound constructions that give instances in which the above lower bound is tight. An extension of our analysis yields similar lower bounds for $k$-rich spheres or $k$-rich flats.

Vertical decomposition is a widely used general technique for decomposing the cells of arrangements of semi-algebraic sets in $d$-space 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 $\mathcal{S}$ be a collection of $n$ semi-algebraic sets of constant complexity in 3D, and let $U(m)$ be an upper bound on the complexity of the union $\mathcal{U}(\mathcal{S}')$ of any subset $\mathcal{S}'\subseteq \mathcal{S}$ of size at most $m$. We prove that the complexity of the vertical decomposition of the complement of $\mathcal{U}(\mathcal{S})$ is $O^*(n^2+U(n))$ (where the $O^*(\cdot)$ notation hides subpolynomial factors). We also show that the complexity of the vertical decomposition of the entire arrangement $\mathcal{A}(\mathcal{S})$ is $O^*(n^2+X)$, where $X$ is the number of vertices in $\mathcal{A}(\mathcal{S})$. (ii) Let $\mathcal{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 $\mathcal{A}(\mathcal{F})$ in 4D lying below the lower envelope of $\mathcal{F}$ is $O^*(n^3)$. These results lead to efficient algorithms for a variety of problems involving these decompositions, including algorithms for constructing the decompositions themselves, and for constructing $(1/r)$-cuttings of substructures of arrangements of the kinds considered above. One additional algorithm of interest is for output-sensitive point enclosure queries amid semi-algebraic sets in three or four dimensions. In addition, as a main domain of applications, we study various proximity problems involving points and lines in 3D.