Search

We develop simple and general techniques to obtain faster (near-linear time) static approximation algorithms, as well as efficient dynamic data structures, for four fundamental geometric optimization problems: minimum piercing set (MPS), maximum independent set (MIS), minimum vertex cover (MVC), and maximum-cardinality matching (MCM). Highlights of our results include the following: * For $n$ axis-aligned boxes in any constant dimension $d$, we give an $O(\log \log n)$-approximation algorithm for MPS that runs in $O(n^{1+\delta})$ time for an arbitrarily small constant $\delta>0$. This significantly improves the previous $O(\log\log n)$-approximation algorithm by Agarwal, Har-Peled, Raychaudhury, and Sintos (SODA~2024), which ran in $O(n^{d/2}\mathop{\rm polylog} n)$ time. * Furthermore, we show that our algorithm can be made fully dynamic with $O(n^{\delta})$ amortized update time. Previously, Agarwal et al.~(SODA~2024) obtained dynamic results only in $\mathbb{R}^2$ and achieved only $O(\sqrt{n}\mathop{\rm polylog} n)$ amortized expected update time. * For $n$ axis-aligned rectangles in $\mathbb{R}^2$, we give an $O(1)$-approximation algorithm for MIS that runs in $O(n^{1+\delta})$ time. Our result significantly improves the running time of the celebrated algorithm by Mitchell (FOCS~2021) (which was about $O(n^{21})$), and answers one of his open questions. Our algorithm can also be made fully dynamic with $O(n^{\delta})$ amortized update time. * For $n$ (unweighted or weighted) fat objects in any constant dimension, we give a dynamic $O(1)$-approximation algorithm for MIS with $O(n^{\delta})$ amortized update time. * For disks in $\mathbb{R}^2$ or hypercubes in any constant dimension, we give the first fully dynamic $(1+\varepsilon)$-approximation algorithms for MVC and MCM with $O(\mathop{\rm polylog}n)$ amortized update time., Comment: This paper includes the results on vertex cover and matching from our previous arXiv submission (arXiv:2402.07441), along with new results on piercing and independent sets. Abstract shortened to meet arXiv limit

We revisit a standard polygon containment problem: given a convex $k$-gon $P$ and a convex $n$-gon $Q$ in the plane, find a placement of $P$ inside $Q$ under translation and rotation (if it exists), or more generally, find the largest copy of $P$ inside $Q$ under translation, rotation, and scaling. Previous algorithms by Chazelle (1983), Sharir and Toledo (1994), and Agarwal, Amenta, and Sharir (1998) all required $\Omega(n^2)$ time, even in the simplest $k=3$ case. We present a significantly faster new algorithm for $k=3$ achieving $O(n$polylog $n)$ running time. Moreover, we extend the result for general $k$, achieving $O(k^{O(1/\varepsilon)}n^{1+\varepsilon})$ running time for any $\varepsilon>0$. Along the way, we also prove a new $O(k^{O(1)}n$polylog $n)$ bound on the number of similar copies of $P$ inside $Q$ that have 4 vertices of $P$ in contact with the boundary of $Q$ (assuming general position input), disproving a conjecture by Agarwal, Amenta, and Sharir (1998)., Comment: To appear in SoCG 2024

Polynomial partitioning techniques have recently led to improved geometric data structures for a variety of fundamental problems related to semialgebraic range searching and intersection searching in 3D and higher dimensions (e.g., see [Agarwal, Aronov, Ezra, and Zahl, SoCG 2019; Ezra and Sharir, SoCG 2021; Agarwal, Aronov, Ezra, Katz, and Sharir, SoCG 2022]). They have also led to improved algorithms for offline versions of semialgebraic range searching in 2D, via lens-cutting [Sharir and Zahl (2017)]. In this paper, we show that these techniques can yield new data structures for a number of other 2D problems even for online queries: 1. Semialgebraic range stabbing. We present a data structure for $n$ semialgebraic ranges in 2D of constant description complexity with $O(n^{3/2+\varepsilon})$ preprocessing time and space, so that we can count the number of ranges containing a query point in $O(n^{1/4+\varepsilon})$ time, for an arbitrarily small constant $\varepsilon>0$. 2. Ray shooting amid algebraic arcs. We present a data structure for $n$ algebraic arcs in 2D of constant description complexity with $O(n^{3/2+\varepsilon})$ preprocessing time and space, so that we can find the first arc hit by a query (straight-line) ray in $O(n^{1/4+\varepsilon})$ time. 3. Intersection counting amid algebraic arcs. We present a data structure for $n$ algebraic arcs in 2D of constant description complexity with $O(n^{3/2+\varepsilon})$ preprocessing time and space, so that we can count the number of intersection points with a query algebraic arc of constant description complexity in $O(n^{1/2+\varepsilon})$ time. In particular, this implies an $O(n^{3/2+\varepsilon})$-time algorithm for counting intersections between two sets of $n$ algebraic arcs in 2D., Comment: SOCG 2024

Let $X$ be a set of points in $\mathbb{R}^2$ and $\mathcal{O}$ be a set of geometric objects in $\mathbb{R}^2$, where $|X| + |\mathcal{O}| = n$. We study the problem of computing a minimum subset $\mathcal{O}^* \subseteq \mathcal{O}$ that encloses all points in $X$. Here a point $x \in X$ is enclosed by $\mathcal{O}^*$ if it lies in a bounded connected component of $\mathbb{R}^2 \backslash (\bigcup_{O \in \mathcal{O}^*} O)$. We propose two algorithmic frameworks to design polynomial-time approximation algorithms for the problem. The first framework is based on sparsification and min-cut, which results in $O(1)$-approximation algorithms for unit disks, unit squares, etc. The second framework is based on LP rounding, which results in an $O(\alpha(n)\log n)$-approximation algorithm for segments, where $\alpha(n)$ is the inverse Ackermann function, and an $O(\log n)$-approximation algorithm for disks., Comment: In SoCG'24

In this work, we study two fundamental graph optimization problems, minimum vertex cover (MVC) and maximum-cardinality matching (MCM), for intersection graphs of geometric objects, e.g., disks, rectangles, hypercubes, etc., in $d$-dimensional Euclidean space. We consider the problems in fully dynamic settings, allowing insertions and deletions of objects. We develop a general framework for dynamic MVC in intersection graphs, achieving sublinear amortized update time for most natural families of geometric objects. In particular, we show that - - For a dynamic collection of disks in $\mathbb{R}^2$ or hypercubes in $\mathbb{R}^d$ (for constant $d$), it is possible to maintain a $(1+\varepsilon)$-approximate vertex cover in polylog amortized update time. These results also hold in the bipartite case. - For a dynamic collection of rectangles in $\mathbb{R}^2$, it is possible to maintain a $(\frac{3}{2}+\varepsilon)$-approximate vertex cover in polylog amortized update time. Along the way, we obtain the first near-linear time static algorithms for MVC in the above two cases with the same approximation factors. Next, we turn our attention to the MCM problem. Although our MVC algorithms automatically allow us to approximate the size of the MCM in bipartite geometric intersection graphs, they do not produce a matching. We give another general framework to maintain an approximate maximum matching, and further extend the approach to handle non-bipartite intersection graphs. In particular, we show that - - For a dynamic collection of (bichromatic or monochromatic) disks in $\mathbb{R}^2$ or hypercubes in $\mathbb{R}^d$ (for constant $d$), it is possible to maintain a $(1+\varepsilon)$-approximate matching in polylog amortized update time., Comment: 25 Pages

We present the first fully dynamic connectivity data structures for geometric intersection graphs achieving constant query time and sublinear amortized update time for most types of geometric objects in 2D. Our data structures can answer connectivity queries between two objects, as well as "global" connectivity queries (e.g., deciding whether the entire graph is connected). Previously, the data structure by Afshani and Chan (ESA'06) achieved such bounds only in the special case of axis-aligned line segments or rectangles but did not work for arbitrary line segments or disks, whereas the data structures by Chan, P\u{a}tra\c{s}cu and Roditty (FOCS'08) worked for more general classes of geometric objects but required $n^{\Omega(1)}$ query time and could not handle global connectivity queries. Specifically, we obtain new data structures with $O(1)$ query time and amortized update time near $n^{4/5}$, $n^{7/8}$, and $n^{20/21}$ for axis-aligned line segments, disks, and arbitrary line segments respectively. Besides greatly reducing the query time, our data structures also improve the previous update times for axis-aligned line segments by Afshani and Chan (from near $n^{10/11}$ to $n^{4/5}$) and for disks by Chan, P\u{a}tra\c{s}cu, and Roditty (from near $n^{20/21}$ to $n^{7/8}$).

We present the first optimal randomized algorithm for constructing the order-$k$ Voronoi diagram of $n$ points in two dimensions. The expected running time is $O(n\log n + nk)$, which improves the previous, two-decades-old result of Ramos (SoCG'99) by a $2^{O(\log^*k)}$ factor. To obtain our result, we (i) use a recent decision-tree technique of Chan and Zheng (SODA'22) in combination with Ramos's cutting construction, to reduce the problem to verifying an order-$k$ Voronoi diagram, and (ii) solve the verification problem by a new divide-and-conquer algorithm using planar-graph separators. We also describe a deterministic algorithm for constructing the $k$-level of $n$ lines in two dimensions in $O(n\log n + nk^{1/3})$ time, and constructing the $k$-level of $n$ planes in three dimensions in $O(n\log n + nk^{3/2})$ time. These time bounds (ignoring the $n\log n$ term) match the current best upper bounds on the combinatorial complexity of the $k$-level. Previously, the same time bound in two dimensions was obtained by Chan (1999) but with randomization., Comment: To appear in SODA 2024. 16 pages, 1 figure

We study the classic Text-to-Pattern Hamming Distances problem: given a pattern $P$ of length $m$ and a text $T$ of length $n$, both over a polynomial-size alphabet, compute the Hamming distance between $P$ and $T[i\, .\, . \, i+m-1]$ for every shift $i$, under the standard Word-RAM model with $\Theta(\log n)$-bit words. - We provide an $O(n\sqrt{m})$ time Las Vegas randomized algorithm for this problem, beating the decades-old $O(n \sqrt{m \log m})$ running time [Abrahamson, SICOMP 1987]. We also obtain a deterministic algorithm, with a slightly higher $O(n\sqrt{m}(\log m\log\log m)^{1/4})$ running time. Our randomized algorithm extends to the $k$-bounded setting, with running time $O\big(n+\frac{nk}{\sqrt{m}}\big)$, removing all the extra logarithmic factors from earlier algorithms [Gawrychowski and Uzna\'{n}ski, ICALP 2018; Chan, Golan, Kociumaka, Kopelowitz and Porat, STOC 2020]. - For the $(1+\epsilon)$-approximate version of Text-to-Pattern Hamming Distances, we give an $\tilde{O}(\epsilon^{-0.93}n)$ time Monte Carlo randomized algorithm, beating the previous $\tilde{O}(\epsilon^{-1}n)$ running time [Kopelowitz and Porat, FOCS 2015; Kopelowitz and Porat, SOSA 2018]. Our approximation algorithm exploits a connection with $3$SUM, and uses a combination of Fredman's trick, equality matrix product, and random sampling; in particular, we obtain new results on approximate counting versions of $3$SUM and Exact Triangle, which may be of independent interest. Our exact algorithms use a novel combination of hashing, bit-packed FFT, and recursion; in particular, we obtain a faster algorithm for computing the sumset of two integer sets, in the regime when the universe size is close to quadratic in the number of elements. We also prove a fine-grained equivalence between the exact Text-to-Pattern Hamming Distances problem and a range-restricted, counting version of $3$SUM., Comment: Appeared in FOCS 2023. Abstract shortened to fit arXiv requirements. v2: added reference and discussion related to Lemma 2.2 and Appendix B

In this paper, we provide simpler reductions from Exact Triangle to two important problems in fine-grained complexity: Exact Triangle with Few Zero-Weight $4$-Cycles and All-Edges Sparse Triangle. Exact Triangle instances with few zero-weight $4$-cycles was considered by Jin and Xu [STOC 2023], who used it as an intermediate problem to show $3$SUM hardness of All-Edges Sparse Triangle with few $4$-cycles (independently obtained by Abboud, Bringmann and Fischer [STOC 2023]), which is further used to show $3$SUM hardness of a variety of problems, including $4$-Cycle Enumeration, Offline Approximate Distance Oracle, Dynamic Approximate Shortest Paths and All-Nodes Shortest Cycles. We provide a simple reduction from Exact Triangle to Exact Triangle with few zero-weight $4$-cycles. Our new reduction not only simplifies Jin and Xu's previous reduction, but also strengthens the conditional lower bounds from being under the $3$SUM hypothesis to the even more believable Exact Triangle hypothesis. As a result, all conditional lower bounds shown by Jin and Xu [STOC 2023] and by Abboud, Bringmann and Fischer [STOC 2023] using All-Edges Sparse Triangle with few $4$-cycles as an intermediate problem now also hold under the Exact Triangle hypothesis. We also provide two alternative proofs of the conditional lower bound of the All-Edges Sparse Triangle problem under the Exact Triangle hypothesis, which was originally proved by Vassilevska Williams and Xu [FOCS 2020]. Both of our new reductions are simpler, and one of them is also deterministic -- all previous reductions from Exact Triangle or 3SUM to All-Edges Sparse Triangle (including P\u{a}tra\c{s}cu's seminal work [STOC 2010]) were randomized., Comment: To appear in SOSA 2024

We study the time complexity of the discrete $k$-center problem and related (exact) geometric set cover problems when $k$ or the size of the cover is small. We obtain a plethora of new results: - We give the first subquadratic algorithm for rectilinear discrete 3-center in 2D, running in $\widetilde{O}(n^{3/2})$ time. - We prove a lower bound of $\Omega(n^{4/3-\delta})$ for rectilinear discrete 3-center in 4D, for any constant $\delta>0$, under a standard hypothesis about triangle detection in sparse graphs. - Given $n$ points and $n$ weighted axis-aligned unit squares in 2D, we give the first subquadratic algorithm for finding a minimum-weight cover of the points by 3 unit squares, running in $\widetilde{O}(n^{8/5})$ time. We also prove a lower bound of $\Omega(n^{3/2-\delta})$ for the same problem in 2D, under the well-known APSP Hypothesis. For arbitrary axis-aligned rectangles in 2D, our upper bound is $\widetilde{O}(n^{7/4})$. - We prove a lower bound of $\Omega(n^{2-\delta})$ for Euclidean discrete 2-center in 13D, under the Hyperclique Hypothesis. This lower bound nearly matches the straightforward upper bound of $\widetilde{O}(n^\omega)$, if the matrix multiplication exponent $\omega$ is equal to 2. - We similarly prove an $\Omega(n^{k-\delta})$ lower bound for Euclidean discrete $k$-center in $O(k)$ dimensions for any constant $k\ge 3$, under the Hyperclique Hypothesis. This lower bound again nearly matches known upper bounds if $\omega=2$. - We also prove an $\Omega(n^{2-\delta})$ lower bound for the problem of finding 2 boxes to cover the largest number of points, given $n$ points and $n$ boxes in 12D. This matches the straightforward near-quadratic upper bound., Comment: Accepted to ICALP'23

In SoCG 2022, Conroy and T\'oth presented several constructions of sparse, low-hop spanners in geometric intersection graphs, including an $O(n\log n)$-size 3-hop spanner for $n$ disks (or fat convex objects) in the plane, and an $O(n\log^2 n)$-size 3-hop spanner for $n$ axis-aligned rectangles in the plane. Their work left open two major questions: (i) can the size be made closer to linear by allowing larger constant stretch? and (ii) can near-linear size be achieved for more general classes of intersection graphs? We address both questions simultaneously, by presenting new constructions of constant-hop spanners that have almost linear size and that hold for a much larger class of intersection graphs. More precisely, we prove the existence of an $O(1)$-hop spanner for arbitrary string graphs with $O(n\alpha_k(n))$ size for any constant $k$, where $\alpha_k(n)$ denotes the $k$-th function in the inverse Ackermann hierarchy. We similarly prove the existence of an $O(1)$-hop spanner for intersection graphs of $d$-dimensional fat objects with $O(n\alpha_k(n))$ size for any constant $k$ and $d$. We also improve on some of Conroy and T\'oth's specific previous results, in either the number of hops or the size: we describe an $O(n\log n)$-size 2-hop spanner for disks (or more generally objects with linear union complexity) in the plane, and an $O(n\log n)$-size 3-hop spanner for axis-aligned rectangles in the plane. Our proofs are all simple, using separator theorems, recursion, shifted quadtrees, and shallow cuttings.

In this paper we carefully combine Fredman's trick [SICOMP'76] and Matou\v{s}ek's approach for dominance product [IPL'91] to obtain powerful results in fine-grained complexity: - Under the hypothesis that APSP for undirected graphs with edge weights in $\{1, 2, \ldots, n\}$ requires $n^{3-o(1)}$ time (when $\omega=2$), we show a variety of conditional lower bounds, including an $n^{7/3-o(1)}$ lower bound for unweighted directed APSP and an $n^{2.2-o(1)}$ lower bound for computing the Minimum Witness Product between two $n \times n$ Boolean matrices, even if $\omega=2$, improving upon their trivial $n^2$ lower bounds. Our techniques can also be used to reduce the unweighted directed APSP problem to other problems. In particular, we show that (when $\omega = 2$), if unweighted directed APSP requires $n^{2.5-o(1)}$ time, then Minimum Witness Product requires $n^{7/3-o(1)}$ time. - We show that, surprisingly, many central problems in fine-grained complexity are equivalent to their natural counting versions. In particular, we show that Min-Plus Product and Exact Triangle are subcubically equivalent to their counting versions, and 3SUM is subquadratically equivalent to its counting version. - We obtain new algorithms using new variants of the Balog-Szemer\'edi-Gowers theorem from additive combinatorics. For example, we get an $O(n^{3.83})$ time deterministic algorithm for exactly counting the number of shortest paths in an arbitrary weighted graph, improving the textbook $\widetilde{O}(n^{4})$ time algorithm. We also get faster algorithms for 3SUM in preprocessed universes, and deterministic algorithms for 3SUM on monotone sets in $\{1, 2, \ldots, n\}^d$., Comment: To appear at STOC'23

We present a (combinatorial) algorithm with running time close to $O(n^d)$ for computing the minimum directed $L_\infty$ Hausdorff distance between two sets of $n$ points under translations in any constant dimension $d$. This substantially improves the best previous time bound near $O(n^{5d/4})$ by Chew, Dor, Efrat, and Kedem from more than twenty years ago. Our solution is obtained by a new generalization of Chan's algorithm [FOCS'13] for Klee's measure problem. To complement this algorithmic result, we also prove a nearly matching conditional lower bound close to $\Omega(n^d)$ for combinatorial algorithms, under the Combinatorial $k$-Clique Hypothesis., Comment: To appear in SoCG 2023

We consider problems related to finding short cycles, small cliques, small independent sets, and small subgraphs in geometric intersection graphs. We obtain a plethora of new results. For example: * For the intersection graph of $n$ line segments in the plane, we give algorithms to find a 3-cycle in $O(n^{1.408})$ time, a size-3 independent set in $O(n^{1.652})$ time, a 4-clique in near-$O(n^{24/13})$ time, and a $k$-clique (or any $k$-vertex induced subgraph) in $O(n^{0.565k+O(1)})$ time for any constant $k$; we can also compute the girth in near-$O(n^{3/2})$ time. * For the intersection graph of $n$ axis-aligned boxes in a constant dimension $d$, we give algorithms to find a 3-cycle in $O(n^{1.408})$ time for any $d$, a 4-clique (or any 4-vertex induced subgraph) in $O(n^{1.715})$ time for any $d$, a size-4 independent set in near-$O(n^{3/2})$ time for any $d$, a size-5 independent set in near-$O(n^{4/3})$ time for $d=2$, and a $k$-clique (or any $k$-vertex induced subgraph) in $O(n^{0.429k+O(1)})$ time for any $d$ and any constant $k$. * For the intersection graph of $n$ fat objects in any constant dimension $d$, we give an algorithm to find any $k$-vertex (non-induced) subgraph in $O(n\log n)$ time for any constant $k$, generalizing a result by Kaplan, Klost, Mulzer, Roddity, Seiferth, and Sharir (1999) for 3-cycles in 2D disk graphs. A variety of techniques is used, including geometric range searching, biclique covers, "high-low" tricks, graph degeneracy and separators, and shifted quadtrees. We also prove a near-$\Omega(n^{4/3})$ conditional lower bound for finding a size-4 independent set for boxes., Comment: To appear in SODA 2023

We revisit the classic problem of simplex range searching and related problems in computational geometry. We present a collection of new results which improve previous bounds by multiple logarithmic factors that were caused by the use of multi-level data structures. Highlights include the following: $\bullet$ For a set of $n$ points in a constant dimension $d$, we give data structures with $O(n^d)$ (or slightly better) space that can answer simplex range counting queries in optimal $O(\log n)$ time and simplex range reporting queries in optimal $O(\log n + k)$ time, where $k$ denotes the output size. For semigroup range searching, we obtain $O(\log n)$ query time with $O(n^d\mathop{\rm polylog}n)$ space. Previous data structures with similar space bounds by Matou\v{s}ek from nearly three decades ago had $O(\log^{d+1}n)$ or $O(\log^{d+1}n + k)$ query time. $\bullet$ For a set of $n$ simplices in a constant dimension $d$, we give data structures with $O(n)$ space that can answer stabbing counting queries (counting the number of simplices containing a query point) in $O(n^{1-1/d})$ time, and stabbing reporting queries in $O(n^{1-1/d}+k)$ time. Previous data structures had extra $\log^d n$ factors in space and query time. $\bullet$ For a set of $n$ (possibly intersecting) line segments in 2D, we give a data structure with $O(n)$ space that can answer ray shooting queries in $O(\sqrt{n})$ time. This improves Wang's recent data structure [SoCG'20] with $O(n\log n)$ space and $O(\sqrt{n}\log n)$ query time., Comment: Updated abstract metadata formatting. Accepted in SODA'23

The $3$SUM hypothesis, the APSP hypothesis and SETH are the three main hypotheses in fine-grained complexity. So far, within the area, the first two hypotheses have mainly been about integer inputs in the Word RAM model of computation. The "Real APSP" and "Real $3$SUM" hypotheses, which assert that the APSP and $3$SUM hypotheses hold for real-valued inputs in a reasonable version of the Real RAM model, are even more believable than their integer counterparts. Under the very believable hypothesis that at least one of the Integer $3$SUM hypothesis, Integer APSP hypothesis or SETH is true, Abboud, Vassilevska W. and Yu [STOC 2015] showed that a problem called Triangle Collection requires $n^{3-o(1)}$ time on an $n$-node graph. Our main result is a nontrivial lower bound for a slight generalization of Triangle Collection, called All-Color-Pairs Triangle Collection, under the even more believable hypothesis that at least one of the Real $3$SUM, the Real APSP, and the OV hypotheses is true. Combined with slight modifications of prior reductions, we obtain polynomial conditional lower bounds for problems such as the (static) ST-Max Flow problem and dynamic Max Flow, now under the new weaker hypothesis. Our main result is built on the following two lines of reductions. * Real APSP and Real $3$SUM hardness for the All-Edges Sparse Triangle problem. Prior reductions only worked from the integer variants of these problems. * Real APSP and OV hardness for a variant of the Boolean Matrix Multiplication problem. Along the way we show that Triangle Collection is equivalent to a simpler restricted version of the problem, simplifying prior work. Our techniques also have other interesting implications, such as a super-linear lower bound of Integer All-Numbers $3$SUM based on the Real $3$SUM hypothesis, and a tight lower bound for a string matching problem based on the OV hypothesis., Comment: To appear at STOC'22. Abstract shortened to fit arXiv requirements

Given a set of points $P$ and a set of regions $\mathcal{O}$, an incidence is a pair $(p,o ) \in P \times \mathcal{O}$ such that $p \in o$. We obtain a number of new results on a classical question in combinatorial geometry: What is the number of incidences (under certain restrictive conditions)? We prove a bound of $O\bigl( k n(\log n/\log\log n)^{d-1} \bigr)$ on the number of incidences between $n$ points and $n$ axis-parallel boxes in $\mathbb{R}^d$, if no $k$ boxes contain $k$ common points, that is, if the incidence graph between the points and the boxes does not contain $K_{k,k}$ as a subgraph. This new bound improves over previous work, by Basit, Chernikov, Starchenko, Tao, and Tran (2021), by more than a factor of $\log^d n$ for $d >2$. Furthermore, it matches a lower bound implied by the work of Chazelle (1990), for $k=2$, thus settling the question for points and boxes. We also study several other variants of the problem. For halfspaces, using shallow cuttings, we get a linear bound in two and three dimensions. We also present linear (or near linear) bounds for shapes with low union complexity, such as pseudodisks and fat triangles.

We revisit Hopcroft's problem and related fundamental problems about geometric range searching. Given $n$ points and $n$ lines in the plane, we show how to count the number of point-line incidence pairs or the number of point-above-line pairs in $O(n^{4/3})$ time, which matches the conjectured lower bound and improves the best previous time bound of $n^{4/3}2^{O(\log^*n)}$ obtained almost 30 years ago by Matou\v{s}ek. We describe two interesting and different ways to achieve the result: the first is randomized and uses a new 2D version of fractional cascading for arrangements of lines; the second is deterministic and uses decision trees in a manner inspired by the sorting technique of Fredman (1976). The second approach extends to any constant dimension. Many consequences follow from these new ideas: for example, we obtain an $O(n^{4/3})$-time algorithm for line segment intersection counting in the plane, $O(n^{4/3})$-time randomized algorithms for bichromatic closest pair and Euclidean minimum spanning tree in three or four dimensions, and a randomized data structure for halfplane range counting in the plane with $O(n^{4/3})$ preprocessing time and space and $O(n^{1/3})$ query time., Comment: Appeared in SODA 2022

Geometric set cover is a classical problem in computational geometry, which has been extensively studied in the past. In the dynamic version of the problem, points and ranges may be inserted and deleted, and our goal is to efficiently maintain a set cover solution (satisfying certain quality requirement). In this paper, we give a plethora of new dynamic geometric set cover data structures in 1D and 2D, which significantly improve and extend the previous results: 1. The first data structure for $(1+\varepsilon)$-approximate dynamic interval set cover with polylogarithmic amortized update time. Specifically, we achieve an update time of $O(\log^3 n/\varepsilon)$, improving the $O(n^\delta/\varepsilon)$ bound of Agarwal et al. [SoCG'20], where $\delta>0$ denotes an arbitrarily small constant. 2. A data structure for $O(1)$-approximate dynamic unit-square set cover with $2^{O(\sqrt{\log n})}$ amortized update time, substantially improving the $O(n^{1/2+\delta})$ update time of Agarwal et al. [SoCG'20]. 3. A data structure for $O(1)$-approximate dynamic square set cover with $O(n^{1/2+\delta})$ randomized amortized update time, improving the $O(n^{2/3+\delta})$ update time of Chan and He [SoCG'21]. 4. A data structure for $O(1)$-approximate dynamic 2D halfplane set cover with $O(n^{17/23+\delta})$ randomized amortized update time. The previous solution for halfplane set cover by Chan and He [SoCG'21] is slower and can only report the size of the approximate solution. 5. The first sublinear results for the \textit{weighted} version of dynamic geometric set cover. Specifically, we give a data structure for $(3+o(1))$-approximate dynamic weighted interval set cover with $2^{O(\sqrt{\log n \log\log n})}$ amortized update time and a data structure for $O(1)$-approximate dynamic weighted unit-square set cover with $O(n^\delta)$ amortized update time., Comment: to appear in SODA 2022

Given a set of $n$ integer-valued coin types and a target value $t$, the well-known change-making problem asks for the minimum number of coins that sum to $t$, assuming an unlimited number of coins in each type. In the more general all-targets version of the problem, we want the minimum number of coins summing to $j$, for every $j=0,\ldots,t$. For example, the textbook dynamic programming algorithms can solve the all-targets problem in $O(nt)$ time. Recently, Chan and He (SOSA'20) described a number of $O(t\,\textrm{polylog}\,t)$-time algorithms for the original (single-target) version of the change-making problem, but not the all-targets version. We obtain a number of new results on change-making and related problems, including: 1. A new algorithm for the all-targets change-making problem with running time $\tilde{O}(t^{4/3})$, improving a previous $\tilde{O}(t^{3/2})$-time algorithm. 2. A very simple $\tilde{O}(u^2+t)$-time algorithm for the all-targets change-making problem, where $u$ denotes the maximum coin value. The analysis of the algorithm uses a theorem of Erd\H{o}s and Graham (1972) on the Frobenius problem. This algorithm can be extended to solve the all-capacities version of the unbounded knapsack problem (for integer item weights bounded by $u$). 3. For the original (single-target) coin changing problem, we describe a simple modification of one of Chan and He's algorithms that runs in $\tilde{O}(u)$ time (instead of $\tilde{O}(t)$). 4. For the original (single-capacity) unbounded knapsack problem, we describe a simple algorithm that runs in $\tilde{O}(nu)$ time, improving previous near-$u^2$-time algorithms. 5. We also observe how one of our ideas implies a new result on the minimum word break problem, an optimization version of a string problem studied by Bringmann et al. (FOCS'17), generalizing change-making (which corresponds to the unary special case)., Comment: This is the full version of our ESA 2020 paper

We revisit a classical problem in computational geometry: finding the largest-volume axis-aligned empty box (inside a given bounding box) amidst $n$ given points in $d$ dimensions. Previously, the best algorithms known have running time $O(n\log^2n)$ for $d=2$ (by Aggarwal and Suri [SoCG'87]) and near $n^d$ for $d\ge 3$. We describe faster algorithms with running time (i) $O(n2^{O(\log^*n)}\log n)$ for $d=2$, (ii) $O(n^{2.5+o(1)})$ time for $d=3$, and (iii) $\widetilde{O}(n^{(5d+2)/6})$ time for any constant $d\ge 4$. To obtain the higher-dimensional result, we adapt and extend previous techniques for Klee's measure problem to optimize certain objective functions over the complement of a union of orthants., Comment: full version of a SoCG 2021 paper

We study geometric set cover problems in dynamic settings, allowing insertions and deletions of points and objects. We present the first dynamic data structure that can maintain an $O(1)$-approximation in sublinear update time for set cover for axis-aligned squares in 2D. More precisely, we obtain randomized update time $O(n^{2/3+\delta})$ for an arbitrarily small constant $\delta>0$. Previously, a dynamic geometric set cover data structure with sublinear update time was known only for unit squares by Agarwal, Chang, Suri, Xiao, and Xue [SoCG 2020]. If only an approximate size of the solution is needed, then we can also obtain sublinear amortized update time for disks in 2D and halfspaces in 3D. As a byproduct, our techniques for dynamic set cover also yield an optimal randomized $O(n\log n)$-time algorithm for static set cover for 2D disks and 3D halfspaces, improving our earlier $O(n\log n(\log\log n)^{O(1)})$ result [SoCG 2020].

APSP with small integer weights in undirected graphs [Seidel'95, Galil and Margalit'97] has an $\tilde{O}(n^\omega)$ time algorithm, where $\omega<2.373$ is the matrix multiplication exponent. APSP in directed graphs with small weights however, has a much slower running time that would be $\Omega(n^{2.5})$ even if $\omega=2$ [Zwick'02]. To understand this $n^{2.5}$ bottleneck, we build a web of reductions around directed unweighted APSP. We show that it is fine-grained equivalent to computing a rectangular Min-Plus product for matrices with integer entries; the dimensions and entry size of the matrices depend on the value of $\omega$. As a consequence, we establish an equivalence between APSP in directed unweighted graphs, APSP in directed graphs with small $(\tilde{O}(1))$ integer weights, All-Pairs Longest Paths in DAGs with small weights, approximate APSP with additive error $c$ in directed graphs with small weights, for $c\le \tilde{O}(1)$ and several other graph problems. We also provide fine-grained reductions from directed unweighted APSP to All-Pairs Shortest Lightest Paths (APSLP) in undirected graphs with $\{0,1\}$ weights and $\#_{\text{mod}\ c}$APSP in directed unweighted graphs (computing counts mod $c$). We complement our hardness results with new algorithms. We improve the known algorithms for APSLP in directed graphs with small integer weights and for approximate APSP with sublinear additive error in directed unweighted graphs. Our algorithm for approximate APSP with sublinear additive error is optimal, when viewed as a reduction to Min-Plus product. We also give new algorithms for variants of #APSP in unweighted graphs, as well as a near-optimal $\tilde{O}(n^3)$-time algorithm for the original #APSP problem in unweighted graphs. Our techniques also lead to a simpler alternative for the original APSP problem in undirected graphs with small integer weights., Comment: abstract shortened to fit arXiv requirements

We improve the running times of $O(1)$-approximation algorithms for the set cover problem in geometric settings, specifically, covering points by disks in the plane, or covering points by halfspaces in three dimensions. In the unweighted case, Agarwal and Pan [SoCG 2014] gave a randomized $O(n\log^4 n)$-time, $O(1)$-approximation algorithm, by using variants of the multiplicative weight update (MWU) method combined with geometric data structures. We simplify the data structure requirement in one of their methods and obtain a deterministic $O(n\log^3 n\log\log n)$-time algorithm. With further new ideas, we obtain a still faster randomized $O(n\log n(\log\log n)^{O(1)})$-time algorithm. For the weighted problem, we also give a randomized $O(n\log^4n\log\log n)$-time, $O(1)$-approximation algorithm, by simple modifications to the MWU method and the quasi-uniform sampling technique.

We present a number of new results about range searching for colored (or "categorical") data: 1. For a set of $n$ colored points in three dimensions, we describe randomized data structures with $O(n\mathop{\rm polylog}n)$ space that can report the distinct colors in any query orthogonal range (axis-aligned box) in $O(k\mathop{\rm polyloglog} n)$ expected time, where $k$ is the number of distinct colors in the range, assuming that coordinates are in $\{1,\ldots,n\}$. Previous data structures require $O(\frac{\log n}{\log\log n} + k)$ query time. Our result also implies improvements in higher constant dimensions. 2. Our data structures can be adapted to halfspace ranges in three dimensions (or circular ranges in two dimensions), achieving $O(k\log n)$ expected query time. Previous data structures require $O(k\log^2n)$ query time. 3. For a set of $n$ colored points in two dimensions, we describe a data structure with $O(n\mathop{\rm polylog}n)$ space that can answer colored "type-2" range counting queries: report the number of occurrences of every distinct color in a query orthogonal range. The query time is $O(\frac{\log n}{\log\log n} + k\log\log n)$, where $k$ is the number of distinct colors in the range. Naively performing $k$ uncolored range counting queries would require $O(k\frac{\log n}{\log\log n})$ time. Our data structures are designed using a variety of techniques, including colored variants of randomized incremental construction (which may be of independent interest), colored variants of shallow cuttings, and bit-packing tricks., Comment: full version of a SoCG'20 paper

We revisit a fundamental problem in string matching: given a pattern of length m and a text of length n, both over an alphabet of size $\sigma$, compute the Hamming distance between the pattern and the text at every location. Several $(1+\epsilon)$-approximation algorithms have been proposed in the literature, with running time of the form $O(\epsilon^{-O(1)}n\log n\log m)$, all using fast Fourier transform (FFT). We describe a simple $(1+\epsilon)$-approximation algorithm that is faster and does not need FFT. Combining our approach with additional ideas leads to numerous new results: - We obtain the first linear-time approximation algorithm; the running time is $O(\epsilon^{-2}n)$. - We obtain a faster exact algorithm computing all Hamming distances up to a given threshold k; its running time improves previous results by logarithmic factors and is linear if $k\le\sqrt m$. - We obtain approximation algorithms with better $\epsilon$-dependence using rectangular matrix multiplication. The time-bound is $\~O(n)$ when the pattern is sufficiently long: $m\ge \epsilon^{-28}$. Previous algorithms require $\~O(\epsilon^{-1}n)$ time. - When k is not too small, we obtain a truly sublinear-time algorithm to find all locations with Hamming distance approximately (up to a constant factor) less than k, in $O((n/k^{\Omega(1)}+occ)n^{o(1)})$ time, where occ is the output size. The algorithm leads to a property tester, returning true if an exact match exists and false if the Hamming distance is more than $\delta m$ at every location, running in $\~O(\delta^{-1/3}n^{2/3}+\delta^{-1}n/m)$ time. - We obtain a streaming algorithm to report all locations with Hamming distance approximately less than k, using $\~O(\epsilon^{-2}\sqrt k)$ space. Previously, streaming algorithms were known for the exact problem with \~O(k) space or for the approximate problem with $\~O(\epsilon^{-O(1)}\sqrt m)$ space.

In SODA'99, Chan introduced a simple type of planar straight-line upward order-preserving drawings of binary trees, known as LR drawings: such a drawing is obtained by picking a root-to-leaf path, drawing the path as a straight line, and recursively drawing the subtrees along the paths. Chan proved that any binary tree with $n$ nodes admits an LR drawing with $O(n^{0.48})$ width. In SODA'17, Frati, Patrignani, and Roselli proved that there exist families of $n$-node binary trees for which any LR drawing has $\Omega(n^{0.418})$ width. In this note, we improve Chan's upper bound to $O(n^{0.437})$ and Frati et al.'s lower bound to $\Omega(n^{0.429})$., Comment: Appears in the Proceedings of the 28th International Symposium on Graph Drawing and Network Visualization (GD 2020)

$\renewcommand{\Re}{\mathbb{R}}$ We develop a general randomized technique for solving "implic it" linear programming problems, where the collection of constraints are defined implicitly by an underlying ground set of elements. In many cases, the structure of the implicitly defined constraints can be exploited in order to obtain efficient linear program solvers. We apply this technique to obtain near-optimal algorithms for a variety of fundamental problems in geometry. For a given point set $P$ of size $n$ in $\Re^d$, we develop algorithms for computing geometric centers of a point set, including the centerpoint and the Tukey median, and several other more involved measures of centrality. For $d=2$, the new algorithms run in $O(n\log n)$ expected time, which is optimal, and for higher constant $d>2$, the expected time bound is within one logarithmic factor of $O(n^{d-1})$, which is also likely near optimal for some of the problems., Comment: This paper is a merge of two conference papers that were published sixteen years apart. The first paper appeared in SODA 2004, and the second paper (which can be viewed as an applications paper of the first paper) appeared in SoCG 2020

In this paper we study two geometric data structure problems in the special case when input objects or queries are fat rectangles. We show that in this case a significant improvement compared to the general case can be achieved. We describe data structures that answer two- and three-dimensional orthogonal range reporting queries in the case when the query range is a \emph{fat} rectangle. Our two-dimensional data structure uses $O(n)$ words and supports queries in $O(\log\log U +k)$ time, where $n$ is the number of points in the data structure, $U$ is the size of the universe and $k$ is the number of points in the query range. Our three-dimensional data structure needs $O(n\log^{\varepsilon}U)$ words of space and answers queries in $O(\log \log U + k)$ time. We also consider the rectangle stabbing problem on a set of three-dimensional fat rectangles. Our data structure uses $O(n)$ space and answers stabbing queries in $O(\log U\log\log U +k)$ time., Comment: extended version of a WADS'19 paper

Range closest-pair (RCP) search is a range-search variant of the classical closest-pair problem, which aims to store a given set $S$ of points into some space-efficient data structure such that when a query range $Q$ is specified, the closest pair in $S \cap Q$ can be reported quickly. RCP search has received attention over years, but the primary focus was only on $\mathbb{R}^2$. In this paper, we study RCP search in higher dimensions. We give the first nontrivial RCP data structures for orthogonal, simplex, halfspace, and ball queries in $\mathbb{R}^d$ for any constant $d$. Furthermore, we prove a conditional lower bound for orthogonal RCP search for $d \geq 3$.

We present new results on a number of fundamental problems about dynamic geometric data structures: 1. We describe the first fully dynamic data structures with sublinear amortized update time for maintaining (i) the number of vertices or the volume of the convex hull of a 3D point set, (ii) the largest empty circle for a 2D point set, (iii) the Hausdorff distance between two 2D point sets, (iv) the discrete 1-center of a 2D point set, (v)the number of maximal (i.e., skyline) points in a 3D point set. The update times are near $n^{11/12}$ for (i) and (ii), $n^{7/8}$ for (iii) and (iv), and $n^{2/3}$ for (v). Previously, sublinear bounds were known only for restricted `semi-online' settings [Chan, SODA 2002]. 2. We slightly improve previous fully dynamic data structures for answering extreme point queries for the convex hull of a 3D point set and nearest neighbor search for a 2D point set. The query time is $O(\log^2n)$, and the amortized update time is $O(\log^4n)$ instead of $O(\log^5n)$ [Chan, SODA 2006; Kaplan et al., SODA 2017]. 3. We also improve previous fully dynamic data structures for maintaining the bichromatic closest pair between two 2D point sets and the diameter of a 2D point set. The amortized update time is $O(\log^4n)$ instead of $O(\log^7n)$ [Eppstein 1995; Chan, SODA 2006; Kaplan et al., SODA 2017].

Given a set of $n$ points in the plane, and a parameter $k$, we consider the problem of computing the minimum (perimeter or area) axis-aligned rectangle enclosing $k$ points. We present the first near quadratic time algorithm for this problem, improving over the previous near-$O(n^{5/2})$-time algorithm by Kaplan etal [KRS17]. We provide an almost matching conditional lower bound, under the assumption that $(\min,+)$-convolution cannot be solved in truly subquadratic time. Furthermore, we present a new reduction (for either perimeter or area) that can make the time bound sensitive to $k$, giving near $O(n k) $ time. We also present a near linear time $(1+\varepsilon)$-approximation algorithm to the minimum area of the optimal rectangle containing $k$ points. In addition, we study related problems including the $3$-sided, arbitrarily oriented, weighted, and subset sum versions of the problem.

For any constant $d$ and parameter $\varepsilon > 0$, we show the existence of (roughly) $1/\varepsilon^d$ orderings on the unit cube $[0,1)^d$, such that any two points $p,q\in [0,1)^d$ that are close together under the Euclidean metric are "close together" in one of these linear orderings in the following sense: the only points that could lie between $p$ and $q$ in the ordering are points with Euclidean distance at most $\varepsilon\| p - q \|$ from $p$ or $q$. These orderings are extensions of the $\mathcal{Z}$-order, and they can be efficiently computed. Functionally, the orderings can be thought of as a replacement to quadtrees and related structures (like well-separated pair decompositions). We use such orderings to obtain surprisingly simple algorithms for a number of basic problems in low-dimensional computational geometry, including (i) dynamic approximate bichromatic closest pair, (ii) dynamic spanners, (iii) dynamic approximate minimum spanning trees, (iv) static and dynamic fault-tolerant spanners, and (v) approximate nearest neighbor search., Comment: Appeared in ITCS 2019, and to appear in SICOMP

We initiate the study of the following natural geometric optimization problem. The input is a set of axis-aligned rectangles in the plane. The objective is to find a set of horizontal line segments of minimum total length so that every rectangle is stabbed by some line segment. A line segment stabs a rectangle if it intersects its left and its right boundary. The problem, which we call Stabbing, can be motivated by a resource allocation problem and has applications in geometric network design. To the best of our knowledge, only special cases of this problem have been considered so far. Stabbing is a weighted geometric set cover problem, which we show to be NP-hard. A constrained variant of Stabbing turns out to be even APX-hard. While for general set cover the best possible approximation ratio is $\Theta(\log n)$, it is an important field in geometric approximation algorithms to obtain better ratios for geometric set cover problems. Chan et al. [SODA'12] generalize earlier results by Varadarajan [STOC'10] to obtain sub-logarithmic performances for a broad class of weighted geometric set cover instances that are characterized by having low shallow-cell complexity. The shallow-cell complexity of Stabbing instances, however, can be high so that a direct application of the framework of Chan et al. gives only logarithmic bounds. We still achieve a constant-factor approximation by decomposing general instances into what we call laminar instances that have low enough complexity. Our decomposition technique yields constant-factor approximations also for the variant where rectangles can be stabbed by horizontal and vertical segments and for two further geometric set cover problems.

In this work, we present a collection of new results on two fundamental problems in geometric data structures: orthogonal point location and rectangle stabbing. -We give the first linear-space data structure that supports 3-d point location queries on $n$ disjoint axis-aligned boxes with optimal $O\left( \log n\right)$ query time in the (arithmetic) pointer machine model. This improves the previous $O\left( \log^{3/2} n \right)$ bound of Rahul [SODA 2015]. We similarly obtain the first linear-space data structure in the I/O model with optimal query cost, and also the first linear-space data structure in the word RAM model with sub-logarithmic query time. -We give the first linear-space data structure that supports 3-d $4$-sided and $5$-sided rectangle stabbing queries in optimal $O(\log_wn+k)$ time in the word RAM model. We similarly obtain the first optimal data structure for the closely related problem of 2-d top-$k$ rectangle stabbing in the word RAM model, and also improved results for 3-d 6-sided rectangle stabbing. For point location, our solution is simpler than previous methods, and is based on an interesting variant of the van Emde Boas recursion, applied in a round-robin fashion over the dimensions, combined with bit-packing techniques. For rectangle stabbing, our solution is a variant of Alstrup, Brodal, and Rauhe's grid-based recursive technique (FOCS 2000), combined with a number of new ideas., Comment: Full version of the ICALP'18 paper

We consider the problem of computing Shapley values for points in the plane, where each point is interpreted as a player, and the value of a coalition is defined by the area of usual geometric objects, such as the convex hull or the minimum axis-parallel bounding box. For sets of $n$ points in the plane, we show how to compute in roughly $O(n^{3/2})$ time the Shapley values for the area of the minimum axis-parallel bounding box and the area of the union of the rectangles spanned by the origin and the input points. When the points form an increasing or decreasing chain, the running time can be improved to near-linear. In all these cases, we use linearity of the Shapley values and algebraic methods. We also show that Shapley values for the area and the perimeter of the convex hull or the minimum enclosing disk can be computed in $O(n^2)$ and $O(n^3)$ time, respectively. In this case the computation is closely related to the model of stochastic point sets considered in computational geometry, but here we have to consider random insertion orders of the points instead of a probabilistic existence of points., Comment: new set of authors; several improvements with respect to v1; 31 pages; 21 figures

We make progress on a number of open problems concerning the area requirement for drawing trees on a grid. We prove that 1. every tree of size $n$ (with arbitrarily large degree) has a straight-line drawing with area $n2^{O(\sqrt{\log\log n\log\log\log n})}$, improving the longstanding $O(n\log n)$ bound; 2. every tree of size $n$ (with arbitrarily large degree) has a straight-line upward drawing with area $n\sqrt{\log n}(\log\log n)^{O(1)}$, improving the longstanding $O(n\log n)$ bound; 3. every binary tree of size $n$ has a straight-line orthogonal drawing with area $n2^{O(\log^*n)}$, improving the previous $O(n\log\log n)$ bound by Shin, Kim, and Chwa (1996) and Chan, Goodrich, Kosaraju, and Tamassia (1996); 4. every binary tree of size $n$ has a straight-line order-preserving drawing with area $n2^{O(\log^*n)}$, improving the previous $O(n\log\log n)$ bound by Garg and Rusu (2003); 5. every binary tree of size $n$ has a straight-line orthogonal order-preserving drawing with area $n2^{O(\sqrt{\log n})}$, improving the $O(n^{3/2})$ previous bound by Frati (2007)., Comment: full version of SoCG 2018 paper

For most algorithms dealing with sets of points in the plane, the only relevant information carried by the input is the combinatorial configuration of the points: the orientation of each triple of points in the set (clockwise, counterclockwise, or collinear). This information is called the order type of the point set. In the dual, realizable order types and abstract order types are combinatorial analogues of line arrangements and pseudoline arrangements. Too often in the literature we analyze algorithms in the real-RAM model for simplicity, putting aside the fact that computers as we know them cannot handle arbitrary real numbers without some sort of encoding. Encoding an order type by the integer coordinates of some realizing point set is known to yield doubly exponential coordinates in some cases. Other known encodings can achieve quadratic space or fast orientation queries, but not both. In this contribution, we give a compact encoding for abstract order types that allows efficient query of the orientation of any triple: the encoding uses O(n^2) bits and an orientation query takes O(log n) time in the word-RAM model. This encoding is space-optimal for abstract order types. We show how to shorten the encoding to O(n^2 (loglog n)^2 / log n) bits for realizable order types, giving the first subquadratic encoding for those order types with fast orientation queries. We further refine our encoding to attain O(log n/loglog n) query time without blowing up the space requirement. In the realizable case, we show that all those encodings can be computed efficiently. Finally, we generalize our results to the encoding of point configurations in higher dimension.

Let $T$ be an $n$-node tree of maximum degree 4, and let $P$ be a set of $n$ points in the plane with no two points on the same horizontal or vertical line. It is an open question whether $T$ always has a planar drawing on $P$ such that each edge is drawn as an orthogonal path with one bend (an "L-shaped" edge). By giving new methods for drawing trees, we improve the bounds on the size of the point set $P$ for which such drawings are possible to: $O(n^{1.55})$ for maximum degree 4 trees; $O(n^{1.22})$ for maximum degree 3 (binary) trees; and $O(n^{1.142})$ for perfect binary trees. Drawing ordered trees with L-shaped edges is harder---we give an example that cannot be done and a bound of $O(n \log n)$ points for L-shaped drawings of ordered caterpillars, which contrasts with the known linear bound for unordered caterpillars., Comment: Appears in the Proceedings of the 25th International Symposium on Graph Drawing and Network Visualization (GD 2017)