The union volume estimation problem asks to (1±ε)-approximate the volume of the union of n given objects X₁,…,X_n ⊂ ℝ^d. In their seminal work in 1989, Karp, Luby, and Madras solved this problem in time O(n/ε²) in an oracle model where each object X_i can be accessed via three types of queries: obtain the volume of X_i, sample a random point from X_i, and test whether X_i contains a given point x. This running time was recently shown to be optimal [Bringmann, Larsen, Nusser, Rotenberg, and Wang, SoCG'25]. In another line of work, Meel, Vinodchandran, and Chakraborty [PODS'21] designed algorithms that read the objects in one pass using polylogarithmic time per object and polylogarithmic space; this can be phrased as a dynamic algorithm supporting insertions of objects for union volume estimation in the oracle model. In this paper, we study algorithms for union volume estimation in the oracle model that support both insertions and deletions of objects. We obtain the following results: 1) an algorithm supporting insertions and deletions in polylogarithmic update and query time and linear space (this is the first such dynamic algorithm, even for 2D triangles); 2) an algorithm supporting insertions and suffix queries (which generalizes the sliding window setting) in polylogarithmic update and query time and space; 3) an algorithm supporting insertions and deletions of convex bodies of constant dimension in polylogarithmic update and query time and space.

We consider the problem of triangulating a polygon with n vertices and h holes, or relatedly the problem of computing the trapezoidal decomposition of a collection of h disjoint simple polygonal chains with n vertices total. Clarkson, Cole, and Tarjan (1992) and Seidel (1991) gave randomized algorithms running in O(nlog^*n + hlog h) time, while Bar-Yehuda and Chazelle (1994) described deterministic algorithms running in O(n+hlog^{1+ε}h) or O((n+hlog h)log log h) time, for an arbitrarily small positive constant ε. No improvements have been reported since. We describe a new O(n+hlog h)-time algorithm, which is optimal and deterministic. More generally, when the given polygonal chains are not necessarily simple and may intersect each other, we show how to compute their trapezoidal decomposition (and in particular, compute all intersections) in optimal O(n+hlog h) deterministic time when the number of intersections is at most n^{1-ε}. To obtain these results, Chazelle’s linear-time algorithm for triangulating a simple polygon is used as a black box.

Recent research on computing the diameter of geometric intersection graphs has made significant strides, primarily focusing on the 2D case [Duraj et al., 2024; Hsien-Chih Chang et al., 2024; Chan et al., 2025] where truly subquadratic-time algorithms were given for simple objects such as unit-disks and (axis-aligned) squares. However, in three or higher dimensions, there is no known truly subquadratic-time algorithm for any intersection graph of non-trivial objects, even basic ones such as unit balls or (axis-aligned) unit cubes. This was partially explained by the pioneering work of Bringmann et al. [Karl Bringmann et al., 2022] which gave several truly subquadratic lower bounds, notably for unit balls or unit cubes in 3D when the graph diameter Δ is at least Ω(log n), hinting at a pessimistic outlook for the complexity of the diameter problem in higher dimensions. In this paper, we substantially extend the landscape of diameter computation for objects in three and higher dimensions, giving a few positive results. Our highlighted findings include: 1) A truly subquadratic-time algorithm for deciding if the diameter of unit cubes in 3D is at most 3 (Diameter-3 hereafter), the first algorithm of its kind for objects in 3D or higher dimensions. Our algorithm is based on a novel connection to pseudolines, which is of independent interest. 2) A truly subquadratic time lower bound for Diameter-3 of unit balls in 3D under the Orthogonal Vector (OV) hypothesis, giving the first separation between unit balls and unit cubes in the small diameter regime. Previously, computing the diameter for both objects was known to be quadratic hard when the diameter is Ω(log n) [Karl Bringmann et al., 2022]. 3) A near-linear-time algorithm for Diameter-2 of unit cubes in 3D, generalizing the previous result for unit squares in 2D [Karl Bringmann et al., 2022]. 4) A truly subquadratic-time algorithm and lower bound for Diameter-2 and Diameter-3 of rectangular boxes (of arbitrary dimension and sizes), respectively.

We present an algorithm that computes the girth of the intersection graph of n given line segments in the plane in O(n^1.483) expected time. This is the first such algorithm with O(n^{3/2-ε}) running time for a positive constant ε, and makes progress towards an open question posed by Chan (SODA 2023). The main techniques include (i) the usage of recent subcubic algorithms for bounded-difference min-plus matrix multiplication, and (ii) an interesting variant of the planar graph separator theorem. The result extends to intersection graphs of connected algebraic curves or semialgebraic sets of constant description complexity.

Computing the diameter of the intersection graphs of objects is a basic problem in computational geometry. Previous works showed that the complexity of computing the diameter mainly depends on the object types: for unit disks and squares in 2D, the problem is solvable in truly subquadratic time [Chan et al., 2025], while for other objects, including unit segments and equilateral triangles in 2D or unit balls and axis-parallel unit cubes in 3D, there is no truly subquadratic time algorithm under the Orthogonal Vector (OV) hypothesis [Bringmann et al., 2022]. We undertake a comprehensive study of computing the diameter of geometric intersection graphs for various types of objects. We discover many new irregularities, showing that the landscape is extremely nuanced: the source of hardness is a combination of the object type, the true diameter value, and how the objects intersect with each other. Our highlighted results for the 2D case include: 1) The diameter of non-degenerate, axis-aligned line segments can be computed in truly subquadratic time. Previous hardness result [Bringmann et al., 2022] for line segments applies only to degenerate instances. On the other hand, for the degenerate case, we show that a truly subquadratic time algorithm exists when the true diameter is constant. 2) An almost-linear-time algorithm for unit-square graphs of constant diameter. Previous algorithms [Duraj et al., 2024; Chan et al., 2025] rely on succinct representation assuming bounded VC-dimension; for such a strategy Ω(n^{7/4}) time is an inherent barrier. 3) An Õ(n^{4/3})-time algorithm to decide if the diameter of a unit-disk graph is at most 2. This improves upon the recent algorithm with running time Õ(n^{2-1/9}) [Chan et al., 2025]. 4) Deciding if the diameter of intersection graphs of fat triangles or line segments is at most 2 is truly subquadratic-hard under fine-grained complexity assumptions. Previous lower bounds [Bringmann et al., 2022] only hold when deciding if diameter is at most 3. Our findings are presented in a pair of papers. This paper focuses solely on the 2D case, while the companion paper is devoted to higher-dimensional cases.

We investigate algorithms with predictions in computational geometry, specifically focusing on the basic problem of computing 2D Delaunay triangulations. Given a set P of n points in the plane and a triangulation G that serves as a "prediction" of the Delaunay triangulation, we would like to use G to compute the correct Delaunay triangulation DT(P) more quickly when G is "close" to DT(P). We obtain a variety of results of this type, under different deterministic and probabilistic settings, including the following: 1) Define D to be the number of edges in G that are not in DT(P). We present a deterministic algorithm to compute DT(P) from G in O(n + Dlog³ n) time, and a randomized algorithm in O(n+Dlog n) expected time, the latter of which is optimal in terms of D. 2) Let R be a random subset of the edges of DT(P), where each edge is chosen independently with probability ρ. Suppose G is any triangulation of P that contains R. We present an algorithm to compute DT(P) from G in O(nlog log n + nlog(1/ρ)) time with high probability. 3) Define d_{vio} to be the maximum number of points of P strictly inside the circumcircle of a triangle in G (the number is 0 if G is equal to DT(P)). We present a deterministic algorithm to compute DT(P) from G in O(nlog^*n + nlog d_{vio}) time. We also obtain results in similar settings for related problems such as 2D Euclidean minimum spanning trees, and hope that our work will open up a fruitful line of future research.

We reexamine the classical subset sum problem: given a set \(X\) of \(n\) positive integers and a number \(t\), decide whether there exists a subset of \(X\) that sums to \(t\); or more generally, compute the set out of all numbers \(y \in \{0,\ldots,t\}\) for which there exists a subset of \(X\) that sums to \(y\). Standard dynamic programming solves the problem in \(O(tn)\) time. In SODA’17, two papers appeared giving the current best deterministic and randomized algorithms, ignoring polylogarithmic factors: Koiliaris and Xu’s deterministic algorithm runs in \(\widetilde{O}(t\sqrt{n})\) time, while Bringmann’s randomized algorithm runs in \(\widetilde{O}(t)\) time. We present the first deterministic algorithm running in \(\widetilde{O}(t)\) time.

In a series of papers, Avraham, Filtser, Kaplan, Katz, and Sharir (SoCG'14), Kaplan, Katz, Saban, and Sharir (ESA'23), and Katz, Saban, and Sharir (ESA'24) studied a class of geometric optimization problems -- including reverse shortest path in unweighted and weighted unit-disk graphs, discrete Fréchet distance with one-sided shortcuts, and reverse shortest path in visibility graphs on 1.5-dimensional terrains -- for which standard parametric search does not work well due to a lack of efficient parallel algorithms for the corresponding decision problems. The best currently known algorithms for all the above problems run in $O^*(n^{6/5})=O^*(n^{1.2})$ time (ignoring subpolynomial factors), and they were obtained using a technique called \emph{shrink-and-bifurcate}. We improve the running time to $\tilde{O}(n^{8/7}) \approx O(n^{1.143})$ for these problems. Furthermore, specifically for reverse shortest path in unweighted unit-disk graphs, we improve the running time further to $\tilde{O}(n^{9/8})=\tilde{O}(n^{1.125})$.

In this paper we study the hypergraph Zarankiewicz’s problem in a geometric setting - for r-partite intersection hypergraphs of families of geometric objects. Our main results are essentially sharp bounds for families of axis-parallel boxes in ℝ^d and families of pseudo-discs. For axis-parallel boxes, we obtain the sharp bound O_{d,t}(n^{r-1}((log n)/(log log n))^{d-1}). The best previous bound was larger by a factor of about (log n)^{d(2^{r-1}-2)}. For pseudo-discs, we obtain the bound O_t(n^{r-1}(log n)^{r-2}), which is sharp up to logarithmic factors. As this hypergraph has no algebraic structure, no improvement of Erdős' 60-year-old O(n^{r-(1/t^{r-1})}) bound was known for this setting. Futhermore, even in the special case of discs for which the semialgebraic structure can be used, our result improves the best known result by a factor of Ω̃(n^{(2r-2)/(3r-2)}). To obtain our results, we use the recently improved results for the graph Zarankiewicz’s problem in the corresponding settings, along with a variety of combinatorial and geometric techniques, including shallow cuttings, biclique covers, transversals, and planarity.

We give the first truly subquadratic time algorithm, with ${O^{\ast}}\left( {{n^{2 - 1/18}}} \right)$ running time, for computing the diameter of an n-vertex unit-disk graph, resolving a central open problem in the literature. Our result is obtained as an instance of a general framework, applicable to different graph families and distance problems. Surprisingly, our framework completely bypasses sublinear separators (or r-divisions) which were used in all previous algorithms. Instead, we use low-diameter decompositions in their most elementary form. We also exploit bounded VC-dimension of set systems associated with the input graph, as well as new ideas on geometric data structures. Among the numerous applications of the general framework, we obtain:1)An $\tilde O\left( {m{n^{1 - 1/(2d)}}} \right)$ time algorithm for computing the diameter of m-edge sparse unweighted graphs with constant VC-dimension d. The previously known algorithms by Ducoffe, Habib, and Viennot [SODA 2019] and Duraj, Konieczny, and Potępa [ESA 2024] are truly subquadratic only when the diameter is a small polynomial. Our result thus generalizes truly subquadratic time algorithms known for planar and minor-free graphs (in fact, it slightly improves the previous time bound for minor-free graphs).2)An $\tilde O\left( {{n^{2 - 1/12}}} \right)$ time algorithm for computing the diameter of intersection graphs of axis-aligned squares with arbitrary size. The best-known algorithm by Duraj, Konieczny, and Potępa [ESA 2024] only works for unit squares and is only truly subquadratic in the low-diameter regime.3)The first algorithms with truly subquadratic complexity for other distance-related problems, including all-vertex eccentricities, Wiener index, and exact distance oracles. In particular, we obtain the first exact distance oracle with truly subquadratic space and $\tilde O(1)$ query time for any sparse graph with bounded VC-dimension, again generalizing previous results for planar and minor-free graphs.

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:

We present the first space-efficient, fully dynamic streaming algorithm for computing a constant-factor approximation of the maximum independent set size of n axis-aligned rectangles in two dimensions. For an arbitrarily small constant δ > 0, our algorithm obtains an O((1/δ)²) approximation and requires O(U^δ polylog n) space and update time with high probability, assuming that coordinates are integers bounded by U. We also obtain a similar result for fat objects in any constant dimension. This extends recent non-streaming algorithms by Bhore and Chan from SODA'25, and also greatly extends previous streaming results, which were limited to special types of geometric objects such as one-dimensional intervals and unit disks.

Abstract. 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 requirements) for the dynamic problem instance. In this paper, we give a plethora of new dynamic geometric set cover data structures in one and two dimensions, which significantly improve and extend the previous results. Our results include the following: (1) The first data structure for [Formula: see text]-approximate dynamic interval set cover with polylogarithmic amortized update time. Specifically, we achieve an update time of [Formula: see text], improving the [Formula: see text] bound of Agarwal et al. [ Proceedings of the 36 th Symposium on Computational Geometry, LIPIcs. Leibniz Int. Proc. Inform. 164, Schloss Dagstuhl - Leibniz Center for Informatics, 2020, 27; ACM Trans. Algorithms, 18 (2022), 40], where [Formula: see text] denotes an arbitrarily small constant. (2) A data structure for [Formula: see text]-approximate dynamic unit-square set cover with [Formula: see text] amortized update time, substantially improving the [Formula: see text] update time of Agarwal et al. (3) A data structure for [Formula: see text]-approximate dynamic square set cover with [Formula: see text] randomized amortized update time, improving the [Formula: see text] update time of Chan and He [ Proceedings of the 36 th Symposium on Computational Geometry, LIPIcs. Leibniz Int. Proc. Inform. 164, Schloss Dagstuhl - Leibniz Center for Informatics, 2020; J. Comput. Geom., 13 (2022), pp. 90–114]. (4) A data structure for [Formula: see text]-approximate dynamic two-dimensional half-plane set cover with [Formula: see text] randomized amortized update time. The previous solution for a half-plane set cover by Chan and He [ Proceedings of the 37 th International Symposium on Computational Geometry, LIPIcs. Leibniz Int. Proc. Inform. 189, Schloss Dagstuhl - Leibniz Center for Informatics, 2021, 25; J. Comput. Geom., 13 (2022), pp. 90–114] is slower and can only report the size of the approximate solution. (5) The first sublinear results for the weighted version of dynamic geometric set cover. Specifically, we give a data structure for [Formula: see text]-approximate dynamic weighted interval set cover with [Formula: see text] amortized update time and a data structure for [Formula: see text]-approximate dynamic weighted unit-square set cover with [Formula: see text] amortized update time.

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+ε}) preprocessing time and space, so that we can count the number of ranges containing a query point in O(n^{1/4+ε}) time, for an arbitrarily small constant ε > 0. (The query time bound is likely close to tight for this space bound.) 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+ε}) preprocessing time and space, so that we can find the first arc hit by a query (straight-line) ray in O(n^{1/4+ε}) time. (The query bound is again likely close to tight for this space bound, and they improve a result by Ezra and Sharir with near n^{3/2} space and near √n query 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+ε}) 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+ε}) time. In particular, this implies an O(n^{3/2+ε})-time algorithm for counting intersections between two sets of n algebraic arcs in 2D. (This generalizes a classical O(n^{3/2+ε})-time algorithm for circular arcs by Agarwal and Sharir from SoCG 1991.)

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(α(n)\log n)$-approximation algorithm for segments, where $α(n)$ is the inverse Ackermann function, and an $O(\log n)$-approximation algorithm for disks.

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 $Ω(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).

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ătraşcu and Roditty (FOCS'08) worked for more general classes of geometric objects but required $n^{Ω(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ătraş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 2O(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 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šek [ 58 ]. We describe two interesting and different ways to achieve the result: The first is randomized and uses a new two-dimensional 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 [42]. 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 distance selection in the plane and 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.

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 $Ω(n^d)$ for combinatorial algorithms, under the Combinatorial $k$-Clique Hypothesis.

In SoCG 2022, Conroy and Tóth 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α_k(n))$ size for any constant $k$, where $α_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α_k(n))$ size for any constant $k$ and $d$. We also improve on some of Conroy and Tóth'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.

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 \ldots 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\left(n \sqrt{m}(\log m \log \log m)^{1 / 4}\right)$ running time. Our randomized algorithm extends to the k-bounded setting, with running time $O\left(n+\frac{n k}{\sqrt{m}}\right)$, removing all the extra logarithmic factors from earlier algorithms [Gawrychowski and Uznanski, ICALP 2018; Chan, Golan, Kociumaka, Kopelowitz and Porat, STOC 2020].•For the $(1+\varepsilon)$-approximate version of Text-to-Pattern Hamming Distances, we give an $\widetilde{O}\left(\varepsilon^{-0.93} n\right)$ time Monte Carlo randomized algorithm (where $\widetilde{O}$ hides poly-logarithmic factors), beating the previous $\widetilde{O}\left(\varepsilon^{-1} n\right)$ running time [Kopelowitz and Porat, FOCS 2015; Kopelowitz and Porat, SOSA 2018].Our approximation algorithm exploits a connection with 3SUM, 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.

Despite numerous results about the list decoding of Hamming-metric codes, development of list decoding on rank-metric codes is not as rapid as its counterpart. The bound of list decoding obeys the Gilbert-Varshamov bound in both the metrics. In the case of the Hamming-metric, the Gilbert-Varshamov bound is a trade-off among rate, decoding radius and alphabet size, while in the case of the rank-metric, the Gilbert-Varshamov bound is a trade-off among rate, decoding radius and column-to-row ratio (i.e., the ratio between the numbers of columns and rows). Hence, alphabet size and column-to-row ratio play a similar role for list decodability in each metric. In the case of the Hamming-metric, it is more challenging to list decode codes over smaller alphabets. In contrast, in the case of the rank-metric, it is more difficult to list decode codes with large column-to-row ratio. In particular, it is extremely difficult to list decode square matrix rank-metric codes (i.e., the column-to-row ratio is equal to 1). The main purpose of this paper is to explicitly construct a class of rank-metric codes 𝒞 of rate R with the column-to-row ratio up to 2/3 and efficiently list decode these codes with decoding radius beyond the decoding radius (1-R)/2 (note that (1-R)/2 is at least half of relative minimum distance δ). In literature, the largest column-to-row ratio of rank-metric codes that can be efficiently list decoded beyond half of minimum distance is 1/2. Thus, it is greatly desired to efficiently design list decoding algorithms for rank-metric codes with the column-to-row ratio bigger than 1/2 or even close to 1. Our key idea is to compress an element of the field F_qⁿ into a smaller F_q-subspace via a linearized polynomial. Thus, the column-to-row ratio gets increased at the price of reducing the code rate. Our result shows that the compression technique is powerful and it has not been employed in the topic of list decoding of both the Hamming and rank metrics. Apart from the above algebraic technique, we follow some standard techniques to prune down the list. The algebraic idea enables us to pin down the message into a structured subspace of dimension linear in the number n of columns. This "periodic" structure allows us to pre-encode the message to prune down the list.

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:

Given a set of points P and a set of regions 𝒪, an incidence is a pair ( p , θ) ∈ P × 𝒪 such that p ∈ ø. 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 ( kn (log n / log log n ) d -1 ) on the number of incidences between n points and n axis-parallel boxes in ℝ 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. * The full version of the paper can be accessed at https://arxiv.org/abs/2112.14829

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:

In this paper we carefully combine Fredman’s trick [SICOMP’76] and Matoušek’s approach for dominance product [IPL’91] to obtain powerful results in fine-grained complexity.

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) for the dynamic problem instance. 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. Our results include the following: The first data structure for (1 + ∊)-approximate dynamic interval set cover with polylogarithmic amortized update time. Specifically, we achieve an update time of O(log3 n/∊), improving the O(nδ/∊) bound of Agarwal et al. [SoCG'20], where δ > 0 denotes an arbitrarily small constant. A data structure for O(1)-approximate dynamic unit-square set cover with amortized update time, substantially improving the O(n1/2+δ) update time of Agarwal et al. [SoCG'20]. A data structure for O(1)-approximate dynamic square set cover with O(n1/2+δ) randomized amortized update time, improving the O(n2/3+δ) update time of Chan and He [SoCG'21]. A data structure for O(1)-approximate dynamic 2D halfplane set cover with O(n17/23+δ) 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. The first sublinear results for the weighted version of dynamic geometric set cover. Specifically, we give a data structure for (3 + o(1))-approximate dynamic weighted interval set cover with amortized update time and a data structure for O(1)-approximate dynamic weighted unit-square set cover with O(nδ) amortized update time.

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(n4/3) time, which matches the conjectured lower bound and improves the best previous time bound of n4/32O(log∗ n) obtained almost 30 years ago by Matouš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(n4/3)-time algorithm for line segment intersection counting in the plane, O(n4/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(n4/3) preprocessing time and space and O(n1/3) query time.

The 3SUM hypothesis, the All-Pairs Shortest Paths (APSP) hypothesis and the Strong Exponential Time Hypothesis are the three main hypotheses in the area of 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 3SUM” hypotheses, which assert that the APSP and 3SUM hypotheses hold for real-valued inputs in a reasonable version of the Real RAM model, are even more believable than their integer counterparts.

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 or the perimeter 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 can be computed in $$O(n^2)$$ time, while for the minimum enclosing disk it takes $$O(n^3)$$ time. These problems are 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.

We develop a general randomized technique for solving implicit 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 used to obtain faster 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 $\mathbb{R}^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.

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(nlog²n) for d = 2 (by Aggarwal and Suri [SoCG'87]) and near n^d for d ≥ 3. We describe faster algorithms with running time - O(n2^{O(log^*n)}log n) for d = 2, - O(n^{2.5+o(1)}) time for d = 3, and - Õ(n^{(5d+2)/6}) time for any constant d ≥ 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.

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+δ})$ for an arbitrarily small constant $δ>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].

Given a graph with n vertices and real edge weights in [0,1], we investigate an approximate version of the standard all-pairs shortest paths (APSP) problem where distances are estimated with additive error at most ε. Yuster (2012) introduced this natural variant of approximate APSP, and presented an algorithm for directed graphs running in Õ(n^{(3+ω)/2}) ≤ O(n^{2.687}) time for an arbitrarily small constant ε > 0, where ω denotes the matrix multiplication exponent. We give a faster algorithm for undirected graphs running in Õ(n^{(3+ω²)/(ω+1)}) ≤ O(n^{2.559}) time for any constant ε > 0. If ω = 2, the time bound is Õ(n^{7/3}), matching a previous result for undirected graphs by Dor, Halperin, and Zwick (2000) which only guaranteed additive error at most 2.

In the colored orthogonal range reporting problem, we want a data structure for storing n colored points so that given a query axis-aligned rectangle, we can report the distinct colors among the points inside the rectangle. This natural problem has been studied in a series of papers, but most prior work focused on the static case. In this paper, we give a dynamic data structure in the 2D case which can answer queries in O(log^{1+o(1)} n + klog^{1/2+o(1)}n) time, where k denotes the output size (the number of distinct colors in the query range), and which can support insertions and deletions in O(log^{2+o(1)}n) time (amortized) in the standard RAM model. This is the first fully dynamic structure with polylogarithmic update time whose query cost per color reported is sublogarithmic (near √{log n}). We also give an alternative data structure with O(log^{1+o(1)} n + klog^{3/4+o(1)}n) query time and O(log^{3/2+o(1)}n) update time (amortized). We also mention extensions to higher constant dimensions.

All-Pairs Shortest Paths (APSP) is one of the most well studied problems in graph algorithms. This paper studies several variants of APSP in unweighted graphs or graphs with small integer weights. APSP with small integer weights in undirected graphs [Seidel'95, Galil and Margalit'97] has an Õ(n^ω) time algorithm, where ω < 2.373 is the matrix multiplication exponent. APSP in directed graphs with small weights however, has a much slower running time that would be Ω(n^{2.5}) even if ω = 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 ω. As a consequence, we establish an equivalence between APSP in directed unweighted graphs, APSP in directed graphs with small (Õ(1)) integer weights, All-Pairs Longest Paths in DAGs with small weights, cRed-APSP in undirected graphs with small weights, for any c ≥ 2 (computing all-pairs shortest path distances among paths that use at most c red edges), #_{≤ c}APSP in directed graphs with small weights (counting the number of shortest paths for each vertex pair, up to c), and approximate APSP with additive error c in directed graphs with small weights, for c ≤ Õ(1). 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 #_{mod c}APSP in directed unweighted graphs (computing counts mod c), thus showing that unless the current algorithms for APSP in directed unweighted graphs can be improved substantially, these problems need at least Ω(n^{2.528}) time. We complement our hardness results with new algorithms. We improve the known algorithms for APSLP in directed graphs with small integer weights (previously studied by Zwick [STOC'99]) and for approximate APSP with sublinear additive error in directed unweighted graphs (previously studied by Roditty and Shapira [ICALP'08]). 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 (such as #_{≤ U}APSP and #_{mod U}APSP for U ≤ n^{Õ(1)}) in unweighted graphs, as well as a near-optimal Õ(n³)-time algorithm for the original #APSP problem in unweighted graphs (when counts may be exponentially large). This also implies an Õ(n³)-time algorithm for Betweenness Centrality, improving on the previous Õ(n⁴) running time for the problem. Our techniques also lead to a simpler alternative to Shoshan and Zwick’s algorithm [FOCS'99] for the original APSP problem in undirected graphs with small integer weights.

We revisit classical problems about searching in totally monotone and Monge matrices, which have many applications in computational geometry and other areas. We present a number of new results, including the following: A randomized algorithm that finds the row minima in an n × n Monge staircase matrix in O(n) expected time; this improves a longstanding O(nα(n)) bound by Klawe and Kleitman (1990) for totally monotone staircase matrices. A randomized algorithm that reports the K smallest elements (in an arbitrary order) in an n × n Monge (complete or staircase) matrix in O(n + K) expected time; this improves and extends a previous O(n + K log n) algorithm by Kravets and Park [SODA'90]. A randomized algorithm that reports the K smallest elements (in an arbitrary order) in an n × n totally monotone (complete) matrix in O(n + K log∗ n) expected time. A randomized algorithm that reports the ki smallest elements in the i-th row, for every i, in an n × n totally monotone (complete) matrix in O((n + K) log∗ n) expected time, where K = Σi ki. A randomized algorithm that finds the row minima in an n × n totally monotone “v-matrix” in O(nα(n) log∗ n log log n) expected time; this answers an open question by Klawe [SODA'90]. The log∗ n factor can be removed in the Monge case.

We revisit classical problems about searching in totally monotone matrices, which have many applications in computational geometry and other areas. In a companion paper, we gave new (near-)linear-time algorithms for a number of such problems. In the present paper, we describe new sub-quadratic results for more basic problems, including the following: A randomized algorithm to select the K-th smallest element in an n × n totally monotone matrix in O(n4/3 polylog n) expected time; this improves previous O(n3/2 polylog n) algorithms by Alon and Azar [SODA'92], Mansour et al. (1993), and Agarwal and Sen (1996). A near-matching lower bound of Ω(n4/3) for the problem (which holds even for Monge matrices). A similar result for selecting the ki-th smallest in the i-th row for all i. In the case when all ki's are the same, an improvement of the running time to O(n6/5 polylog n). Variants of all these bounds that are sensitive to K (or Σi ki). These matrix searching problems are intimately related to problems about arrangements of pseudo-lines. In particular, our selection algorithm implies an O(n4/3 polylog n) algorithm for computing incidences between n points and n pseudo-lines in the plane. This improves, extends, and simplifies a previous method by Agarwal and Sharir [SODA'02].

We show how to solve all-pairs shortest paths on n nodes in deterministic n 3> /2> Ω ( √ log n ) time, and how to count the pairs of orthogonal vectors among n 0−1 vectors in d = c log n dimensions in deterministic n 2−1/ O (log c ) time. These running times essentially match the best known randomized algorithms of Williams [46] and Abboud, Williams, and Yu [8], respectively, and the ability to count was open even for randomized algorithms. By reductions, these two results yield faster deterministic algorithms for many other problems. Our techniques can also be used to deterministically count k -satisfiability ( k -SAT) assignments on n variable formulas in 2 n - n / O ( k ) time, roughly matching the best known running times for detecting satisfiability and resolving an open problem of Santhanam [24]. A key to our constructions is an efficient way to deterministically simulate certain probabilistic polynomials critical to the algorithms of prior work, carefully applying small-biased sets and modulus-amplifying polynomials.

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⁴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³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⁴n 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.

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,…,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 polylog t)-time algorithms for the original (single-target) version of the change-making problem, but not the all-targets version. In this paper, we obtain a number of new results on change-making and related problems: - We present a new algorithm for the all-targets change-making problem with running time Õ(t^{4/3}), improving a previous Õ(t^{3/2})-time algorithm. - We present a very simple Õ(u²+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ő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). - For the original (single-target) coin changing problem, we describe a simple modification of one of Chan and He’s algorithms that runs in Õ(u) time (instead of Õ(t)). - For the original (single-capacity) unbounded knapsack problem, we describe a simple algorithm that runs in Õ(nu) time, improving previous near-u²-time algorithms. - 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).

We present a deterministic, truly subquadratic algorithm for offline (1 + ε)-approximate nearest or farthest neighbor search (in particular, the closest pair or diameter problem) in Hamming space in any dimension d ≤ nδ, for a sufficiently small constant δ > 0. The running time of the algorithm is roughly for nearest neighbors, or for farthest. The algorithm follows from a simple combination of expander walks, Chebyshev polynomials, and rectangular matrix multiplication. We also show how to eliminate errors in the previous Monte Carlo randomized algorithm of Alman, Chan, and Williams [FOCS’16] for offline approximate nearest or farthest neighbors, and obtain a Las Vegas randomized algorithm with expected running time . Finally, we note a simplification of Alman, Chan, and Williams' method and obtain a slightly improved Monte Carlo randomized algorithm with running time . As one application, we obtain improved deterministic and randomized (1 + ε)-approximation algorithms for MAX-SAT.

Range searching on categorical, or “colored”, data has been studied extensively for over two decades. In this paper, we obtain the current best results for perhaps the most basic, and most often studied, version of the geometric problem: colored orthogonal range reporting. Given n colored points in two-dimensional space [U]2, we present a data structure with O(n log3/4+ε n) space, for an arbitrarily small constant ε > 0, so that all k distinct colors in any axis-aligned query rectangle can be reported in (optimal) O (log log U + k) time; this is the first method to break the O(n log n) space barrier. In three dimensions, we present a data structure with O(n log9/5+ε n) space and O(log n/ log log n + k) time; this improves the previous space bound of O(n log4 n).

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 σ, compute the Hamming distance (i.e., the number of mismatches) between the pattern and the text at every location. Several randomized (1+ε)-approximation algorithms have been proposed in the literature (e.g., by Karloff (Inf. Proc. Lett., 1993), Indyk (FOCS 1998), and Kopelowitz and Porat (SOSA 2018)), with running time of the form O(ε−O(1) nlognlogm), all using fast Fourier transform (FFT). We describe a simple randomized (1+ε)-approximation algorithm that is faster and does not need FFT. Combining our approach with additional ideas leads to numerous new results (all Monte-Carlo randomized) in different settings:

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^{5/6}$$ for (iii) and (iv), and $$n^{2/3}$$ for (v). Previously, sublinear bounds were known only for restricted “semi-online” settings (Chan in SIAM J. Comput. 32(3), 700–716 (2003)). (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 ^2\!n)$$ , and the amortized update time is $$O(\log ^4\!n)$$ instead of $$O(\log ^5\!n)$$ (Chan in J. ACM 57(3), # 16 (2010); Kaplan et al. in 28th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 2495–2504. SIAM, Philadelphia (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 ^4\!n)$$ instead of $$O(\log ^7\!n)$$ (Eppstein in Discrete Comput. Geom. 13(1), 111–122 (1995); Chan in J. ACM 57(3), # 16 (2010); Kaplan et al. in 28th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 2495–2504. SIAM, Philadelphia (2017)).

For any constant $d$ and parameter $\varepsilon \in (0,1/2]$, we show the existence of (roughly) $1/\varepsilon^d$ orderings on the unit cube $[0,1)^d$ such that for any two points $p, q\in [0,1)^d$ close together under the Euclidean metric, there is a linear ordering in which all points between $p$ and $q$ in the ordering are “close” to $p$ or $q$. More precisely, the only points that could lie between $p$ and $q$ in the ordering are points with Euclidean distance at most $\varepsilon\left\| {p} - {q} \right\|$ from either $p$ or $q$. These orderings are extensions of the 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.

This article presents an algorithm that solves the 3SUM problem for n real numbers in O (( n 2 / log 2 n )(log log n ) O (1) ) time, improving previous solutions by about a logarithmic factor. Our framework for shaving off two logarithmic factors can be applied to other problems, such as (median,+)-convolution/matrix multiplication and algebraic generalizations of 3SUM. This work also obtains the first subquadratic results on some 3SUM-hard problems in computational geometry, for example, deciding whether (the interiors of) a constant number of simple polygons have a common intersection.

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 et al. [Haim Kaplan et al., 2017]. 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+epsilon)-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 epsilon > 0, we show the existence of (roughly) 1/epsilon^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 epsilon | p - q | from p or q. These orderings are extensions of the 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.

For many 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 a 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 with word size w >= log n. This encoding is space-optimal for abstract order types. We show how to shorten the encoding to O(n^2 {(log log 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/log log n) query time at the expense of a negligibly larger 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.

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).

We present the first near-linear-time (1 + epsilon)-approximation algorithm for the diameter of a weighted unit-disk graph of n vertices, running in O(n log^2 n) time, for any constant epsilon>0, improving the near-O(n^{3/2})-time algorithm of Gao and Zhang [STOC 2003]. Using similar ideas, we can construct a (1+epsilon)-approximate distance oracle for weighted unit-disk graphs with O(1) query time, with a similar improvement in the preprocessing time, from near O(n^{3/2}) to O(n log^3 n). We also obtain new results for a number of other related problems in the weighted unit-disk graph metric, such as the radius and bichromatic closest pair. As a further application, we use our new distance oracle, along with additional ideas, to solve the (1 + epsilon)-approximate all-pairs bounded-leg shortest paths problem for a set of n planar points, with near O(n^{2.579}) preprocessing time, O(n^2 log n) space, and O(log{log n}) query time, improving thus the near-cubic preprocessing bound by Roditty and Segal [SODA 2007].

In this paper we consider the following modification of the iterative search problem. We are given a tree $T$, so that a dynamic catalog $C(v)$ is associated with every tree node $v$. For any $x$ and for any node-to-root path $π$ in $T$, we must find the predecessor of $x$ in $\cup_{v\in π} C(v)$. We present a linear space dynamic data structure that supports such queries in $O(t(n)+|π|)$ time, where $t(n)$ is the time needed to search in one catalog and $|π|$ denotes the number of nodes on path $π$. We also consider the reporting variant of this problem, in which for any $x_1$, $x_2$ and for any path $π'$ all elements of $\cup_{v\in π'} (C(v)\cap [x_1,x_2])$ must be reported; here $π'$ denotes a path between an arbitrary node $v_0$ and its ancestor $v_1$. We show that such queries can be answered in $O(t(n)+|π'|+ k)$ time, where $k$ is the number of elements in the answer. To illustrate applications of our technique, we describe the first dynamic data structures for the stabbing-max problem, the horizontal point location problem, and the orthogonal line-segment intersection problem with optimal $O(\log n/\log \log n)$ query time and poly-logarithmic update time.

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.

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. 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.

We present an algorithm that solves the 3SUM problem for n real numbers in O((n2 / log2 n)(log log n)O(1)) time, improving previous solutions by about a logarithmic factor. Our framework for shaving off two logarithmic factors can be applied to other problems, such as (median,+)-convolution/matrix multiplication and algebraic generalizations of 3SUM. We also obtain the first subquadratic results on some 3SUM-hard problems in computational geometry, for example, deciding whether (the interiors of) a constant number of simple polygons have a common intersection.

We describe a fully dynamic linear-space data structure for point location in connected planar subdivisions, or more generally vertical ray shooting among nonintersecting line segments, that supports queries in $O(\log n(\log\log n)^2)$ time and updates in $O(\log n\log\log n)$ time. This is the first data structure that achieves close to logarithmic query and update time simultaneously, ignoring $\log\log n$ factors. We further show how to reduce the query time to $O(\log n\log\log n)$ in the RAM model with randomization. Alternatively, the query time can be lowered to $O(\log n)$ if the update time is increased to $O(\log^{1+\varepsilon}n)$ for any constant $\varepsilon>0$, or vice versa.

Chazelle and Matoušek [ J. Algorithms , 1996] presented a derandomization of Clarkson’s sampling-based algorithm [ J. ACM , 1995] for solving linear programs with n constraints and d variables in d (7+ o (1)) d n deterministic time. The time bound can be improved to d (5+ o (1)) d n with subsequent work by Brönnimann, Chazelle, and Matoušek [ SIAM J. Comput. , 1999]. We first point out a much simpler derandomization of Clarkson’s algorithm that avoids ε-approximations and runs in d (3+ o (1)) d n time. We then describe a few additional ideas that eventually improve the deterministic time bound to d (1/2+ o (1)) d n .

We consider the classical selection and sorting problems in a model where the initial permutation of the input has to be restored after completing thecomputation. Such algorithms are useful for designing space-efficient algorithms, when one encounters subproblems that have to be solved by subroutines. It is important that these subroutines leave the array in its original state after they finish so that the computation can be properly resumed. Algorithms in this model can also be relevant for saving communication time, in case the data is distributed among several machines and would need to be copied to further machines for execution of the subroutine. Although the requirement of the restoration is stringent compared to the classicalversions of the problems, this model is more relaxed than a read-only memory where the input elements are not allowed to be moved within the input array. We first show that for a sequence of n integers, selection (finding the median or more generally the k -th smallest element for a given k ) can be done in O ( n ) time using O (lg n ) words 1 of extra space in this model. In contrast, no linear-time selection algorithm is known that uses polylogarithmic space in the read-only memory model. For sorting n integers in this model, we first present an O ( n lg n )-time algorithm using O (lg n ) words of extra space that outputs (in a write only tape) the given sequence in sorted order while restoring the order of the original input in the input tape. When the universe size U is polynomial in n , we give a faster O ( n )-time algorithm (analogous to radix sort) that uses O ( n ε ) words of extra space for an arbitrarily small constant ε > 0. More generally, we show how to match the time bound of any word-RAM integer sorting algorithms using O ( n ε ) words of extra space. In sharp contrast, there is an Ω ( n 2 / S )-time lower bound for integer sorting using O ( S ) bits of space in the read-only memory model. Extension of our results to arbitrary input types beyond integers is not possible: for “indivisible” input elements, we can prove the same Ω ( n 2 / S ) lower bound for sorting in our model. We also describe space-efficient algorithms to count the number of inversions in a given sequence in this model. En route, we develop linear-time in-place algorithms to extract leading bits of the input array and to compress and decompress strings with low entropy; these techniques may be of independent interest.

We apply the polynomial method - specifically, Chebyshev polynomials - to obtain a number of new results on geometric approximation algorithms in low constant dimensions. For example, we give an algorithm for constructing epsilon-kernels (coresets for approximate width and approximate convex hull) in close to optimal time O(n + (1/epsilon)^{(d-1)/2}), up to a small near-(1/epsilon)^{3/2} factor, for any d-dimensional n-point set. We obtain an improved data structure for Euclidean *approximate nearest neighbor search* with close to O(n log n + (1/epsilon)^{d/4} n) preprocessing time and O((1/epsilon)^{d/4} log n) query time. We obtain improved approximation algorithms for discrete Voronoi diagrams, diameter, and bichromatic closest pair in the L_s-metric for any even integer constant s >= 2. The techniques are general and may have further applications.

We revisit the orthogonal range searching problem and the exact l_infinity nearest neighbor searching problem for a static set of n points when the dimension d is moderately large. We give the first data structure with near linear space that achieves truly sublinear query time when the dimension is any constant multiple of log n. Specifically, the preprocessing time and space are O(n^{1+delta}) for any constant delta>0, and the expected query time is n^{1-1/O(c log c)} for d = c log n. The data structure is simple and is based on a new "augmented, randomized, lopsided" variant of k-d trees. It matches (in fact, slightly improves) the performance of previous combinatorial algorithms that work only in the case of offline queries [Impagliazzo, Lovett, Paturi, and Schneider (2014) and Chan (SODA'15)]. It leads to slightly faster combinatorial algorithms for all-pairs shortest paths in general real-weighted graphs and rectangular Boolean matrix multiplication. In the offline case, we show that the problem can be reduced to the Boolean orthogonal vectors problem and thus admits an n^{2-1/O(log c)}-time non-combinatorial algorithm [Abboud, Williams, and Yu (SODA'15)]. This reduction is also simple and is based on range trees. Finally, we use a similar approach to obtain a small improvement to Indyk's data structure [FOCS'98] for approximate l_infinity nearest neighbor search when d = c log n.

We study a longstanding problem in computational geometry: 2-d dynamic orthogonal range reporting. We present a new data structure achieving O(log n / log log n + k) optimal query time and O(log^{2/3+o(1)}n) update time (amortized) in the word RAM model, where n is the number of data points and k is the output size. This is the first improvement in over 10 years of Mortensen's previous result [SIAM J. Comput., 2006], which has O(log^{7/8+epsilon}n) update time for an arbitrarily small constant epsilon. In the case of 3-sided queries, our update time reduces to O(log^{1/2+epsilon}n), improving Wilkinson's previous bound [ESA 2014] of O(log^{2/3+epsilon}n).

We present an algorithm that computes a (1+varepsilon)-approximation of the diameter of a weighted, undirected planar graph of n vertices with non-negative edge lengths in O(nlog n(log n + (1/varepsilon)^5)) expected time, improving upon the O(n((1/varepsilon)^4 log^4(n) + 2^{O(1/varepsilon)}))-time algorithm of Weimann and Yuster [ICALP 2013]. Our algorithm makes two improvements over that result: first and foremost, it replaces the exponential dependency on 1/varepsilon with a polynomial one, by adapting and specializing Cabello's recent abstract-Voronoi-diagram-based technique [SODA 2017] for approximation purposes; second, it shaves off two logarithmic factors by choosing a better sequence of error parameters during recursion. Moreover, using similar techniques, we improve the (1+varepsilon)-approximate distance oracle of Gu and Xu [ISAAC 2015] by first replacing the exponential dependency on 1/varepsilon on the preprocessing time and space with a polynomial one and second removing a logarithmic factor from the preprocessing time.

We prove the existence of an algorithm A for computing 2D or 3D convex hulls that is optimal for every point set in the following sense: for every sequence σ of n points and for every algorithm A ′ in a certain class A , the running time of A on input σ is at most a constant factor times the running time of A ′ on the worst possible permutation of σ for A ′. In fact, we can establish a stronger property: for every sequence σ of points and every algorithm A ′, the running time of A on σ is at most a constant factor times the average running time of A ′ over all permutations of σ. We call algorithms satisfying these properties instance optimal in the order-oblivious and random-order setting. Such instance-optimal algorithms simultaneously subsume output-sensitive algorithms and distribution-dependent average-case algorithms, and all algorithms that do not take advantage of the order of the input or that assume the input are given in a random order. The class A under consideration consists of all algorithms in a decision tree model where the tests involve only multilinear functions with a constant number of arguments. To establish an instance-specific lower bound, we deviate from traditional Ben-Or-style proofs and adopt a new adversary argument. For 2D convex hulls, we prove that a version of the well-known algorithm by Kirkpatrick and Seidel [1986] or Chan, Snoeyink, and Yap [1995] already attains this lower bound. For 3D convex hulls, we propose a new algorithm. We further obtain instance-optimal results for a few other standard problems in computational geometry, such as maxima in 2D and 3D, orthogonal line segment intersection in 2D, finding bichromatic L ∞ -close pairs in 2D, offline orthogonal range searching in 2D, offline dominance reporting in 2D and 3D, offline half-space range reporting in 2D and 3D, and offline point location in 2D. Our framework also reveals a connection to distribution-sensitive data structures and yields new results as a byproduct, for example, on online orthogonal range searching in 2D and online half-space range reporting in 2D and 3D.

Given an $n$-vertex graph and two straight-line planar drawings of the graph that have the same faces and the same outer face, we show that there is a morph (i.e., a continuous transformation) between the two drawings that preserves straight-line planarity and consists of $O(n)$ steps, which we prove is optimal in the worst case. Each step is a unidirectional linear morph, which means that every vertex moves at constant speed along a straight line, and the lines are parallel although the vertex speeds may differ. Thus we provide an efficient version of Cairns' 1944 proof of the existence of straight-line planarity-preserving morphs for triangulated graphs, which required an exponential number of steps.

Introduced by Agarwal, Har-Peled, and Varadarajan [J. ACM, 2004], an epsilon-kernel of a point set is a coreset that can be used to approximate the width, minimum enclosing cylinder, minimum bounding box, and solve various related geometric optimization problems. Such coresets form one of the most important tools in the design of linear-time approximation algorithms in computational geometry, as well as efficient insertion-only streaming algorithms and dynamic (non-streaming) data structures. In this paper, we continue the theme and explore dynamic streaming algorithms (in the so-called turnstile model). Andoni and Nguyen [SODA 2012] described a dynamic streaming algorithm for maintaining a (1+epsilon)-approximation of the width using O(polylog U) space and update time for a point set in [U]^d for any constant dimension d and any constant epsilon>0. Their sketch, based on a "polynomial method", does not explicitly maintain an epsilon-kernel. We extend their method to maintain an epsilon-kernel, and at the same time reduce some of logarithmic factors. As an application, we obtain the first randomized dynamic streaming algorithm for the width problem (and related geometric optimization problems) that supports k outliers, using poly(k, log U) space and time.

Given a set of geometric objects each associated with a time value, we wish to determine whether a given property is true for a subset of those objects whose time values fall within a query time window. We call such problems time-windowed decision problems, and they have been the subject of much recent attention, for instance studied by Bokal, Cabello, and Eppstein [SoCG 2015]. In this paper, we present new approaches to this class of problems that are conceptually simpler than Bokal et al.'s, and also lead to faster algorithms. For instance, we present algorithms for preprocessing for the time-windowed 2D diameter decision problem in O(n log n) time and the time-windowed 2D convex hull area decision problem in O(n alpha(n) log n) time (where alpha is the inverse Ackermann function), improving Bokal et al.'s O(n log^2 n) and O(n log n loglog n) solutions respectively. Our first approach is to reduce time-windowed decision problems to a generalized range successor problem, which we solve using a novel way to search range trees. Our other approach is to use dynamic data structures directly, taking advantage of a new observation that the total number of combinatorial changes to a planar convex hull is near linear for any FIFO update sequence, in which deletions occur in the same order as insertions. We also apply these approaches to obtain the first O(n polylog n) algorithms for the time-windowed 3D diameter decision and 2D orthogonal segment intersection detection problems.

We design new polynomials for representing threshold functions in three different regimes: probabilistic polynomials of low degree, which need far less randomness than previous constructions, polynomial threshold functions (PTFs) with "nice" threshold behavior and degree almost as low as the probabilistic polynomials, and a new notion of probabilistic PTFs where we combine the above techniques to achieve even lower degree with similar "nice" threshold behavior. Utilizing these polynomial constructions, we design faster algorithms for a variety of problems: · Offline Hamming Nearest (and Furthest) Neighbors: Given n red and n blue points in d-dimensional Hamming space for d = c log n, we can find an (exact) nearest (or furthest) blue neighbor for every red point in randomized time n2-1/O(√clog2/3c) or deterministic time n2-1/O(c log2 c). These improve on a randomized n2-1/O(c log2 c)bound by Alman and Williams (FOCS'15), and also lead to faster MAX-SAT algorithms for sparse CNFs. · Offline Approximate Nearest (and Furthest) Neighbors: Given n red and n blue points in d-dimensional ℓ1or Euclidean space, we can find a (1+ε)-approximate nearest (or furthest) blue neighbor for each red point in randomized time near dn+n2-Ω(ε1/3/log(1/ε)). This improves on an algorithm by Valiant (FOCS'12) with randomized time near dn+n2-Ω(√ε), which in turn improves previous methods based on locality-sensitive hashing. · SAT Algorithms and Lower Bounds for Circuits With Linear Threshold Functions: We give a satisfiability algorithm for AC0[m] o LTF LTF circuits with a subquadratic number of LTF gates on the bottom layer, and a subexponential number of gates on the other layers, that runs in deterministic 2n-nεtime. This strictly generalizes a SAT algorithm for ACC0oLTF circuits of subexponential size by Williams (STOC'14) and also implies new circuit lower bounds for threshold circuits, improving a recent gate lower bound of Kane and Williams (STOC'16). We also give a randomized 2n-nε-time SAT algorithm for subexponential-size MAJ o AC0oLTF o AC0oLTF circuits, where the top MAJ gate and middle LTF gates have O(n6/5-δ) fan-in.

In this paper we study the all-pairs shortest paths problem in (unweighted) unit-disk graphs. The previous best solution for this problem required O(n^2 log n) time, by running the O(n log n)-time single-source shortest path algorithm of Cabello and Jejcic [Comput. Geom., 2015] from every source vertex,where n is the number of vertices. We not only manage to eliminate the logarithmic factor, but also obtain the first (slightly) subquadratic algorithm for the problem, running in O(n^2 sqrt{ frac{log log n}{log n} }) time. Our algorithm computes an implicit representation of all the shortest paths, and, in the same amount of time, can also compute the diameter of the graph.

At SODA'93, Chazelle and Matoušek presented a derandomization of Clarkson's sampling-based algorithm [FOCS'88] for solving linear programs with n constraints and d variables in d(7+o(1))dn deterministic time. The time bound can be improved to d(5+o(1))dn with subsequent work by Brönnimann, Chazelle, and Matoušek [FOCS'93]. We first point out a much simpler derandomization of Clarkson's algorithm that avoids ∊-approximations and runs in d(3+o(1))dn time. We then describe a few additional ideas that eventually improve the deterministic time bound to d(1/2+o(1))dn.

We show how to solve all-pairs shortest paths on n nodes in deterministic time, and how to count the pairs of orthogonal vectors among n 0–1 vectors in d = clogn dimensions in deterministic n2–1/O(logc) time. These running times essentially match the best known randomized algorithms of (Williams, STOC'14) and (Abboud, Williams, and Yu, SODA 2015) respectively, and the ability to count was open even for randomized algorithms. By reductions, these two results yield faster deterministic algorithms for many other problems. Our techniques can also be used to deterministically count k-SAT assignments on n variable formulas in 2n–n/O(k) time, roughly matching the best known running times for detecting satisfiability and resolving an open problem of Santhanam (2013). A key to our constructions is an efficient way to deterministically simulate certain probabilistic polynomials critical to the algorithms of prior work, carefully applying small-biased sets and modulus-amplifying polynomials.

We present three new results on one of the most basic problems in geometric data structures, 2-D orthogonal range counting . All the results are in the w -bit word RAM model. —It is well known that there are linear-space data structures for 2-D orthogonal range counting with worst-case optimal query time O (log n /log log n ). We give an O ( n log log n )-space adaptive data structure that improves the query time to O (log log n + log k /log log n ), where k is the output count. When k = O (1), our bounds match the state of the art for the 2-D orthogonal range emptiness problem [Chan et al., 2011]. —We give an O ( n log log n )-space data structure for approximate 2-D orthogonal range counting that can compute a (1 + δ)-factor approximation to the count in O (log log n ) time for any fixed constant δ > 0. Again, our bounds match the state of the art for the 2-D orthogonal range emptiness problem. —Last, we consider the 1-D range selection problem, where a query in an array involves finding the k th least element in a given subarray. This problem is closely related to 2-D 3-sided orthogonal range counting. Recently, Jørgensen and Larsen [2011] presented a linear-space adaptive data structure with query time O (log log n + log k /log log n ). We give a new linear-space structure that improves the query time to O (1 + log k /log log n ), exactly matching the lower bound proved by Jørgensen and Larsen.

Chazelle [FOCS'89] gave a linear-time algorithm to compute the intersection of two convex polyhedra in three dimensions. We present a simpler algorithm to do the same.

We present optimal deterministic algorithms for constructing shallow cuttings in an arrangement of lines in two dimensions or planes in three dimensions. Our results improve the deterministic polynomial-time algorithm of Matousek (1992) and the optimal but randomized algorithm of Ramos (1999). This leads to efficient derandomization of previous algorithms for numerous well-studied problems in computational geometry, including halfspace range reporting in 2-d and 3-d, k nearest neighbors search in 2-d, (<= k)-levels in 3-d, order-k Voronoi diagrams in 2-d, linear programming with k violations in 2-d, dynamic convex hulls in 3-d, dynamic nearest neighbor search in 2-d, convex layers (onion peeling) in 3-d, epsilon-nets for halfspace ranges in 3-d, and more. As a side product we also describe an optimal deterministic algorithm for constructing standard (non-shallow) cuttings in two dimensions, which is arguably simpler than the known optimal algorithms by Matousek (1991) and Chazelle (1993).

We describe a fully dynamic linear-space data structure for point location in connected planar subdivisions, or more generally vertical ray shooting among non-intersecting line segments, that supports queries in O(log n(log log n)2) time and updates in O(log nlog log n) time. This is the first data structure that achieves close to logarithmic query and update time simultaneously, ignoring log logn factors. We further show how to reduce the query time to O(logn log log n) in the RAM model with randomization. Alternatively, the query time can be lowered to O(log n) if the update time is increased to O(log1+εn) for any constant ε > 0, or vice versa.

We present a new combinatorial algorithm for Boolean matrix multiplication that runs in O(n3(log log n)3/log3 n) time. This improves the previous combinatorial algorithm by Bansal and Williams [FOCS'O9] that runs in O(n3(log log n)2/log9/4n) time. Whereas Bansal and Williams' algorithm uses regularity lemmas for graphs, the new algorithm is simple and uses entirely elementary techniques: table lookup, word operations, plus a deceptively straightforward divide-and-conquer.

We present a collection of new results on problems related to 3SUM, including: The first truly subquadratic algorithm for computing the (min,+) convolution for monotone increasing sequences with integer values bounded by O(n), solving 3SUM for monotone sets in 2D with integer coordinates bounded by O(n), and preprocessing a binary string for histogram indexing (also called jumbled indexing).

Recently, Arya, da Fonseca, and Mount [STOC 2011, SODA 2012] made notable progress in improving the ϵ-dependencies in the space/query-time tradeoffs for (1 + ϵ)-factor approximate nearest neighbor search in fixed-dimensional Euclidean spaces. However, ϵ-dependencies in the preprocessing time were not considered, and so their data structures cannot be used to derive faster algorithms for offline proximity problems. Known algorithms for many such problems, including approximate bichromatic closest pair (BCP) and approximate Euclidean minimum spanning trees (EMST), typically have factors near (1/ϵ)d/2±O(1) in the running time when the dimension d is a constant.

Many standard problems in computational geometry have been solved asymptotically optimally as far as comparison-based algorithms are concerned, but there has been little work focusing on improving the constant factors hidden in big-Oh bounds on the number of comparisons needed. In this paper, we consider orthogonal-type problems and present a number of results that achieve optimality in the constant factors of the leading terms, including:

We consider the classical selection and sorting problems in a model where the initial permutation of the input has to be restored after completing the computation. While the requirement of the restoration is stringent compared to the classical versions of the problems, this model is more relaxed than a read-only memory where the input elements are not allowed to be moved within the input array. We first show that for a sequence of n integers, selection (finding the median or more generally the k-th smallest element for a given k) can be done in O(n) time using O(lgn) words1 of extra space in this model. In contrast, no linear-time selection algorithm is known which uses polylogarithmic space in the read-only memory model. For sorting n integers in this model, we first present an O(n lg n)-time algorithm using O(lg n) words of extra space. When the universe size U is polynomial in n, we give a faster O(n)-time algorithm (analogous to radix sort) which uses O(n∊) words of extra space for an arbitrarily small constant ∊ > 0. More generally, we show how to match the time bound of any word-RAM integer-sorting algorithms using O(n∊) words of extra space. In sharp contrast, there is an Ω(n2/S)-time lower bound for integer sorting using O(S) bits of space in the read-only memory model. Extension of our results to arbitrary input types beyond integers is not possible: for “indivisible” input elements, we can prove the same Ω(n2/S) lower bound for sorting in our model. En route, we develop linear-time in-place algorithms to extract leading bits of the input array and to compress and decompress strings with low entropy; these techniques may be of independent interest.

We present a new algorithm for a classic problem in computational geometry, Klee's measure problem: given a set of n axis-parallel boxes in d-dimensional space, compute the volume of the union of the boxes. The algorithm runs in O(nd/2) time for any constant d ≥ 3. Although it improves the previous best algorithm by “just” an iterated logarithmic factor, the real surprise lies in the simplicity of the new algorithm. We also show that it is theoretically possible to beat the O(nd/2) time bound by logarithmic factors for integer input in the word RAM model, and for other variants of the problem. With additional work, we obtain an O(nd/3polylog n)-time algorithm for the important special case of orthants or unit hypercubes (which include the so-called “hypervolume indicator problem”), and an O(n(d+1)/3polylog n)-time algorithm for the case of arbitrary hypercubes or fat boxes, improving a previous O(n(d+2)/3)-time algorithm by Bringmann.

In 1944, Cairns proved the following theorem: given any two straight-line planar drawings of a triangulation with the same outer face, there exists a morph (i.e., a continuous transformation) between the two drawings so that the drawing remains straight-line planar at all times. Cairns's original proof required exponentially many morphing steps. We prove that there is a morph that consists of O(n2) steps, where each step is a linear morph that moves each vertex at constant speed along a straight line. Using a known result on compatible triangulations this implies that for a general planar graph G and any two straight-line planar drawings of G with the same embedding, there is a morph between the two drawings that preserves straight-line planarity and consists of O(n4) steps.

We present three new results on one of the most basic problems in geometric data structures, 2-D orthogonal range counting. All the results are in the w-bit word RAM model. It is well known that there are linear-space data structures for 2-D orthogonal range counting with worst-case optimal query time O(logw n). We give an O(n log log n)-space adaptive data structure that improves the query time to O (log log n + logw k), where k is the output count. When k = O(1), our bounds match the state of the art for the 2-D orthogonal range emptiness problem [Chan, Larsen, and Pătraşcu, SoCG 2011]. We give an O(n log log n)-space data structure for approximate 2-D orthogonal range counting that can compute a (1 + δ)-factor approximation to the count in O (log log n) time for any fixed constant δ > 0. Again, our bounds match the state of the art for the 2-D orthogonal range emptiness problem. Lastly, we consider the 1-D range selection problem, where a query in an array involves finding the kth least element in a given subarray. This problem is closely related to 2-D 3-sided orthogonal range counting. Recently, Jørgensen and Larsen [SODA 2011] presented a linear-space adaptive data structure with query time O (log log n + logw k). We give a new linear-space structure that improves the query time to O(1 + logw k), exactly matching the lower bound proved by Jørgensen and Larsen.

We answer a basic data structuring question (e.g., raised by Dietz and Raman [1991]): Can van Emde Boas trees be made persistent, without changing their asymptotic query/update time? We present a (partially) persistent data structure that supports predecessor search in a set of integers in {1, ..., U } under an arbitrary sequence of n insertions and deletions, with O (log log U ) expected query time and expected amortized update time, and O ( n ) space. The query bound is optimal in U for linear-space structures and improves previous near- O ((log log U ) 2 ) methods. The same method solves a fundamental problem from computational geometry: point location in orthogonal planar subdivisions (where edges are vertical or horizontal). We obtain the first static data structure achieving O (log log U ) worst-case query time and linear space. This result is again optimal in U for linear-space structures and improves the previous O ((log log U ) 2 ) method by de Berg et al. [1995]. The same result also holds for higher-dimensional subdivisions that are orthogonal binary space partitions, and for certain nonorthogonal planar subdivisions such as triangulations without small angles. Many geometric applications follow, including improved query times for orthogonal range reporting for dimensions ≥ 3 on the RAM. Our key technique is an interesting new van-Emde-Boas--style recursion that alternates between two strategies, both quite simple.

In the conflict-free coloring problem, for a given range space, we want to bound the minimum value F(n) such that every set P of n points can be colored with F(n) colors with the property that every nonempty range contains a unique color. We prove a new upper bound O(n0.368) with respect to orthogonal ranges in two dimensions (i.e., axis-parallel rectangles), which is the first improvement over the previous bound O(n0.382) by Ajwani, Elbassioni, Govindarajan, and Ray [SPAA'07]. This result leads to an O(n1-0.632/2d-2) upper bound with respect to orthogonal ranges (boxes) in dimension d, and also an O(n1-0.632/(2d-3-0.368)) upper bound with respect to dominance ranges (orthants) in dimension d ≥ 4.

The minimum-weight set cover problem is widely known to be O(log n)-approximable, with no improvement possible in the general case. We take the approach of exploiting problem structure to achieve better results, by providing a geometry-inspired algorithm whose approximation guarantee depends solely on an instance-specific combinatorial property known as shallow cell complexity (SCC). Roughly speaking, a set cover instance has low SCC if any column-induced submatrix of the corresponding element-set incidence matrix has few distinct rows. By adapting and improving Varadarajan's recent quasi-uniform random sampling method for weighted geometric covering problems, we obtain strong approximation algorithms for a structurally rich class of weighted covering problems with low SCC. We also show how to derandomize our algorithm. Our main result has several immediate consequences. Among them, we settle an open question of Chakrabarty et al. [8] by showing that weighted instances of the capacitated covering problem with underlying network structure have O(1)-approximations. Additionally, our improvements to Varadarajan's sampling framework yield several new results for weighted geometric set cover, hitting set, and dominating set problems. In particular, for weighted covering problems exhibiting linear (or near-linear) union complexity, we obtain approximability results agreeing with those known for the unweighted case. For example, we obtain a constant approximation for the weighted disk cover problem, improving upon the 2O(log* n)-approximation known prior to our work and matching the O(1)-approximation known for the unweighted variant.

A mode of a multiset S is an element a in S of maximum multiplicity; that is, a occurs at least as frequently as any other element in S. Given an array A[1:n] of n elements, we consider a basic problem: constructing a static data structure that efficiently answers range mode queries on A. Each query consists of an input pair of indices (i, j) for which a mode of A[i:j] must be returned. The best previous data structure with linear space, by Krizanc, Morin, and Smid (ISAAC 2003), requires O(sqrt(n) loglog n) query time. We improve their result and present an O(n)-space data structure that supports range mode queries in O(sqrt(n / log n)) worst-case time. Furthermore, we present strong evidence that a query time significantly below sqrt(n) cannot be achieved by purely combinatorial techniques; we show that boolean matrix multiplication of two sqrt(n) by sqrt(n) matrices reduces to n range mode queries in an array of size O(n). Additionally, we give linear-space data structures for orthogonal range mode in higher dimensions (queries in near O(n^(1-1/2d)) time) and for halfspace range mode in higher dimensions (queries in O(n^(1-1/d^2)) time).

We revisit the all-pairs-shortest-paths problem for an unweighted undirected graph with n vertices and m edges. We present new algorithms with the following running times: { O ( mn /log n ) if m > n log n log log log n O ( mn log log n /log n ) if m > n log log n O ( n 2 log 2 log n /log n ) if m ≤ n log log n . These represent the best time bounds known for the problem for all m ≪ n 1.376 . We also obtain a similar type of result for the diameter problem for unweighted directed graphs.

We present three results related to dynamic convex hulls: A fully dynamic data structure for maintaining a set of n points in the plane so that we can find the edges of the convex hull intersecting a query line, with expected query and amortized update time O(log1+en) for an arbitrarily small constant e>0. This improves the previous bound of O(log3/2n). A fully dynamic data structure for maintaining a set of n points in the plane to support halfplane range reporting queries in O(log n + k) time with O(polylog, n) expected amortized update time. A similar result holds for 3-dimensional orthogonal range reporting. For 3-dimensional halfspace range reporting, the query time increases to O(log2 n/log log n + k). A semi-online dynamic data structure for maintaining a set of n line segments in the plane, so that we can decide whether a query line segment lies completely above the lower envelope, with query time O(log n) and amortized update time O(ne). As a corollary, we can solve the following problem in O(n1+e) time: given a triangulated terrain in 3-d of size n, identify all faces that are partially visible from a fixed viewpoint.

We present a number of new results on one of the most extensively studied topics in computational geometry, orthogonal range searching. All our results are in the standard word RAM model: We present two data structures for 2-d orthogonal range emptiness. The first achieves O(n lg lg n) space and O(lg lg n) query time, assuming that the n given points are in rank space. This improves the previous results by Alstrup, Brodal, and Rauhe (FOCS'00), with O(n lgε n) space and O(lg lg n) query time, or with O(n lg lg n) space and O(lg2lg n) query time. Our second data structure uses O(n) space and answers queries in O(lgε n) time. The best previous O(n)-space data structure, due to Nekrich (WADS'07), answers queries in O(lg n/lg lg n) time. We give a data structure for 3-d orthogonal range reporting with O(n lg1+ε n) space and O(lg lg n + k) query time for points in rank space, for any constant ε>0. This improves the previous results by Afshani (ESA'08), Karpinski and Nekrich (COCOON'09), and Chan (SODA'11), with O(n lg3 n) space and O(lg lg n + k) query time, or with O(n lg1+εn) space and O(lg2lg n + k) query time. Consequently, we obtain improved upper bounds for orthogonal range reporting in all constant dimensions above 3.

We study the complexity of geometric minimum spanning trees under a stochastic model of input: Suppose we are given a master set of points s1,s_2,...,sn in d-dimensional Euclidean space, where each point si is active with some independent and arbitrary but known probability pi. We want to compute the expected length of the minimum spanning tree (MST) of the active points. This particular form of stochastic problems is motivated by the uncertainty inherent in many sources of geometric data but has not been investigated before in computational geometry to the best of our knowledge. Our main results include the following.

We answer a basic data structuring question (for example, raised by Dietz and Raman back in SODA 1991): can van Emde Boas trees be made persistent, without changing their asymptotic query/update time? We present a (partially) persistent data structure that supports predecessor search in a set of integers in {1, …, U} under an arbitrary sequence of n insertions and deletions, with O(log log U) expected query time and expected amortized update time, and O(n) space. The query bound is optimal in U for linear-space structures and improves previous near-O((log log U)2) methods.

In this talk, I will discuss some "textbook exercises" in low-dimensional computational geometry that any algorithmist with no computational-geometry background can attempt to solve: Given a set of red and blue points, is there a red point dominating (bigger along all coordinates than) a blue point? Given a set of horizontal and vertical line segments, is there an intersection? Given a set of axis-parallel boxes, is there a box strictly contained in another box? There are connections to non-geometric problems such as counting inversions and all-pairs shortest paths. Remarkably, certain versions of these problems are still open! I will describe the latest worst-case results in the standard word-RAM model, as well as the recent surprising discovery of "instance-optimal" algorithms in the traditional comparison model.

Dynamic connectivity is a well-studied problem, but so far the most compelling progress has been confined to the edge-update model: maintain an understanding of connectivity in an undirected graph, subject to edge insertions and deletions. In this paper, we study two more challenging, yet equally fundamental, problems. Subgraph connectivity asks us to maintain an understanding of connectivity under vertex updates: updates can turn vertices on and off, and queries refer to the subgraph induced by on vertices. (For instance, this is closer to applications in networks of routers, where node faults may occur.) We describe a data structure supporting vertex updates in $\widetilde{O}(m^{2/3})$ amortized time, where m denotes the number of edges in the graph. This greatly improves upon the previous result [T. M. Chan, in Proceedings of the 34th Annual ACM Symposium on Theory of Computing (STOC), 2002, pp. 7–13], which required fast matrix multiplication and had an update time of $O(m^{0.94})$. The new data structure is also simpler. Geometric connectivity asks us to maintain a dynamic set of n geometric objects and query connectivity in their intersection graph. (For instance, the intersection graph of balls describes connectivity in a network of sensors with bounded transmission radius.) Previously, nontrivial fully dynamic results were known only for special cases like axis-parallel line segments and rectangles. We provide similarly improved update times, $\widetilde{O}(n^{2/3})$, for these special cases. Moreover, we show how to obtain sublinear update bounds for virtually all families of geometric objects which allow sublinear time range queries. In particular, we obtain the first sublinear update time for arbitrary two-dimensional line segments: $O^*(n^{9/10})$; for d-dimensional simplices: $O^*(n^{1-\frac{1}{d(2d+1)}})$; and for d-dimensional balls: $O^*(n^{1-\frac{1}{(d+1)(2d+3)}})$.

We revisit one of the most fundamental classes of data structure problems in computational geometry: range searching. Back in SoCG'92, Matousek gave a partition tree method for d-dimensional simplex range searching achieving O(n) space and O(n1-1/d) query time. Although this method is generally believed to be optimal, it is complicated and requires O(n1+ε) preprocessing time for any fixed ε>0. An earlier method by Matousek (SoCG'91) requires O(n log n) preprocessing time but O(n1-1/d logO(1)n) query time. We give a new method that achieves simultaneously O(n log n) preprocessing time, O(n) space, and O(n1-1/d) query time with high probability. Our method has several advantages:

We give an -time algorithm for counting the number of inversions in a permutation on n elements. This improves a long-standing previous bound of O(n lg n/lg lg n) that followed from Dietz's data structure [WADS'89], and answers a question of Andersson and Petersson [SODA'95]. As Dietz's result is known to be optimal for the related dynamic rank problem, our result demonstrates a significant improvement in the offline setting. Our new technique is quite simple: we perform a “vertical partitioning” of a trie (akin to van Emde Boas trees), and use ideas from external memory. However, the technique finds numerous applications: for example, we obtain in d dimensions, an algorithm to answer n offline orthogonal range counting queries in time O(n lgd–2+1/d n); an improved construction time for online data structures for orthogonal range counting; an improved update time for the partial sums problem; faster Word RAM algorithms for finding the maximum depth in an arrangement of axis-aligned rectangles, and for the slope selection problem. As a bonus, we also give a simple (1 + ε)-approximation algorithm for counting inversions that runs in linear time, improving the previous O(n lg lg n) bound by Andersson and Petersson.

We present a fully dynamic randomized data structure that can answer queries about the convex hull of a set of n points in three dimensions, where insertions take O (log 3 n ) expected amortized time, deletions take O (log 6 n ) expected amortized time, and extreme-point queries take O (log 2 n ) worst-case time. This is the first method that guarantees polylogarithmic update and query cost for arbitrary sequences of insertions and deletions, and improves the previous O ( n ϵ )-time method by Agarwal and Matoušek a decade ago. As a consequence, we obtain similar results for nearest neighbor queries in two dimensions and improved results for numerous fundamental geometric problems (such as levels in three dimensions and dynamic Euclidean minimum spanning trees in the plane).

In the first part of the paper, we reexamine the all-pairs shortest path (APSP) problem and present a new algorithm with running time $O(n^3\log^3\log n/\log^2n)$, which improves all known algorithms for general real-weighted dense graphs. In the second part of the paper, we use fast matrix multiplication to obtain truly subcubic APSP algorithms for a large class of “geometrically weighted” graphs, where the weight of an edge is a function of the coordinates of its vertices. For example, for graphs embedded in Euclidean space of a constant dimension d, we obtain a time bound near $O(n^{3-(3-\omega)/(2d+4)})$, where $\omega<2.376$; in two dimensions, this is $O(n^{2.922})$. Our framework greatly extends the previously considered case of small–integer-weighted graphs, and incidentally also yields the first truly subcubic result (near $O(n^{3-(3-\omega)/4})=O(n^{2.844})$ time) for APSP in real–vertex-weighted graphs, as well as an improved result (near $O(n^{(3+\omega)/2})=O(n^{2.688})$ time) for the all-pairs lightest shortest path problem for small–integer-weighted graphs.

We establish the first nontrivial lower bounds on time-space trade-offs for the selection problem. We prove that any comparison-based randomized algorithm for finding the median requires Ω( n log log S n ) expected time in the RAM model (or more generally in the comparison branching program model), if we have S bits of extra space besides the read-only input array. This bound is tight for all S > log n , and remains true even if the array is given in a random order. Our result thus answers a 16-year-old question of Munro and Raman [1996], and also complements recent lower bounds that are restricted to sequential access, as in the multipass streaming model [Chakrabarti et al. 2008b]. We also prove that any comparison-based, deterministic, multipass streaming algorithm for finding the median requires Ω( n log * ( n / s )+ n log s n ) worst-case time (in scanning plus comparisons), if we have s cells of space. This bound is also tight for all s >log 2 n . We get deterministic lower bounds for I/O-efficient algorithms as well. The proofs in this article are self-contained and do not rely on communication complexity techniques.

We study a bichromatic version of the well-known k-set problem : given two sets R and B of points of total size n and an integer k , how many subsets of the form (R ∩ h ) ∪ ( B ∖ h ) can have size exactly k over all halfspaces h ? In the dual, the problem is asymptotically equivalent to determining the worst-case combinatorial complexity of the k-level in an arrangement of n halfspaces . Disproving an earlier conjecture by Linhart [1993], we present the first nontrivial upper bound for all k ≪ n in two dimensions: O ( nk 1/3 + n 5/6−ϵ k 2/3+2 ϵ + k 2 ) for any fixed ϵ<0. In three dimensions, we obtain the bound O ( nk 3/2 + n 0.5034 k 2.4932 + k 3 ). Incidentally, this also implies a new upper bound for the original k -set problem in four dimensions: O ( n 2 k 3/2 + n 1.5034 k 2.4932 + n k 3 ), which improves the best previous result for all k ≪ n 0.923 . Extensions to other cases, such as arrangements of disks, are also discussed.

We describe the first optimal randomized in-place algorithm for the basic 3-d convex hull problem (and, in particular, for 2-d Voronoi diagrams). The algorithm runs in O(n log n) expected time using only O(1) extra space; this improves the previous O(n log3 n) bound by Bronnimann, Chan, and Chen [SoCG'04]. The same approach leads to an optimal randomized in-place algorithm for the 2-d line segment intersection problem, with O(n log n+K) expected running time for output size K, improving the previous O(n log2 n + K) bound by Vahrenhold [WADS'05]. As a bonus, we also point out a simplification of a known optimal cache-oblivious (non-in-place) algorithm by Kumar and Ramos (2002) for 3-d convex hulls, and observe its applicability to 2-d segment intersection, extending a recent result for red/blue segment intersection by Arge, Molhave, and Zeh [ESA'08]. Our results are all obtained by standard random sampling techniques, with some interesting twists.

We present approximation algorithms for maximum independent set of pseudo-disks in the plane, both in the weighted and unweighted cases. For the unweighted case, we prove that a local search algorithm yields a PTAS. For the weighted case, we suggest a novel rounding scheme based on an LP relaxation of the problem, that leads to a constant-factor approximation. Most previous algorithms for maximum independent set (in geometric settings) relied on packing arguments that are not applicable in this case. As such, the analysis of both algorithms requires some new combinatorial ideas, which we believe to be of independent interest.

We prove the existence of an algorithm A for computing 2-d or 3-dconvex hulls that is optimal for every point set in the following sense: for every set S of n points and for every algorithm A' in a certain class A, the running time of A on the worst permutation of S for A is at most a constant factor times the running time of A' on the worst permutation of S for A'. In fact, we can establish a stronger property: for every S and A', the running time of A on S is at most a constant factor times the average running time of A' over all permutations of S. We call algorithms satisfying these properties instance-optimal in the order-oblivious and random-order setting. Such instance-optimal algorithms simultaneously subsume output-sensitive algorithms and distribution-dependent average-case algorithms, and all algorithms that do not take advantage of the order of the input or that assume the input is given in a random order. The class A under consideration consists of all algorithms in a decision tree model where the tests involve only multilinear functions with a constant number of arguments. To establish an instance-specific lower bound, we deviate from traditional Ben-Or-style proofs and adopt an interesting adversary argument. For 2-d convex hulls, we prove that a version of the well known algorithm by Kirkpatrick and Seidel (1986) or Chan, Snoeyink, and Yap(1995) already attains this lower bound. For 3-d convex hulls, we propose a new algorithm. We further obtain instance-optimal results for a few other standard problems in computational geometry, such as maxima in 2-d and 3-d, orthogonal line segment intersection in 2-d, offline orthogonal range searching in 2-d, off-line halfspace range reporting in 2-d and 3-d, and off-line point location in 2-d. The theory we develop also neatly reveals connections to entropy-dependent data structures, and yields as a byproduct new expected case results, e.g., for on-line orthogonal range counting in 2-d.

We give the first optimal solution to a standard problem in computational geometry: three-dimensional halfspace range reporting. We show that n points in 3-d can be stored in a linear-space data structure so that all k points inside a query halfspace can be reported in O(log n + k) time. The data structure can be built in O(n log n) expected time. The previous methods with optimal query time required superlinear (O(n log log n)) space. We also mention consequences, for example, to higher dimensions and to external-memory data structures. As an aside, we partially answer another open question concerning the crossing number in Matoušek's shallow partition theorem in the 3-d case (a tool used in many known halfspace range reporting methods).

We establish the first nontrivial lower bounds on time-space tradeoffs for the selection problem. We prove that any comparison-based randomized algorithm for finding the median requires Ω(nloglogSn) expected time in the RAM model (or more generally in the comparison branching program model), if we have S bits of extra space besides the read-only input array. This bound is tight for all S ≫ log n, and remains true even if the array is given in a random order. Our result thus answers a 16-year-old question of Munro and Raman, and also complements recent lower bounds that are restricted to sequential access, as in the multi-pass streaming model [Chakrabarti et al, SODA 2008]. We also prove that any comparison-based, deterministic, multi-pass streaming algorithm for finding the median requires Ω(nlog*(n/s) + nlogs n) worst-case time (in scanning plus comparisons), if we have s cells of space. This bound is also tight for all s ≫ log2 n. We get deterministic lower bounds for I/O-efficient algorithms as well. All proofs in this paper involve “elementary” techniques only.

Given a planar subdivision whose coordinates are integers bounded by $U\leq2^w$, we present a linear-space data structure that can answer point-location queries in $O(\min\{\lg n/\lg\lg n,$ $\sqrt{\lg U/\lg\lg U}\})$ time on the unit-cost random access machine (RAM) with word size w. This is the first result to beat the standard $\Theta(\lg n)$ bound for infinite precision models. As a consequence, we obtain the first $o(n\lg n)$ (randomized) algorithms for many fundamental problems in computational geometry for arbitrary integer input on the word RAM, including: constructing the convex hull of a three-dimensional (3D) point set, computing the Voronoi diagram or the Euclidean minimum spanning tree of a planar point set, triangulating a polygon with holes, and finding intersections among a set of line segments. Higher-dimensional extensions and applications are also discussed. Though computational geometry with bounded precision input has been investigated for a long time, improvements have been limited largely to problems of an orthogonal flavor. Our results surpass this long-standing limitation, answering, for example, a question of Willard (SODA'92).

We give a dynamic data structure that can maintain an μ-coreset of n points, with respect to the extent measure, in O(log n) time for any constant μ > 0 and any constant dimension. The previous method by Agarwal, Har-Peled, and Varadarajan requires polylogarithmic update time. For points with integer coordinates bounded by U, we alternatively get O(log log U) time. Numerous applications follow, for example, on dynamically approximating the width, smallest enclosing cylinder, minimum bounding box, or minimum-width annulus. We can also use the same approach to maintain approximate k-centers in O(min log n, log log U) randomized amortized time for any constant k and any constant dimension.

We revisit the problem of bounding the combinatorial complexity of the k-level in a two-dimensional arrangement of n curves. We give a number of small improvements over the results from the author's previous paper (FOCS'03). For example:

Given n axis-parallel boxes in a fixed dimension d ≥ 3, how efficiently can we compute the volume of the union? This standard problem in computational geometry, commonly referred to as Klee's measure problem, can be solved in time O(nd/2 log n) by an algorithm of Overmars and Yap (FOCS 1988). We give the first (albeit small) improvement: our new algorithm runs in time nd/22O(log*n), where log* denotes the iterated logarithm.

Dynamic connectivity is a well-studied problem, but so far the most compelling progress has been confined to the edge-update model: maintain an understanding of connectivity in an undirected graph, subject to edge insertions and deletions. In this paper, we study two more challenging, yet equally fundamental problems:Subgraph connectivity asks to maintain an understanding of connectivity under vertex updates: updates can turn vertices on and off, and queries refer to the subgraph induced by "on" vertices. (For instance, this is closer to applications in networks of routers, where node faults may occur.)We describe a data structure supporting vertex updates in O~(m^{2/3}) amortized time, where m denotes the number of edges in the graph. This greatly improves over the previous result [Chan, STOC'02], which required fast matrix multiplication and had an update time of O(m^{0.94}). The new data structure is also simpler.Geometric connectivity asks to maintain a dynamic set of ngeometric objects, and query connectivity in their intersection graph. (For instance, the intersection graph of balls describes connectivity in a network of sensors with bounded transmission radius.)Previously, nontrivial fully dynamic results were known onlyfor special cases like axis-parallel line segments and rectangles. We provide similarly improved update times, O~(n^{2/3}), for these special cases. Moreover, we show how to obtain sublinear update bounds for virtually all families of geometric objects which allow sublinear-time range queries. In particular, we obtain the first sublinear update time for arbitrary 2D line segments: O*(n^{9/10}); for d-dimensional simplices: O*(n^{1-1/d(2d+1)}); and for d-dimensional balls: O*(n^{1-1/(d+1)(2d+3)}).

We improve the previous results by Aronov and Har-Peled (SODA'05) and Kaplan and Sharir (SODA'06) and present a randomized data structure of O(n) expected sizewhich can answer 3D approximate halfspace range counting queries in O(log n/k) expected time, where k is the actual value of the count. This is the first optimal method for the problem in the standard decision tree model; moreover, unlike previous methods, the new method is Las Vegas instead of Monte Carlo.In addition, we describe new results for several related problems, includingapproximate Tukey depth queries in 3D, approximate regression depthqueries in 2D, and approximate linear programming with violations inlow dimensions.

In the first part of the paper, we reexamine the all-pairsshortest paths (APSP) problem and present a newalgorithm with running time approaching O(n3/log2n), which improves all known algorithms for general real-weighted dense graphs andis perhaps close to the best result possible without using fast matrix multiplication, modulo a few log log n factors.

We reexamine fundamental problems from computational geometry in theallword RAM model, where input coordinates are integers that fit in a machine word. We develop a new algorithm for offline point location, a two-dimensional analog of sorting where one needs to order points with respect to segments. This result implies, for example, that the Voronoi diagram of n points in the plane can be constructed in (randomized) time n· 2O(√ lg lg n). Similar bounds hold for numerous other geometric problems, such as three-dimensional convex hulls, planar Euclidean minimum spanning trees, line segment intersection, and triangulation of non-simple polygons.In FOCS'06, we developed a data structure for online point location, which implied a bound of O(n (lg n)/(lg lg n) for Voronoi diagrams and the other problems. Our current bounds are dramatically better, and a convincing improvement over the classic O(n lg n) algorithms. As in the field of integer sorting, the main challenge is to find ways to manipulate information, while avoiding the online problem (in that case, predecessor search).

Given n points in the plane with integer coordinates bounded by U les 2w, we show that the Voronoi diagram can be constructed in O(min {n log n/ log log n, n(radic(log U)}) expected time by a randomized algorithm on the unit-cost RAM with word size w. Similar results are also obtained for many other fundamental problems in computational geometry, such as constructing the convex hull of a 3-dimensional point set, computing the Euclidean minimum spanning tree of a planar point set, triangulating a polygon with holes, and finding intersections among a set of line segments. These are the first results to beat the Omega(n log n) algebraic-decision-tree lower bounds known for these problems. The results are all derived from a new two-dimensional version of fusion trees that can answer point location queries in O(min { log n / log log n, radic(log U)}) time with linear space. Higher-dimensional extensions and applications are also mentioned in the paper

Inspired by dynamic connectivity applications in computational geometry, we consider a problem we call dynamic subgraph connectivity: design a data structure for an undirected graph $G=(V,E)$ and a subset of vertices $S \subseteq V$ to support insertions/deletions in S and connectivity queries (are two vertices connected?) in the subgraph induced by S. We develop the first sublinear, fully dynamic method for this problem for general sparse graphs, using a combination of several simple ideas. Our method requires $\widetilde O(|E|^{4\omega/(3\omega+3)})=O(|E|^{0.94})$ amortized update time, and $\widetilde O(|E|^{1/3})$ query time, after $\widetilde O(|E|^{(5\omega+1)/(3\omega+3)})$ preprocessing time, where ω is the matrix multiplication exponent and $\widetilde O$ hides polylogarithmic factors.

We initiate the study of exact geometric algorithms that require limited storage and make only a small number of passes over the input. Fundamental problems such as low-dimensional linear programming and convex hulls are considered.

Two decades ago, Megiddo and Dyer showed that linear programming (LP) in two and three dimensions (and subsequently any constant number of dimensions) can be solved in linear time. In this paper, we consider the LP problem with at most kviolations , i.e., finding a point inside all but at most k halfspaces, given a set of n halfspaces. We present a simple algorithm in two dimensions that runs in O((n+k 2 )log n) expected time; this is faster than earlier algorithms by Everett, Robert, and van Kreveld (1993) and Matousek (1994) for many values of k and is probably near-optimal. An extension of our algorithm in three dimensions runs in near O(n+k 11/4 n 1/4 ) expected time. Interestingly, the idea is based on concave-chain decompositions (or covers) of the $(\le k)$-level, previously used in proving combinatorial k-level bounds. Applications in the plane include improved algorithms for finding a line that misclassifies the fewest among a set of bichromatic points, and finding the smallest circle enclosing all but k points. We also discuss related problems of finding local minima in levels.

For many geometric problems, there are efficient algorithms that surprisingly use very little extra space other than the given array holding the input. For many geometric query problems, there are efficient data structures that need no extra space at all other than an array holding a permutation of the input. In this paper, we obtain the first such space-economical solutions for a number of fundamental problems, including three-dimensional convex hulls, two-dimensional Delaunay triangulations, fixed-dimensional range queries, and fixed-dimensional nearest neighbor queries.

We speed up previous (1+ε)-factor approximation algorithms for a number of geometric optimization problems in fixed dimensions: diameter, width, minimum-radius enclosing cylinder, minimum-width annulus, minimum-volume bounding box, minimum-width cylindrical shell, etc. Linear time bounds were known before we further improve the dependence of the "constants" in terms of ε.We next consider the data stream model and present new (1+ε)-factor approximation algorithms that need only constant space for all of the above problems in any fixed dimension. Previously, such a result was known only for diameter.Both sets of results are obtained using the core-set framework recently proposed by Agarwal, Har-Peled, and Varadarajan.

Let #K be the worst-case (supremum) ratio of the weight of the minimum degree-K spanning tree to the weight of the minimum spanning tree, over all finite point sets in the Euclidean plane. It is known that #2 = 2 and #5 = 1. In STOC'94, Khuller, Raghavachari, and Young established the following inequalities: 1.103 < #3 1.5 and 1.035 < 1.25. We present the first improved upper bounds: #3 < 1.402 and #4 < 1.143. As a result, we obtain better approximation algorithms for Euclidean minimum bounded-degree spanning trees. Let

We consider two variants of the well-known "sailor in the fog" puzzle. The first version (the "asteroid surveying" problem) is set in three dimensions and asks for the shortest curve that starts at the origin and intersects all planes at unit distance from the origin. Several possible solutions are suggested in the video, including a curve of length less than 12.08. The second version (the "river shore" problem) asks for the shortest curve in the plane that has unit width. A solution of length 2.2782 is described, which we have proved to be optimal.

We give a surprisingly short proof that in any planar arrangement of n curves where each pair intersects at most a fixed number (s) of times, the k-level has subquadratic (O(n/sup 2-1/2s/)) complexity. This answers one of the main open problems from the author's previous paper, which provided a weaker bound for a restricted class of curves (graphs of degree-s polynomials) only. When combined with existing tools (cutting curves, sampling, etc.), the new idea generates a slew of improved k-level results for most of the curve families studied earlier, including a near-O(n/sup 3/2/) bound for parabolas.

We give the first nontrivial worst-case results for dynamic versions of various basic geometric optimization and measure problems under the semi-online model, where during the insertion of an object we are told when the object is to be deleted. Problems that we can solve with sublinear update time include the Hausdorff distance of two point sets, discrete 1-center, largest empty circle, convex hull volume in three dimensions, volume of the union of axis-parallel cubes, and minimum enclosing rectangle. The decision versions of the Hausdorff distance and discrete 1-center problems can be solved fully dynamically. Some applications are mentioned.

Megiddo (1984) and Dyer (1984) showed that linear programming in 2 and 3 dimensions (and subsequently, any constant number of dimensions) can be solved in linear time. In this paper, we consider linear programming with at most k violations: finding a point inside all but at most k of n given halfspaces. We give a simple algorithm in 2-d that runs in O((n + k/sup 2/) log n) expected time; this is faster than earlier algorithms by Everett, Robert, and van Kreveld (1993) and Matousek (1994) and is probably near-optimal for all k /spl Lt/ n/2. A (theoretical) extension of our algorithm in 3-d runs in near O(n + k/sup 11/4/n/sup 1/4/) expected time. Interestingly; the idea is based on concave-chain decompositions (or covers) of the (/spl les/ k)-level, previously used in proving combinatorial k -level bounds. Applications in the plane include improved algorithms for finding a line that misclassifies the fewest among a set of bichromatic points, and finding the smallest circle enclosing all but k points. We also discuss related problems of finding local minima in levels.

(MATH) Inspired by dynamic connectivity applications in computational geometry, we consider a problem we call dynamic subgraph connectivity: design a data structure for an undirected graph $G=(V,E)$ and a subset of vertices $S\on V$, to support insertions and deletions in~$S$ and connectivity queries (are two vertices connected\@?) in the subgraph induced by~$S$. We develop the first sublinear, fully dynamic method for this problem for general sparse graphs, using an elegant combination of several simple ideas. Our method requires linear space, $\OO (|E|^{4\w/(3\w+3)})=O(|E|^{0.94})$ amortized update time, and $\OO(|E|^{1/3})$ query time, where $\w$ is the matrix multiplication exponent and $\OO$ hides polylogarithmic factors.

We show how to maintain the width of a set of $n$ planar points subjec t to insertions and deletions of points in $O(\sqrt{n}\log^3n)$ amortized time per update. Previously, no fully dynamic algorithm with a guaranteed sublinear time bound was known.

We give a data structure that allows arbitrary insertions and deletions on a planar point set P and supports basic queries on the convex hull of P , such as membership and tangent-finding. Updates take O (log 1+ε n ) amori tzed time and queries take O (log n time each, where n is the maximum size of P and ε is any fixed positive constant. For some advanced queries such as bridge-finding, both our bounds increase to O (log 3/2 n ). The only previous fully dynamic solution was by Overmars and van Leeuwen from 1981 and required O (log 2 n ) time per update and O (log n ) time per query.

Article Approximating the diameter, width, smallest enclosing cylinder, and minimum-width annulus Share on Author: Timothy M. Chan Dept. of Computer Science, Univ. of Waterloo, Waterloo, Ontario N2L 3G1, Canada Dept. of Computer Science, Univ. of Waterloo, Waterloo, Ontario N2L 3G1, CanadaView Profile Authors Info & Claims SCG '00: Proceedings of the sixteenth annual symposium on Computational geometryMay 2000 Pages 300–309https://doi.org/10.1145/336154.336216Online:01 May 2000Publication History 30citation816DownloadsMetricsTotal Citations30Total Downloads816Last 12 Months35Last 6 weeks3 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

Analyzing the worst-case complexity of the k-level in a planar arrangement of n curves is a fundamental problem in combinatorial geometry. We give the first subquadratic upper bound (roughly O(nk/sup 1-2/3/*)) for curves that are graphs of polynomial functions of an arbitrary fixed degree s. Previously, nontrivial results were known only for the case s=1 and s=2. We also improve the earlier bound for pseudo-parabolas (curves that pairwise intersect at most twice) to O(nk/sup 7/9/log/sup 2/3/ k). The proofs are simple and rely on a theorem of Tamaki and Tokuyama on cutting pseudo-parabolas into pseudo-segments, as well as a new observation for cutting pseudo-segments into pieces that can be extended to pseudo-lines. We mention applications to parametric and kinetic minimum spanning trees.

Given n points in three dimensions, we show how to answer halfspace range reporting queries in O(log n+k) expected time for an output size k. Our data structure can be preprocessed in optimal O(n log n) expected time. We apply this result to obtain the first optimal randomized algorithm for the construction of the $(\le k)$-level in an arrangement of n planes in three dimensions. The algorithm runs in O(n log n+nk 2 ) expected time. Our techniques are based on random sampling. Applications in two dimensions include an improved data structure for "k nearest neighbors" queries and an algorithm that constructs the order-k Voronoi diagram in O(n log n+nk log k) expected time.

We give a data structure that allows arbitrary insertions and deletions on a planar point set P and supports basic queries on the convex hull of P, such as membership and tangent-finding. Updates take O(log/sup 1+/spl epsiv// n) amortized time and queries take O(log n) time each, where n is the maximum size of P and /spl epsiv/ is any fixed positive constant. For some advanced queries such as bridge-finding, both our bounds increase to O(log/sup 3/2/ n). The only previous fully dynamic solution was by Overmars and van Leeuwen (1981) and required O(log/sup 2/ n) time per update.

This paper considers the planar Euclidean two-center problem: given a planar n-point set S, find two congruent circular disks of the smallest radius covering S. The main result is a deterministic algorithm with running time O(nlog2nlog2logn), improving the previous O(nlog9n) bound of Sharir and almost matching the randomized O(nlog2n) bound of Eppstein. If a point in the intersection of the two disks is given, then we can solve the problem in O(nlogn) time with high probability.

Article Geometric applications of a randomized optimization technique Share on Author: Timothy M. Chan Dapartment of Mathematics and Computer Science, University of Miami, Coral Gables, FL Dapartment of Mathematics and Computer Science, University of Miami, Coral Gables, FLView Profile Authors Info & Claims SCG '98: Proceedings of the fourteenth annual symposium on Computational geometryJune 1998 Pages 269–278https://doi.org/10.1145/276884.276915Online:07 June 1998Publication History 5citation357DownloadsMetricsTotal Citations5Total Downloads357Last 12 Months4Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

Given an n-point set, the problems of enumerating the k closest pairs and selecting the k-th smallest distance are revisited. For the enumeration problem, we give simpler randomized and deterministic algorithms with O(n log n + k) running time in any fixed-dimensional Euclidean space. For the selection problem, we give a randomized algorithm with running time O(n log n + n 2=3 k 1=3 log 5=3 n). We also describe output-sensitive results for halfspace range counting that are of use in more general distance selection problems. None of our algorithms requires parametric search. Keywords: distance enumeration, distance selection, closest pairs, range counting, randomized algorithms. 1 Introduction Finding the closest pair of an n-point set has a long history in computational geometry (see [34] for a nice survey). In the plane, the problem can be solved in O(n log n) time using the Delaunay triangulation. In an arbitrary fixed dimension d, the first O(n log n) algorithm, based on di...

Given n points in three dimensions, we show how to answer halfspace range reporting queries in O(log n+k) expected time for an output size k. Our data structure can be preprocessed in optimal O(n log n) expected time. We apply this result to obtain the first optimal randomized algorithm for the construction of the (/spl les/k)-level in an arrangement of n planes in three dimensions. The algorithm runs in O(n log n+nk/sup 2/) expected time. Our techniques are based on random sampling. Applications in two dimensions include an improved data structure for "k nearest neighbors" queries, and an algorithm that constructs the order-k Voronoi diagram in O(n log n+nk log k) expected time.

This note gives a short proof of a sampling lemma used by Karger, Klein, and Tarjan in the analysis of their randomized linear-time algorithm for minimum spanning trees.

This paper proposes new methods to answer approximate nearest neighbor queries on a set of n points in d-dimensional Euclidean space. For any xed constant d, a data structure with O( " (1;d)=2 n log n) preprocessing time and O( " (1;d)=2 log n) query time achieves approximation factor 1 + " for any given 0 <"<1�avariant reduces the "-dependence by afactorof ";1=2.For any arbitrary d, a data structure with O(d 2 n log n) preprocessing time and O(d 2 log n) query time achieves approximation factor O(d 3=2). Applications to various proximity problems are discussed. 1

We derive two results from Clarkson's randomized algorithm for linear programming in a fixed dimension d. The first is a simple general method that reduces the problem of answering linear programming queries to the problem of answering halfspace range queries. For example, this yields a randomized data structure with O(n) space and O(n 1\\Gamma1=bd=2c 2 O(log n) ) query time for linear programming on n halfspaces (d ? 3). The second result is a simpler proof of the following: a sequence of q linear programming queries on n halfspaces can be answered in O(n log q) time, if q n ff d for a certain constant ff d ? 0. Unlike previous methods, our algorithms do not require parametric searching. 1 Introduction One of the major discoveries in computational geometry is that fixed-dimensional linear programming can be solved in linear time [Meg84]. It was observed that the introduction of randomization leads to considerably simpler solutions [Sei91, Cla95]. The goal of this paper is...

We use known data structures for ray shooting and linear programming queries to derive new output-sensitive results on convex hulls, extreme points, and related problems.We show that the f-face convex hull of an n-point set P in a fixed dimension d can be constructed in O(n log f -t (n.f)l-1J(l~i2~+lJ logo(l) n) time.In particular, this yields new optimal output-sensitive convex hull algorithms in two and three dimensions.We also show that the h extreme points of P can be computedOur techniques are then applied to obtain improved time bounds for other problems including convex layers, levels in arrangements, and linear programming with few violated constraints. 1