Let K be a compact, centrally-symmetric, strictly-convex region in ℝ³, which is a semi-algebraic set of constant complexity, i.e. the unit ball of a corresponding metric, denoted as ‖⋅‖_K. Let 𝒦 be a set of n homothetic copies of K. This paper contains two main sets of results: (i) For a storage parameter s ∈ [n,n³], 𝒦 can be preprocessed in O^*(s) expected time into a data structure of size O^*(s), so that for a query homothet K₀ of K, an intersection-detection query (determine whether K₀ intersects any member of 𝒦, and if so, report such a member) or a nearest-neighbor query (return the member of 𝒦 whose ‖⋅‖_K-distance from K₀ is smallest) can be answered in O^*(n/s^{1/3}) time; all k homothets of 𝒦 intersecting K₀ can be reported in additional O(k) time. In addition, the data structure supports insertions/deletions in O^*(s/n) amortized expected time per operation. Here the O^*(⋅) notation hides factors of the form n^ε, where ε > 0 is an arbitrarily small constant, and the constant of proportionality depends on ε. (ii) Let 𝒢(𝒦) denote the intersection graph of 𝒦. Using the above data structure, breadth-first or depth-first search on 𝒢(𝒦) can be performed in O^*(n^{3/2}) expected time. Combining this result with the so-called shrink-and-bifurcate technique, the reverse-shortest-path problem in a suitably defined proximity graph of 𝒦 can be solved in O^*(n^{62/39}) expected time. Dijkstra’s shortest-path algorithm, as well as Prim’s MST algorithm, on a ‖⋅‖_K-proximity graph on n points in ℝ³, with edges weighted by ‖⋅‖_K, can also be performed in O^*(n^{3/2}) time.

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

Let P be a set of n points in ℝ^d, d ≥ 2, and let t ≥ 2 be an integer. Let H_t(P) denote the t-uniform hypergraph on P, whose hyperedges consist of all t-tuples T ⊂ P for which ‖p-q‖ ≤ 1, for any two points p,q ∈ T. A matching in H_t(P) is a collection of vertex-disjoint hyperedges. We present a PTAS for finding a maximum matching in H_t(P). In particular, we present the first PTAS for the well-studied problem known as maximum (vertex-disjoint) triangle packing in unit disk graphs. Our approach consists of a sparsification stage, which replaces P by a subset Q with favorable properties, followed by an implementation of a PTAS for a maximum matching in H_t(Q). The two stages follow the high-level machinery in [Édouard Bonnet et al., 2023] and [Rom Aschner et al., 2013], respectively, but are considerably more involved.

We present efficient algorithms for the bottleneck path problem in two geometric settings that arise naturally in applications: directional-antenna graphs in the plane with antenna angles bounded from below by a constant, and visibility graphs whose vertices lie on or above a 1.5-dimensional terrain, both with Euclidean distances as edge weights. We provide near-linear algorithms for the corresponding decision problems, namely, determining whether the subgraph obtained by retaining all edges with weight at most some threshold bn contains a path from s to t. We then use the decision procedures to obtain algorithms for the bottleneck path problem that run in O^*(n^{8/7}) randomized expected time, where n is the input size and the O^*(⋅) notation hides subpolynomial factors. Within the same performance bounds, we can also solve the bounded-hop version, in which we only consider s-t paths with at most k edges, for a given integer k < n.

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

Semialgebraic graphs are graphs whose vertices are points in {ℝ}^d, and adjacency between two vertices is determined by the truth value of a semialgebraic predicate of constant complexity. We show how to harness polynomial partitioning methods to construct compact adjacency labeling schemes for families of semialgebraic graphs. That is, we show that for any family of semialgebraic graphs, given a graph on n vertices in this family, we can assign a label consisting of O(n^{1-2/(d+1) + {ε}}) bits to each vertex (where {ε} > 0 can be made arbitrarily small and the constant of proportionality depends on {ε} and on the complexity of the adjacency-defining predicate), such that adjacency between two vertices can be determined solely from their two labels, without any additional information. We obtain for instance that unit disk graphs and segment intersection graphs have such labelings with labels of O(n^{1/3 + {ε}}) bits. This is in contrast to their natural implicit representation consisting of the coordinates of the disk centers or segment endpoints, which sometimes require exponentially many bits. It also improves on the best known bound of O(n^{1-1/d}log n) for d-dimensional semialgebraic families due to Alon (Discrete Comput. Geom., 2024), a bound that holds more generally for graphs with shattering functions bounded by a degree-d polynomial. Our labeling scheme is efficient in the sense that not only adjacency between two vertices can be decided in time linear in the size of their labels, but the labels can be computed in subquadratic time on a real RAM from the input points and the semialgebraic adjacency predicate, using recent polynomial partitioning algorithms. We also give new bounds on the size of adjacency labels for other families of graphs. In particular, we consider semilinear graphs, which are semialgebraic graphs in which the predicate only involves linear polynomials. We show that semilinear graphs have adjacency labels of size O(log n). We also prove that polygon visibility graphs, which are not semialgebraic in the above sense, have adjacency labels of size O(log³ n).

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

Let ℬ be a collection of n arbitrary balls in ℝ³, and let G₀(ℬ) be their intersection graph. We provide an algorithm for performing BFS on G₀(ℬ), which runs in O^*(n^{4/3}) time, where the O^*(⋅) notation hides subpolynomial factors. For r ≥ 0, let G_r(ℬ) be the intersection graph of the set ℬ_r = {B+r ∣ B ∈ ℬ}, where B+r is the ball concentric with B whose radius is larger by r than the radius of B. We provide an efficient algorithm for the reverse shortest path (RSP) problem, where we are given two designated balls B_s, B_t of ℬ and a parameter 0 < λ < n, and seek the smallest value r^* for which G_{r^*}(ℬ) contains a path from B_s to B_t of at most λ edges. For the special case of congruent balls (equivalently, for points in ℝ³), the algorithm runs in O^*(n^{29/21}) ≈ O^*(n^{1.381}) time. For the general case, the algorithm runs in O^*(n^{56/39}) ≈ O^*(n^{1.436}) time. We also extend the technique to handle other measures of expansion and higher dimensions.

Abstract. For a set [Formula: see text] of [Formula: see text] points in [Formula: see text], for any [Formula: see text], a hyperplane [Formula: see text] is called [Formula: see text]- rich with respect to [Formula: see text] if it contains at least [Formula: see text] points of [Formula: see text]. Answering and generalizing a question asked by Peyman Afshani, we show that if the number of [Formula: see text]-rich hyperplanes in [Formula: see text], [Formula: see text], is at least [Formula: see text], with a sufficiently large constant of proportionality and with [Formula: see text], then there exists a [Formula: see text]-flat that contains [Formula: see text] points of [Formula: see text]. We also present upper bound constructions that give instances in which the above lower bound is tight. An extension of our analysis yields similar lower bounds for [Formula: see text]-rich spheres or [Formula: see text]-rich flats.

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

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

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

Let W ⊂ ℝ2 be a planar polygonal environment (i.e., a polygon potentially with holes) with a total of n vertices, and let A, B be two robots, each modeled as an axis-aligned unit square, that can translate inside W. Given source and target placements sA,tA,sB, tB ∈ W of A and B, respectively, the goal is to compute a collision-free-motion plan π*, i.e., a motion plan that continuously moves A from sA to tA and B from sB to tB so that A and B remain inside W and do not collide with each other during the motion. Furthermore, if such a plan exists, then we wish to return a plan that minimizes the sum of the lengths of the paths traversed by the robots. Given W,sA,tA,sB,tB and a parameter ɛ > 0, we present an n2ɛ-°(1) log n-time (1 + ɛ)-approximation algorithm for this problem. We are not aware of any polynomial-time algorithm for this problem, nor do we know whether the problem is NP-Hard. Our result is the first polynomial-time (1 + ɛ)-approximation algorithm for an optimal motion-planning problem involving two robots moving in a polygonal environment.

Let S be a set of n geometric objects of constant complexity (e.g., points, line segments, disks, ellipses) in ℝ², and let ϱ: S× S → ℝ_{≥ 0} be a distance function on S. For a parameter r ≥ 0, we define the proximity graph G(r) = (S,E) where E = {(e₁,e₂) ∈ S×S ∣ e₁≠e₂, ϱ(e₁,e₂) ≤ r}. Given S, s,t ∈ S, and an integer k ≥ 1, the reverse-shortest-path (RSP) problem asks for computing the smallest value r^* ≥ 0 such that G(r^*) contains a path from s to t of length at most k. In this paper we present a general randomized technique that solves the RSP problem efficiently for a large family of geometric objects and distance functions. Using standard, and sometimes more involved, semi-algebraic range-searching techniques, we first give an efficient algorithm for the decision problem, namely, given a value r ≥ 0, determine whether G(r) contains a path from s to t of length at most k. Next, we adapt our decision algorithm and combine it with a random-sampling method to compute r^*, by efficiently performing a binary search over an implicit set of O(n²) candidate values that contains r^*. We illustrate the versatility of our general technique by applying it to a variety of geometric proximity graphs. For example, we obtain (i) an O^*(n^{4/3}) expected-time randomized algorithm (where O^*(⋅) hides polylog(n) factors) for the case where S is a set of pairwise-disjoint line segments in ℝ² and ϱ(e₁,e₂) = min_{x ∈ e₁, y ∈ e₂} ‖x-y‖ (where ‖⋅‖ is the Euclidean distance), and (ii) an O^*(n+m^{4/3}) expected-time randomized algorithm for the case where S is a set of m points lying on an x-monotone polygonal chain T with n vertices, and ϱ(p,q), for p,q ∈ S, is the smallest value h such that the points p' := p+(0,h) and q' := q+(0,h) are visible to each other, i.e., all points on the segment p'q' lie above or on the polygonal chain T.

In the classical linear degeneracy testing problem, we are given $n$ real numbers and a $k$-variate linear polynomial $F$, for some constant $k$, and have to determine whether there exist $k$ numbers $a_1,\ldots,a_k$ from the set such that $F(a_1,\ldots,a_k) = 0$. We consider a generalization of this problem in which $F$ is an arbitrary constant-degree polynomial, we are given $k$ sets of $n$ numbers, and have to determine whether there exist a $k$-tuple of numbers, one in each set, on which $F$ vanishes. We give the first improvement over the naïve $O^*(n^{k-1})$ algorithm for this problem (where the $O^*(\cdot)$ notation omits subpolynomial factors). We show that the problem can be solved in time $O^*\left( n^{k - 2 + \frac 4{k+2}}\right)$ for even $k$ and in time $O^*\left( n^{k - 2 + \frac{4k-8}{k^2-5}}\right)$ for odd $k$ in the real RAM model of computation. We also prove that for $k=4$, the problem can be solved in time $O^*(n^{2.625})$ in the algebraic decision tree model, and for $k=5$ it can be solved in time $O^*(n^{3.56})$ in the same model, both improving on the above uniform bounds. All our results rely on an algebraic generalization of the standard meet-in-the-middle algorithm for $k$-SUM, powered by recent algorithmic advances in the polynomial method for semi-algebraic range searching. In fact, our main technical result is much more broadly applicable, as it provides a general tool for detecting incidences and other interactions between points and algebraic surfaces in any dimension. In particular, it yields an efficient algorithm for a general, algebraic version of Hopcroft's point-line incidence detection problem in any dimension.

We present a general technique, based on parametric search with some twist, for solving a variety of optimization problems on a set of semi-algebraic geometric objects of constant complexity. The common feature of these problems is that they involve a `growth parameter' $r$ and a semi-algebraic predicate $Π(o,o';r)$ of constant complexity on pairs of input objects, which depends on $r$ and is monotone in $r$. One then defines a graph $G(r)$ whose edges are all the pairs $(o,o')$ for which $Π(o,o';r)$ is true, and seeks the smallest value of $r$ for which some monotone property holds for $G(r)$. Problems that fit into this context include (i) the reverse shortest path problem in unit-disk graphs, recently studied by Wang and Zhao, (ii) the same problem for weighted unit-disk graphs, with a decision procedure recently provided by Wang and Xue, (iii) extensions of these problems to three and higher dimensions, (iv) the discrete Fréchet distance with one-sided shortcuts in higher dimensions, extending the study by Ben Avraham et al., (v) perfect matchings in intersection graphs: given, e.g., a set of fat ellipses of roughly the same size, find the smallest value $r$ such that if we expand each of the ellipses by $r$, the resulting intersection graph contains a perfect matching, (vi) generalized distance selection problems: given, e.g., a set of disjoint segments, find the $k$'th smallest distance among the pairwise distances determined by the segments, for a given (sufficiently small but superlinear) parameter $k$, and (vii) the maximum-height independent towers problem, in which we want to erect vertical towers of maximum height over a 1.5-dimensional terrain so that no pair of tower tips are mutually visible. We obtain significantly improved solutions for problems (i), (ii) and (vi), and new efficient solutions to the other problems.

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

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

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

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

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

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

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

We study several variants of the problem of moving a convex polytope K, with n edges, in three dimensions through a flat rectangular (and sometimes more general) window. Specifically: ii) We study variants where the motion is restricted to translations only, discuss situations where such a motion can be reduced to sliding (translation in a fixed direction), and present efficient algorithms for those variants, which run in time close to O(n^{8/3}). iii) We consider the case of a gate (an unbounded window with two parallel infinite edges), and show that K can pass through such a window, by any collision-free rigid motion, iff it can slide through it, an observation that leads to an efficient algorithm for this variant too. iv) We consider arbitrary compact convex windows, and show that if K can pass through such a window W (by any motion) then K can slide through a slab of width equal to the diameter of W. v) We show that if a purely translational motion for K through a rectangular window W exists, then K can also slide through W keeping the same orientation as in the translational motion. For a given fixed orientation of K we can determine in linear time whether K can translate (and hence slide) through W keeping the given orientation, and if so plan the motion, also in linear time. vi) We give an example of a polytope that cannot pass through a certain window by translations only, but can do so when rotations are allowed. vii) We study the case of a circular window W, and show that, for the regular tetrahedron K of edge length 1, there are two thresholds 1 > δ₁≈ 0.901388 > δ₂≈ 0.895611, such that (a) K can slide through W if the diameter d of W is ≥ 1, (b) K cannot slide through W but can pass through it by a purely translational motion when δ₁ ≤ d < 1, (c) K cannot pass through W by a purely translational motion but can do it when rotations are allowed when δ₂ ≤ d < δ₁, and (d) K cannot pass through W at all when d < δ₂. viii) Finally, we explore the general setup, where we want to plan a general motion (with all six degrees of freedom) for K through a rectangular window W, and present an efficient algorithm for this problem, with running time close to O(n⁴).

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

Let be a set of n axis-aligned cubes of arbitrary sizes in ℝ3 in general position. Let ≔ be their union, and let κ be the number of vertices on ∂; κ can vary between O(1) and O(n2). We show that cl(ℝ3 \ ) can be decomposed into O(κ log4 n) axis-aligned boxes with pairwise-disjoint interiors. Given a boundary representation of , such a decomposition can be computed in O(n log2 n + κ log6 n) time. We also show that a decomposition of size O(σ log4 n + κ log2 n), where σ is the number of input cubes that appear on ∂, can be computed in O(n log2 n + σ log8 n + κ log6 n) time. The complexity and runtime bounds improve to O(n log n) if all cubes in are congruent.

We present an explicit and efficient construction of additively weighted Voronoi diagrams on planar graphs. Let $G$ be a planar graph with $n$ vertices and $b$ sites that lie on a constant number of faces. We show how to preprocess $G$ in $\tilde O(nb^2)$ time so that one can compute any additively weighted Voronoi diagram for these sites in $\tilde O(b)$ time. We use this construction to compute the diameter of a directed planar graph with real arc lengths in $\tilde{O}(n^{5/3})$ time. This improves the recent breakthrough result of Cabello [ SODA 2017, SIAM, Philadelphia, 2017, pp. 2143--2152], both by improving the running time (from $\tilde{O}(n^{11/6})$), and by providing a deterministic algorithm. It is in fact the first truly subquadratic deterministic algorithm for this problem. Our use of Voronoi diagrams to compute the diameter follows that of Cabello, but he used abstract Voronoi diagrams, which makes his diameter algorithm more involved, more expensive, and randomized. As in Cabello's work, our algorithm can compute, for every vertex $v$, both the farthest vertex from $v$ (i.e., the eccentricity of $v$), and the sum of distances from $v$ to all other vertices. Hence, our algorithm can also compute the radius, median, and Wiener index (sum of all pairwise distances) of a planar graph within the same time bounds. Our construction of Voronoi diagrams for planar graphs is of independent interest.

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

We study the question of how to compute a point in the convex hull of an input set $S$ of $n$ points in ${\mathbb R}^d$ in a differentially private manner. This question, which is trivial non-privately, turns out to be quite deep when imposing differential privacy. In particular, it is known that the input points must reside on a fixed finite subset $G\subseteq{\mathbb R}^d$, and furthermore, the size of $S$ must grow with the size of $G$. Previous works focused on understanding how $n$ needs to grow with $|G|$, and showed that $n=O\left(d^{2.5}\cdot8^{\log^*|G|}\right)$ suffices (so $n$ does not have to grow significantly with $|G|$). However, the available constructions exhibit running time at least $|G|^{d^2}$, where typically $|G|=X^d$ for some (large) discretization parameter $X$, so the running time is in fact $Ω(X^{d^3})$. In this paper we give a differentially private algorithm that runs in $O(n^d)$ time, assuming that $n=Ω(d^4\log X)$. To get this result we study and exploit some structural properties of the Tukey levels (the regions $D_{\ge k}$ consisting of points whose Tukey depth is at least $k$, for $k=0,1,...$). In particular, we derive lower bounds on their volumes for point sets $S$ in general position, and develop a rather subtle mechanism for handling point sets $S$ in degenerate position (where the deep Tukey regions have zero volume). A naive approach to the construction of the Tukey regions requires $n^{O(d^2)}$ time. To reduce the cost to $O(n^d)$, we use an approximation scheme for estimating the volumes of the Tukey regions (within their affine spans in case of degeneracy), and for sampling a point from such a region, a scheme that is based on the volume estimation framework of Lovász and Vempala (FOCS 2003) and of Cousins and Vempala (STOC 2015). Making this framework differentially private raises a set of technical challenges that we address.

Abstract We describe a new data structure for dynamic nearest neighbor queries in the plane with respect to a general family of distance functions. These include $$L_p$$ L p -norms and additively weighted Euclidean distances. Our data structure supports general (convex, pairwise disjoint) sites that have constant description complexity (e.g., points, line segments, disks, etc.). Our structure uses $$O(n \log ^3 n)$$ O ( n log 3 n ) storage, and requires polylogarithmic update and query time, improving an earlier data structure of Agarwal, Efrat, and Sharir which required $$O(n^{\varepsilon })$$ O ( n ε ) time for an update and $$O(\log n)$$ O ( log n ) time for a query [SICOMP 1999]. Our data structure has numerous applications. In all of them, it gives faster algorithms, typically reducing an $$O(n^{\varepsilon })$$ O ( n ε ) factor in the previous bounds to polylogarithmic. In addition, we give here two new applications: an efficient construction of a spanner in a disk intersection graph, and a data structure for efficient connectivity queries in a dynamic disk graph. To obtain this data structure, we combine and extend various techniques from the literature. Along the way, we obtain several side results that are of independent interest. Our data structure depends on the existence and an efficient construction of “vertical” shallow cuttings in arrangements of bivariate algebraic functions. We prove that an appropriate level in an arrangement of a random sample of a suitable size provides such a cutting. To compute it efficiently, we develop a randomized incremental construction algorithm for computing the lowest k levels in an arrangement of bivariate algebraic functions (we mostly consider here collections of functions whose lower envelope has linear complexity, as is the case in the dynamic nearest-neighbor context, under both types of norm). To analyze this algorithm, we also improve a longstanding bound on the combinatorial complexity of the vertical decomposition of these levels. Finally, to obtain our structure, we combine our vertical shallow cutting construction with Chan’s algorithm for efficiently maintaining the lower envelope of a dynamic set of planes in $${{\mathbb {R}}}^3$$ R 3 . Along the way, we also revisit Chan’s technique and present a variant that uses a single binary counter, with a simpler analysis and improved amortized deletion time (by a logarithmic factor; the insertion and query costs remain asymptotically the same).

We consider the classical camera pose estimation problem that arises in many computer vision applications, in which we are given n 2D-3D correspondences between points in the scene and points in the camera image (some of which are incorrect associations), and where we aim to determine the camera pose (the position and orientation of the camera in the scene) from this data. We demonstrate that this posing problem can be reduced to the problem of computing ε-approximate incidences between two-dimensional surfaces (derived from the input correspondences) and points (on a grid) in a four-dimensional pose space. Similar reductions can be applied to other camera pose problems, as well as to similar problems in related application areas. We describe and analyze three techniques for solving the resulting ε-approximate incidences problem in the context of our camera posing application. The first is a straightforward assignment of surfaces to the cells of a grid (of side-length ε) that they intersect. The second is a variant of a primal-dual technique, recently introduced by a subset of the authors [2] for different (and simpler) applications. The third is a non-trivial generalization of a data structure Fonseca and Mount [3], originally designed for the case of hyperplanes. We present and analyze this technique in full generality, and then apply it to the camera posing problem at hand. We compare our methods experimentally on real and synthetic data. Our experiments show that for the typical values of n and ε, the primal-dual method is the fastest, also in practice.

A classical open problem in combinatorial geometry is to obtain tight asymptotic bounds on the maximum number of k-level vertices in an arrangement of n hyperplanes in d dimensions (vertices with exactly k of the hyperplanes passing below them). This is a dual version of the k-set problem, which, in a primal setting, seeks bounds for the maximum number of k-sets determined by n points in d dimensions, where a k-set is a subset of size k that can be separated from its complement by a hyperplane. The k-set problem is still wide open even in the plane, with a substantial gap between the best known upper and lower bounds. The gap gets larger as the dimension grows. In three dimensions, the best known upper bound is O(nk^(3/2)). In its dual version, the problem can be generalized by replacing hyperplanes by other families of surfaces (or curves in the planes). Reasonably sharp bounds have been obtained for curves in the plane, but the known upper bounds are rather weak for more general surfaces, already in three dimensions, except for the case of triangles. The best known general bound, due to Chan is O(n^2.997), for families of surfaces that satisfy certain (fairly weak) properties. In this paper we consider the case of pseudoplanes in 3 dimensions (defined in detail in the introduction), and establish the upper bound O(nk^(5/3)) for the number of k-level vertices in an arrangement of n pseudoplanes. The bound is obtained by establishing suitable (and nontrivial) extensions of dual versions of classical tools that have been used in studying the primal k-set problem, such as the Lova'sz Lemma and the Crossing Lemma.

Let $S \subset \mathbb{R}^2$ be a set of $n$ sites, where each $s \in S$ has an associated radius $r_s > 0$. The disk graph $D(S)$ is the undirected graph with vertex set $S$ and an undirected edge between two sites $s, t \in S$ if and only if $|st| \leq r_s + r_t$, i.e., if the disks with centers $s$ and $t$ and respective radii $r_s$ and $r_t$ intersect. Disk graphs are used to model sensor networks. Similarly, the transmission graph $T(S)$ is the directed graph with vertex set $S$ and a directed edge from a site $s$ to a site $t$ if and only if $|st| \leq r_s$, i.e., if $t$ lies in the disk with center $s$ and radius $r_s$. We provide algorithms for detecting (directed) triangles and, more generally, computing the length of a shortest cycle (the girth) in $D(S)$ and in $T(S)$. These problems are notoriously hard in general, but better solutions exist for special graph classes such as planar graphs. We obtain similarly efficient results for disk graphs and for transmission graphs. More precisely, we show that a shortest (Euclidean) triangle in $D(S)$ and in $T(S)$ can be found in $O(n \log n)$ expected time, and that the (weighted) girth of $D(S)$ can be found in $O(n \log n)$ expected time. For this, we develop new tools for batched range searching that may be of independent interest.

Let P be a set of n points in the plane in general position, and consider the problem of finding an axis-parallel rectangle with a given perimeter, or area, or diagonal, that encloses the maximum number of points of P . We present an exact algorithm that finds such a rectangle in O ( n 5 / 2 log ⁡ n ) time, and, for the case of a fixed perimeter or diagonal, we also obtain (i) an improved exact algorithm that runs in O ( n k 3 / 2 log ⁡ k ) time, and (ii) an approximation algorithm that finds, in O ( n + n k ε 5 log 5 / 2 ⁡ n k log ⁡ ( 1 ε log ⁡ n k ) ) time, a rectangle of the given perimeter that contains at least ( 1 − ε ) k points of P , where k is the optimum value. We then show how to turn this algorithm into one that finds, for a given k , an axis-parallel rectangle of smallest perimeter (or area, or diagonal) that contains k points of P . We obtain the first subcubic algorithms for these problems, significantly improving the current state of the art.

Let T={triangle_1,...,triangle_n} be a set of of n pairwise-disjoint triangles in R^3, and let B be a convex polytope in R^3 with a constant number of faces. For each i, let C_i = triangle_i oplus r_i B denote the Minkowski sum of triangle_i with a copy of B scaled by r_i>0. We show that if the scaling factors r_1, ..., r_n are chosen randomly then the expected complexity of the union of C_1, ..., C_n is O(n^{2+epsilon), for any epsilon > 0; the constant of proportionality depends on epsilon and the complexity of B. The worst-case bound can be Theta(n^3). We also consider a special case of this problem in which T is a set of points in R^3 and B is a unit cube in R^3, i.e., each C_i is a cube of side-length 2r_i. We show that if the scaling factors are chosen randomly then the expected complexity of the union of the cubes is O(n log^2 n), and it improves to O(n log n) if the scaling factors are chosen randomly from a "well-behaved" probability density function (pdf). We also extend the latter results to higher dimensions. For any fixed odd value of d, we show that the expected complexity of the union of the hypercubes is O(n^floor[d/2] log n) and the bound improves to O(n^floor[d/2]) if the scaling factors are chosen from a "well-behaved" pdf. The worst-case bounds are Theta(n^2) in R^3, and Theta(n^{ceil[d/2]}) in higher dimensions.

Our goal is to compare two planar point sets by finding subsets of a given size such that a minimum-weight matching between them has the smallest weight. This can be done by a translation of one set that minimizes the weight of the matching. We give efficient algorithms (a) for finding approximately optimal matchings, when the cost of a matching is the L_p-norm of the tuple of the Euclidean distances between the pairs of matched points, for any p in [1,infty], and (b) for constructing small-size approximate minimization (or matching) diagrams: partitions of the translation space into regions, together with an approximate optimal matching for each region.

Suppose we are given a set D of n pairwise intersecting disks in the plane. A planar point set P stabs D if and only if each disk in D contains at least one point from P. We present a deterministic algorithm that takes O(n) time to find five points that stab D. Furthermore, we give a simple example of 13 pairwise intersecting disks that cannot be stabbed by three points. This provides a simple - albeit slightly weaker - algorithmic version of a classical result by Danzer that such a set D can always be stabbed by four points.

This year we are celebrating the 10th anniversary of a dramatic revolution in combinatorial geometry, fueled by the infusion of techniques from algebraic geometry and algebra that have proven effective in solving a variety of hard problems that were thought to be unreachable with more traditional techniques. The new era has begun with two groundbreaking papers of Guth and Katz, the second of which has (almost completely) solved the celebrated distinct distances problem of Paul Erdös, open since 1946. In this talk I will survey, as time permits, some of the progress that has been made since then, including a variety of problems on distinct and repeated distances and other configurations, on incidences between points and lines, curves, and surfaces in two, three, and higher dimensions, on polynomials vanishing on Cartesian products with applications, and on cycle elimination for lines and triangles in three dimensions.

We present an efficient construction of additively weighted Voronoi diagrams on planar graphs. Let G be a planar graph with n vertices and b sites that lie on a constant number of faces. We show how to preprocess G in Õ(nb2) time1 so that one can compute any additively weighted Voronoi diagram for these sites in Õ(b) time. We use this construction to compute the diameter of a directed planar graph with real arc lengths in Õ(n5/3) time. This improves the recent breakthrough result of Cabello (SODA’17), both by improving the running time (from Õ(n11/6)), and by providing a deterministic algorithm. It is in fact the first truly subquadratic deterministic algorithm for this problem. Our use of Voronoi diagrams to compute the diameter follows that of Cabello, but he used abstract Voronoi diagrams, which makes his diameter algorithm more involved, more expensive, and randomized. As in Cabello's work, our algorithm can also compute the Wiener index of a planar graph (i.e., the sum of all pairwise distances) within the same bound. Our construction of Voronoi diagrams for planar graphs is of independent interest. It has already been used to obtain fast exact distance oracles for planar graphs [Cohen-Addad et al., FOCS’17].

Dynamic Time Warping (DTW) and Geometric Edit Distance (GED) are basic similarity measures between curves or general temporal sequences (e.g., time series) that are represented as sequences of points in some metric space (X, dist). The DTW and GED measures are massively used in various fields of computer science and computational biology. Consequently, the tasks of computing these measures are among the core problems in P. Despite extensive efforts to find more efficient algorithms, the best-known algorithms for computing the DTW or GED between two sequences of points inX= Rdare long-standing dynamic programming algorithms that require quadratic runtime, even for the one-dimensional cased= 1, which is perhaps one of the most used in practice. In this article, we break the nearly 50-year-old quadratic time bound for computing DTW or GED between two sequences ofnpoints in R by presenting deterministic algorithms that run inO(n2log log logn/ log logn) time. Our algorithms can be extended to work also for higher-dimensional spaces Rd, for any constantd, when the underlying distance-metric dist is polyhedral (e.g.,L1,Linfin).

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

For the past 10 years, combinatorial geometry (and to some extent, computational geometry too) has gone through a dramatic revolution, due to the infusion of techniques from algebraic geometry and algebra that have proven effective in solving a variety of hard problems that were thought to be unreachable with more traditional techniques. The new era has begun with two groundbreaking papers of Guth and Katz, the second of which has (almost completely) solved the distinct distances problem of Erdos, open since 1946. In this talk I will survey some of the progress that has been made since then, including a variety of problems on distinct and repeated distances and other configurations, on incidences between points and lines, curves, and surfaces in two, three, and higher dimensions, on polynomials vanishing on Cartesian products with applications, on cycle elimination for lines and triangles in three dimensions, on range searching with semialgebraic sets, and I will most certainly run out of time while doing so.

We consider the Approximate Nearest Neighbor (ANN) problem where the input set consists of n k-flats in the Euclidean Rd, for any fixed parameters k 0 is another prespecified parameter. We present an algorithm that achieves this task with n^{k+1}(log(n)/epsilon)^O(1) storage and preprocessing (where the constant of proportionality in the big-O notation depends on d), and can answer a query in O(polylog(n)) time (where the power of the logarithm depends on d and k). In particular, we need only near-quadratic storage to answer ANN queries amidst a set of n lines in any fixed-dimensional Euclidean space. As a by-product, our approach also yields an algorithm, with similar performance bounds, for answering exact nearest neighbor queries amidst k-flats with respect to any polyhedral distance function. Our results are more general, in that they also provide a tradeoff between storage and query time.

An $ε$-approximate incidence between a point and some geometric object (line, circle, plane, sphere) occurs when the point and the object lie at distance at most $ε$ from each other. Given a set of points and a set of objects, computing the approximate incidences between them is a major step in many database and web-based applications in computer vision and graphics, including robust model fitting, approximate point pattern matching, and estimating the fundamental matrix in epipolar (stereo) geometry. In a typical approximate incidence problem of this sort, we are given a set $P$ of $m$ points in two or three dimensions, a set $S$ of $n$ objects (lines, circles, planes, spheres), and an error parameter $ε>0$, and our goal is to report all pairs $(p,s)\in P\times S$ that lie at distance at most $ε$ from one another. We present efficient output-sensitive approximation algorithms for quite a few cases, including points and lines or circles in the plane, and points and planes, spheres, lines, or circles in three dimensions. Several of these cases arise in the applications mentioned above.

Given a set of $n$ real numbers, the 3SUM problem is to decide whether there are three of them that sum to zero. Until a recent breakthrough by Grønlund and Pettie [FOCS'14], a simple $Θ(n^2)$-time deterministic algorithm for this problem was conjectured to be optimal. Over the years many algorithmic problems have been shown to be reducible from the 3SUM problem or its variants, including the more generalized forms of the problem, such as $k$-SUM and $k$-variate linear degeneracy testing ($k$-LDT). The conjectured hardness of these problems have become extremely popular for basing conditional lower bounds for numerous algorithmic problems in P. In this paper, we show that the randomized $4$-linear decision tree complexity of 3SUM is $O(n^{3/2})$, and that the randomized $(2k-2)$-linear decision tree complexity of $k$-SUM and $k$-LDT is $O(n^{k/2})$, for any odd $k\ge 3$. These bounds improve (albeit randomized) the corresponding $O(n^{3/2}\sqrt{\log n})$ and $O(n^{k/2}\sqrt{\log n})$ decision tree bounds obtained by Grønlund and Pettie. Our technique includes a specialized randomized variant of fractional cascading data structure. Additionally, we give another deterministic algorithm for 3SUM that runs in $O(n^2 \log\log n / \log n )$ time. The latter bound matches a recent independent bound by Freund [Algorithmica 2017], but our algorithm is somewhat simpler, due to a better use of word-RAM model.

Dynamic Time Warping (DTW) and Geometric Edit Distance (GED) are basic similarity measures between curves or general temporal sequences (e.g., time series) that are represented as sequences of points in some metric space (X, dist). The DTW and GED measures are massively used in various fields of computer science and computational biology, consequently, the tasks of computing these measures are among the core problems in P. Despite extensive efforts to find more efficient algorithms, the best-known algorithms for computing the DTW or GED between two sequences of points in X = R^d are long-standing dynamic programming algorithms that require quadratic runtime, even for the one-dimensional case d = 1, which is perhaps one of the most used in practice. In this paper, we break the nearly 50 years old quadratic time bound for computing DTW or GED between two sequences of n points in R, by presenting deterministic algorithms that run in O( n^2 log log log n / log log n ) time. Our algorithms can be extended to work also for higher dimensional spaces R^d, for any constant d, when the underlying distance-metric dist is polyhedral (e.g., L_1, L_infty).

Given a set $S$ of $n$ points in \mathbb{R}^d, the Closest Pair problem is to find a pair of distinct points in S at minimum distance. When d is constant, there are efficient algorithms that solve this problem, and fast approximate solutions for general d. However, obtaining an exact solution in very high dimensions seems to be much less understood. We consider the high-dimensional L_\infty Closest Pair problem, where d=n^r for some r > 0, and the underlying metric is L_\infty. We improve and simplify previous results for L_\infty Closest Pair, showing that it can be solved by a deterministic strongly-polynomial algorithm that runs in O(DP(n,d)\log n) time, and by a randomized algorithm that runs in O(DP(n,d)) expected time, where DP(n,d) is the time bound for computing the dominance product for n points in \mathbb{R}^d. That is a matrix D, such that D[i,j] = \bigl| \{k \mid p_i[k] \leq p_j[k]\} \bigr|; this is the number of coordinates at which p_j dominates p_i. For integer coordinates from some interval [-M, M], we obtain an algorithm that runs in \tilde{O}\left(\min\{Mn^{\omega(1,r,1)},\, DP(n,d)\}\right) time, where \omega(1,r,1) is the exponent of multiplying an n \times n^r matrix by an n^r \times n matrix. We also give slightly better bounds for DP(n,d), by using more recent rectangular matrix multiplication bounds. Computing the dominance product itself is an important task, since it is applied in many algorithms as a major black-box ingredient, such as algorithms for APBP (all pairs bottleneck paths), and variants of APSP (all pairs shortest paths).

Given n non-vertical pairwise disjoint triangles in 3-space, their vertical depth (above/below) relation may contain cycles. We show that, for any ∊ > 0, the triangles can be cut into O(n3/2+∊) pieces, where each piece is a connected semi-algebraic set whose description complexity depends only on the choice of ∊, such that the depth relation among these pieces is now a proper partial order. This bound is nearly tight in the worst case. We are not aware of any previous study of this problem with a subquadratic bound on the number of pieces. This work extends the recent study by two of the authors on eliminating depth cycles among lines in 3-space. Our approach is again algebraic, and makes use of a recent variant of the polynomial partitioning technique, due to Guth, which leads to a recursive procedure for cutting the triangles. In contrast to the case of lines, our analysis here is considerably more involved, due to the two-dimensional nature of the objects being cut, so additional tools, from topology and algebra, need to be brought to bear. Our result essentially settles a 35-year-old open problem in computational geometry, motivated by hidden-surface removal in computer graphics.

We describe a new data structure for dynamic nearest neighbor queries in the plane with respect to a general family of distance functions that includes Lp-norms and additively weighted Euclidean distances, and for general (convex, pair- wise disjoint) sites that have constant description complexity (line segments, disks, etc.). Our data structure has a polylogarithmic update and query time, improving an earlier data structure of Agarwal, Efrat and Sharir that required O(n∊) time for an update and O(log n) time for a query [1]. Our data structure has numerous applications, and in all of them it gives faster algorithms, typically reducing an O(n∊) factor in the bounds to polylogarithmic. To further demonstrate its effectiveness, we give here two new applications: an efficient construction of a spanner in a disk intersection graph, and a data structure for efficient connectivity queries in a dynamic disk graph. To obtain this data structure, we combine and extend various techniques and obtain several side results that are of independent interest. Our data structure depends on the existence and an efficient construction of “vertical” shallow cuttings in arrangements of bivariate algebraic functions. We prove that an appropriate level in an arrangement of a random sample of a suitable size provides such a cutting. To compute it efficiently, we develop a randomized incremental construction algorithm for finding the lowest k levels in an arrangement of bivariate algebraic functions (we mostly consider here collections of functions whose lower envelope has linear complexity, as is the case in the dynamic nearest- neighbor context). To analyze this algorithm, we improve a longstanding bound on the combinatorial complexity of the vertical decomposition of these levels. Finally, to obtain our structure, we plug our vertical shallow cutting construction into Chan's algorithm for efficiently maintaining the lower envelope of a dynamic set of planes in ℝ3. While doing this, we also revisit Chan's technique and present a variant that uses a single binary counter, with a simpler analysis and an improved amortized deletion time.

We study a wide spectrum of incidence problems involving points and curves or points and surfaces in ℝ3. The current (and in fact the only viable) approach to such problems, pioneered by Guth and Katz [35, 36], requires a variety of tools from algebraic geometry, most notably (i) the polynomial partitioning technique, and (ii) the study of algebraic surfaces that are ruled by lines or, in more recent studies [37], by algebraic curves of some constant degree. By exploiting and refining these tools, we obtain new and improved bounds for numerous incidence problems in ℝ3. In broad terms, we consider two kinds of problems, those involving points and constant-degree algebraic curves, and those involving points and constant-degree algebraic surfaces. In some variants we assume that the points lie on some fixed constant-degree algebraic variety, and in others we consider arbitrary sets of points in 3-space. The case of points and curves has been considered in several previous studies, starting with Guth and Katz's work on points and lines [36]. Our results, which are based on a recent work of Guth and Zahl [37] concerning surfaces that are doubly ruled by curves, provide a grand generalization of all previous results. We reconstruct the bound for points and lines, and improve, in certain significant ways, recent bounds involving points and circles (in [50]) and points and arbitrary constant-degree algebraic curves (in [49]). While in these latter instances the bounds are not known (and are strongly suspected not) to be tight, our bounds are, in a certain sense, the best that can be obtained with this approach, given the current state of knowledge. In the case of points and surfaces, the incidence graph between them can contain large complete bipartite graphs, each involving points on some curve and surfaces containing this curve (unlike earlier studies, we do not rule out this possibility, which makes our approach more general). Our bounds estimate the total size of the vertex sets in such a complete bipartite graph decomposition of the incidence graph. In favorable cases, our bounds translate into actual incidence bounds. Overall, here too our results can be regarded as providing a “grand generalization” of most of the previous studies of (special instances of) this problem. As applications of our point-surface incidence bounds, we consider the problems of distinct and repeated distances determined by a set of n points in ℝ3, two of the most celebrated open problems in combinatorial geometry. We obtain new and improved bounds for two special cases, one in which the points lie on some algebraic variety of constant degree, and one involving distances between pairs in P1 × P2, where Pi is contained in a variety and P2 is arbitrary.

We describe a data structure for submatrix maximum queries in Monge matrices or partial Monge matrices, where a query seeks the maximum element in a contiguous submatrix of the given matrix. The structure, for an n × n Monge matrix, takes O ( n log n ) space and O ( n log n ) preprocessing time, and answers queries in O (log 2 n ) time. For partial Monge matrices, the space grows by α( n ), the preprocessing grows by α( n )log n (α( n ) is the inverse Ackermann function), and the query remains O (log 2 n ). Our design exploits an interpretation of the column maxima in a Monge (partial Monge, respectively) matrix as an upper envelope of pseudo-lines (pseudo-segments, respectively). We give two applications: (1) For a planar set of n points in an axis-parallel rectangle B , we build a data structure, in O ( n α( n )log 4 n ) time and O ( n α( n )log 3 n ) space, that returns, for a query point p , the largest-area empty axis-parallel rectangle contained in B and containing p , in O (log 4 n ) time. This improves substantially the nearly quadratic storage and preprocessing obtained by Augustine et al. [2010]. (2) Given an n -node arbitrarily weighted planar digraph, with possibly negative edge weights, we build, in O ( n log 2 n /log log n ) time, a linear-size data structure that supports edge-weight updates and graph-distance queries between arbitrary pairs of nodes in O ( n 2/3 log 5/3 n ) time per operation. This improves a previous algorithm of Fakcharoenphol and Rao [2006]. Our data structure has already been applied in a recent maximum flow algorithm for planar graphs in Borradaile et al. [2011].

Let H be a set of n non-vertical planes in three dimensions, and let r < n be a parameter. We give a simple alternative proof of the existence of a O(1/r)-cutting of the first n/r levels of (H), which consists of O(r) semi-unbounded vertical triangular prisms. The same construction yields an approximation of the (n/r)-level by a terrain consisting of O(r/∊3) triangular faces, which lies entirely between the levels (1 ± ∊)n/r. The proof does not use sampling, and exploits techniques based on planar separators and various structural properties of levels in three-dimensional arrangements and of planar maps. The proof is constructive, and leads to a simple randomized algorithm, that computes the terrain in O(n + r2∊–6 log3 r) expected time. An application of this technique allows us to mimic Matoušek's construction of cuttings in the plane [36], to obtain a similar construction of “layered” (1/r)-cutting of the entire arrangement (H), of optimal size O(r3). Another application is a simplified optimal approximate range counting algorithm in three dimensions, competing with that of Afshani and Chan [1].

Given n non-vertical lines in 3-space, their vertical depth (above/below) relation can contain cycles. We show that the lines can be cut into O(n3/2polylog n) pieces, such that the depth relation among these pieces is now a proper partial order. This bound is nearly tight in the worst case. As a consequence, we deduce that the number of pairwise non-overlapping cycles, namely, cycles whose xy-projections do not overlap, is O(n3/2polylog n); this bound too is almost tight in the worst case.

We show that the number of unit-area triangles determined by a set S of n points in the plane is O(n^{20/9}), improving the earlier bound O(n^{9/4}) of Apfelbaum and Sharir. We also consider two special cases of this problem: (i) We show, using a somewhat subtle construction, that if S consists of points on three lines, the number of unit-area triangles that S spans can be Omega(n^2), for any triple of lines (it is always O(n^2) in this case). (ii) We show that if S is a convex grid of the form A x B, where A, B are convex sets of n^{1/2} real numbers each (i.e., the sequences of differences of consecutive elements of A and of B are both strictly increasing), then S determines O(n^{31/14}) unit-area triangles.

Let F in Complex[x,y,z] be a constant-degree polynomial, and let A,B,C be sets of complex numbers with |A|=|B|=|C|=n. We show that F vanishes on at most O(n^{11/6}) points of the Cartesian product A x B x C (where the constant of proportionality depends polynomially on the degree of F), unless F has a special group-related form. This improves a theorem of Elekes and Szabo [ES12], and generalizes a result of Raz, Sharir, and Solymosi [RSS14a]. The same statement holds over R. When A, B, C have different sizes, a similar statement holds, with a more involved bound replacing O(n^{11/6}). This result provides a unified tool for improving bounds in various Erdos-type problems in combinatorial geometry, and we discuss several applications of this kind.

We give a fairly elementary and simple proof that shows that the number of incidences between m points and n lines in R^3, so that no plane contains more than s lines, is O(m^{1/2}n^{3/4} + m^{2/3}n^{1/3}s^{1/3} + m + n) (in the precise statement, the constant of proportionality of the first and third terms depends, in a rather weak manner, on the relation between m and n). This bound, originally obtained by Guth and Katz as a major step in their solution of Erdos's distinct distances problem, is also a major new result in incidence geometry, an area that has picked up considerable momentum in the past six years. Its original proof uses fairly involved machinery from algebraic and differential geometry, so it is highly desirable to simplify the proof, in the interest of better understanding the geometric structure of the problem, and providing new tools for tackling similar problems. This has recently been undertaken by Guth. The present paper presents a different and simpler derivation, with better bounds than those in Guth, and without the restrictive assumptions made there. Our result has a potential for applications to other incidence problems in higher dimensions.

We show that the number of incidences between m distinct points and n distinct lines in R4is O(2c√log m(m2/5n4/5+ m) + m1/2n1/2q1/4+ m2/3n1/3s1/3+ n), for a suitable absolute constant c, provided that no 2-plane contains more than s input lines, and no hyperplane or quadric contains more than q lines. The bound holds without the extra factor 2c√log mwhen m ≤ n6/7or m ≥ n5/3. Except for this possible factor, the bound is tight in the worst case. The context of this work is incidence geometry, a topic that has been widely studied for more than three decades, with strong connections to a variety of topics, from range searching in computational geometry to the Kakeya problem in harmonic analysis and geometric measure theory. The area has picked up considerable momentum in the past seven years, following the seminal works of Guth and Katz [12, 13], where the later work solves the point-line incidence problem in three dimensions, using new tools and techniques from algebraic geometry. This work extends their result to four dimensions. In doing so, it had to overcome many new technical hurdles that arise from the higher-dimensional context, by developing and adapting more advanced tools from algebraic geometry.

The Fréchet distance is a well-studied similarity measure between curves. The discrete Fréchet distance is an analogous similarity measure, defined for two sequences of m and n points, where the points are usually sampled from input curves. We consider a variant, called the discrete Fréchet distance with shortcuts , which captures the similarity between (sampled) curves in the presence of outliers. When shortcuts are allowed only in one noise-containing curve, we give a randomized algorithm that runs in O (( m + n ) 6/5 + ε ) expected time, for any ε > 0. When shortcuts are allowed in both curves, we give an O (( m 2/3 n 2/3 + m + n )log 3 ( m + n ))-time deterministic algorithm. We also consider the semicontinuous Fréchet distance with one-sided shortcuts, where we have a sequence of m points and a polygonal curve of n edges, and shortcuts are allowed only in the sequence. We show that this problem can be solved in randomized expected time O (( m + n ) 2/3 m 2/3 n 1/3 log ( m + n )). Our techniques are novel and may find further applications. One of the main new technical results is: Given two sets of points A and B in the plane and an interval I , we develop an algorithm that decides whether the number of pairs ( x , y ) ∈ A × B whose distance dist( x , y ) is in I is less than some given threshold L . The running time of this algorithm decreases as L increases. In case there are more than L pairs of points whose distance is in I , we can get a small sample of pairs that contain a pair at approximate median distance (i.e., we can approximately “bisect” I ). We combine this procedure with additional ideas to search, with a small overhead, for the optimal one-sided Fréchet distance with shortcuts, using a very fast decision procedure. We also show how to apply this technique for approximating distance selection (with respect to rank), and a somewhat more involved variant of this technique is used in the solution of the semicontinuous Fréchet distance with one-sided shortcuts. In general, the new technique can be applied to optimization problems for which the decision procedure is very fast but standard techniques like parametric search makes the optimization algorithm substantially slower.

The Fréchet distance is a well studied similarity measure between curves. The discrete Fréchet distance is an analogous similarity measure, defined for two sequences of m and n points, where the points are usually sampled from input curves. We consider a variant, called the discrete Fréchet distance with shortcuts, which captures the similarity between (sampled) curves in the presence of outliers. When shortcuts are allowed only in one noise-containing curve, we give a randomized algorithm that runs in O((m+n)6/5+ϵ) expected time, for any ϵ > 0. When shortcuts are allowed in both curves, we give an O((m2/3n2/3 + m + n) log3(m + n))-time deterministic algorithm.

Let D be a set of n disks in the plane. We present a data structure of size O(n) that can compute, for any query point q, the largest disk in D that contains q, in O(log n) time. The structure can be constructed in O(n log3 n) time. The optimal storage and query time of the structure improve several recent results on this and related problems [1, 2, 4].

Let p1, p2, p3 be three distinct points in the plane, and, for i = 1, 2, 3, let Ci be a family of n unit circles that pass through pi. We address a conjecture made by Székely, and show that the number of points incident to a circle of each family is O(n11/6), improving an earlier bound for this problem due to Elekes, Simonovits, and Szabó [4]. The problem is a special instance of a more general problem studied by Elekes and Szabó [5] (and by Elekes and Rónyai [3]).

In this paper we characterize real bivariate polynomials which have a small range over large Cartesian products. We show that for every constant-degree bivariate real polynomial f, either |f(A, B)| = Ω(n4/3), for every pair of finite sets A, B ⊂ R, with |A| = |B| = n (where the constant of proportionality depends on deg f), or else f must be of one of the special forms f(u, v) = h(φ(u) + ψ(v)), or f(u, v) = h(φ(u) · ψ(v)), for some univariate polynomials φ, ψ, h over R. This significantly improves a result of Elekes and Rónyai [7].

We show that the number of incidences between m distinct points and n distinct lines in R4 is at most

The Fréchet distance measures similarity between two curves $f$ and $g$ that takes into account the ordering of the points along the two curves: Informally, it is the minimum length of a leash required to connect a dog, walking along $f$, and its owner, walking along $g$, as they walk without backtracking along their respective curves from one endpoint to the other. The discrete Fréchet distance replaces the dog and its owner by a pair of frogs that can only reside on $m$ and $n$ specific stones, respectively. The stones are in fact sequences of points, typically sampled from the respective curves $f$ and $g$. These frogs hop from one stone to the next without backtracking, and the discrete Fréchet distance is the minimum length of a “leash” that connects the frogs and allows them to execute such a sequence of hops from the starting points to the terminal points of their sequences. The discrete Fréchet distance can be computed in $O(mn)$ time by a straightforward dynamic programming algorithm. We present the first subquadratic algorithm for computing the discrete Fréchet distance between two sequences of points in the plane. Assuming $m\le n$, the algorithm runs in $O(\frac{mn\log\log n}{\log n})$ time, in the word RAM model, using $O(n)$ storage. Our approach uses the geometry of the problem in a subtle way to encode legal positions of the frogs as states of a finite automaton.

We consider the following problem, which arises in many database and web-based applications: Given a set $P$ of $n$ points in a high-dimensional space $\mathbb{R}^d$ and a distance $r$, we want to report all pairs of points of $P$ at Euclidean distance at most $r$. We present two randomized algorithms, one based on randomly shifted grids, and the other on randomly shifted and rotated grids. The running time of both algorithms is of the form $C(d)(n+k)\log n$, where $k$ is the output size and $C(d)$ is a constant that depends on the dimension $d$. The $\log n$ factor is needed to guarantee, with high probability, that all neighbor pairs are reported and can be dropped if it suffices to report, in expectation, an arbitrarily large fraction of the pairs. When only translations are used, $C(d)$ is of the form $(a\sqrt{d})^d$ for some (small) absolute constant $a\approx 0.484$; this bound is worst-case tight, up to an exponential factor of about $2^d$. When both rotationsand translations are used, $C(d)$ can be improved to roughly $6.74^d$, getting rid of the superexponential factor $\sqrt{d}^d$. When the input set (lies in a subset of $d$-space that) has low doubling dimension $\delta$, the performance of the first algorithm improves to $C(d,\delta)(n+k)\log n$ (or to $C(d,\delta)(n+k)$), where $C(d,\delta) = O((ed/\delta)^\delta)$ for $\delta \le \sqrt{d}$. Otherwise, $C(d,\delta) = O( e^{\sqrt{d}} \sqrt{d}^\delta )$. We also present experimental results on several large data sets, demonstrating that our algorithms run significantly faster than all the leading existing algorithms for reporting neighbors.

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

Let C=C1,...,Cn} be a set of n pairwise-disjoint convex s-gons, for some constant s, and let p be a probability density function (pdf) over the non-negative reals. For each i, let Ki be the Minkowski sum of Ci with a disk of radius ri, where each ri is a random non-negative number drawn independently from the distribution determined by π. We show that the expected complexity of the union of K1,..,Kn is O(n log n), for any pdf p; the constant of proportionality depends on s, but not on the pdf. Next, we consider the following problem that arises in analyzing the vulnerability of a network under a physical attack. Let G=(V,E) be a planar geometric graph where E is a set of n line segments with pairwise-disjoint relative interiors. Let f: R -> [0,1] be an edge failure probability function, where a physical attack at a location x causes an edge e of E at distance r from x to fail with probability f(r); we assume that f is of the form f(x)=1-P(x), where P is a cumulative distribution function on the non-negative reals. The goal is to compute the most vulnerable location for G, i.e., the location of the attack that maximizes the expected number of failing edges of G. Using our bound on the complexity of the union of random Minkowski sums, we present a near-linear Monte-Carlo algorithm for computing a location that is an approximately most vulnerable location of attack for G.

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

The Fréchet distance is a similarity measure between two curves A and B that takes into account the location and ordering of the points along the two curves: Informally, it is the minimum length of a leash required to connect a dog, walking along A, and its owner, walking along B, as they walk without backtracking along their respective curves from one endpoint to the other. The discrete Fréchet distance replaces the dog and its owner by a pair of frogs that can only reside on n and m specific stones on the curves A and B, respectively. These frogs hop from one stone to the next without backtracking, and the discrete Fréchet distance is the minimum length of a “leash” that connects the frogs and allows them to execute such a sequence of hops. It can be computed in quadratic time by a straightforward dynamic programming algorithm. We present the first subquadratic algorithm for computing the discrete Fréchet distance between two sequences of points in the plane. Assuming m ≤ n, the algorithm runs in time, in the standard RAM model, using O(n) storage. Our approach uses the geometry of the problem in a subtle way to encode legal positions of the frogs as states of a finite automaton.

We consider the following problem, which arises in many database and web-based applications: Given a set P of n points in a high-dimensional space ℝd and a distance r, we want to report all pairs of points of P at Euclidean distance at most r. We present two randomized algorithms, one based on randomly shifted grids, and the other on randomly shifted and rotated grids. The running time of both algorithms is of the form C(d)(n + k) log n, where k is the output size and C(d) is a constant that depends on the dimension d. The log n factor is needed to guarantee, with high probability, that all neighbor pairs are reported, and can be dropped if it suffices to report, in expectation, an arbitrarily large fraction of the pairs. When only translations are used, C(d) is of the form , for some (small) absolute constant a ≈ 0.484; this bound is worst-case tight, up to an exponential factor of about 2d. When both rotations and translations are used, C(d) can be improved to roughly 6.74d, getting rid of the super-exponential factor . When the input set (lies in a subset of d-space that) has low doubling dimension δ, the performance of the first algorithm improves to C(d, δ)(n + k) log n (or to C(d, δ)(n + k)), where C(d, δ) = O((ed/δ)δ), for . Otherwise, . We also present experimental results on several large datasets, demonstrating that our algorithms run significantly faster than all the leading existing algorithms for reporting neighbors.

Let $P$ be a set of $n$ points in $\mathbb{R}^d$. We present a linear-size data structure for answering range queries on $P$ with constant-complexity semialgebraic sets as ranges, in time close to $O(n^{1-1/d})$. It essentially matches the performance of similar structures for simplex range searching, and, for $d\ge 5$, significantly improves earlier solutions by the first two authors obtained in 1994. This almost settles a long-standing open problem in range searching. The data structure is based on a partitioning technique of Guth and Katz [On the Erdös distinct distances problem in the plane, arXiv:1011.4105, 2010], which shows that for a parameter $r$, $1 < r \le n$, there exists a $d$-variate polynomial $f$ of degree $O(r^{1/d})$ such that each connected component of $\mathbb{R}^d\setminus Z(f)$ contains at most $n/r$ points of $P$, where $Z(f)$ is the zero set of $f$. We present an efficient randomized algorithm for computing such a polynomial partition, which is of independent interest and is likely to have additional applications.

Let P be a set of n points in the plane. We present an efficient algorithm for preprocessing P, so that, for a given query point q, we can quickly report the largest disk that contains q but its interior is disjoint from P. The storage required by the data structure is O(n log n), the preprocessing cost is O(n log2n), and a query takes O(log2n) time.

We derive improved upper bounds on the number of crossing-free straight-edge spanning cycles (also known as Hamiltonian tours and simple polygonizations) that can be embedded over any specific set of N points in the plane. More specifically, we bound the ratio between the number of spanning cycles (or perfect matchings) that can be embedded over a point set and the number of triangulations that can be embedded over it. The respective bounds are O(1.8181N) for cycles and O(1.1067N) for matchings. These imply a new upper bound of O(54.543N) on the number of crossing-free straight-edge spanning cycles that can be embedded over any specific set of N points in the plane (improving upon the previous best upper bound O(68.664N)). Our analysis is based on a weighted variant of Kasteleyn's linear algebra technique.

Let $P$ be a set of $n$ points in $\R^d$. We present a linear-size data structure for answering range queries on $P$ with constant-complexity semi algebraic sets as ranges, in time close to $O(n^{1-1/d})$. It essentially matches the performance of similar structures for simplex range searching, and, for $d\ge 5$, significantly improves earlier solutions by the first two authors obtained in~1994. This almost settles a long-standing open problem in range searching. The data structure is based on the polynomial-partitioning technique of Guth and Katz [arXiv:1011.4105], which shows that for a parameter $r$, $1

We study cross-graph charging schemes for graphs drawn in the plane. These are charging schemes where charge is moved across vertices of different graphs. Such methods have been recently applied to obtain various properties of triangulations that are embedded over a fixed set of points in the plane. We show how this method can be generalized to obtain results for various other types of graphs that are embedded in the plane. Specifically, we obtain a new bound of \(O^*\left(187.53^N \right)\) for the maximum number of crossing-free straight-edge graphs that can be embedded over any specific set of N points in the plane (improving upon the previous best upper bound 207.85 N in Hoffmann et al.[14]). We also derive upper bounds for numbers of several other types of plane graphs (such as connected and bi-connected plane graphs), and obtain various bounds on expected vertex-degrees in graphs that are uniformly chosen from the set of all crossing-free straight-edge graphs that can be embedded over a specific point set. We then show how to apply the cross-graph charging-scheme method for graphs that allow certain types of crossings. Specifically, we consider graphs with no set of k pairwise-crossing edges (more commonly known as k -quasi-planar graphs). For k = 3 and k = 4, we prove that, for any set S of N points in the plane, the number of graphs that have a straight-edge k -quasi-planar embedding over S is only exponential in N . These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

We describe a data structure for submatrix maximum queries in Monge matrices or Monge partial matrices, where a query specifies a contiguous submatrix of the given matrix, and its output is the maximum element of that submatrix. Our data structure for an n × n Monge matrix takes O(n log n) space, O(n log2 n) preprocessing time, and can answer queries in O(log2 n) time. For a Monge partial matrix the space bound and the preprocessing time both grow by the small factor α(n), where α(n) is the inverse Ackermann function. Our design exploits an interpretation of the column maxima in a Monge matrix (resp., Monge partial matrix) as an upper envelope of pseudo-lines (resp., pseudosegments). We give two applications for this data structure: (1) For a set of n points in a rectangle B in the plane, we build a data structure that, given a query point p, returns the largest-area empty axis-parallel rectangle contained in B and containing p, in O(log4 n) time. The preprocessing time is O(nα(n) log4 n), and the space required is O(nα(n) log3 n). This improves substantially a previous data structure of Augustine et al. [arXiv:1004.0558] that requires quadratic space. (2) Given an n-node arbitrarily weighted planar digraph, with possibly negative edge weights, we build, in O(n log2 n/log log n) time, a linear-size data structure that supports edge-weight updates and distance queries between arbitrary pairs of nodes (where the distance is minimum weight of a path in the graph between the pair of nodes), in O(n2/3 log5,3 n) time for each update and query. This improves the O(n4/5 log13/5 n)-time bound of Fakcharoenphol and Rao [JCSS 72, 2006]. Our data structure has already been applied in a recent maximum flow algorithm for planar graphs of Borradaile et al. [FOCS 2011], and we believe it will find additional applications.

We show that the number of geometric permutations of an arbitrary collection of n pairwise disjoint convex sets in ${\mathbb R}^d$, for $d\geq 3$, is $O(n^{2d-3}\log n)$, improving Wenger's 20-year-old bound of $O(n^{2d-2})$.

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

Let P be a simple polygon, and let Q be a set of points in P. We present an almost-linear time algorithm for computing a minimum cover of Q by disks that are contained in P. We then generalize the algorithm so that it can compute a minimum cover of Q by homothets of any fixed compact convex set ${\cal O}$ of constant description complexity that are contained in P. This improves previous results of Katz and Morgenstern [Lecture Notes in Comput. Sci. 5664, 2009, pp. 447–458]. We also consider the minimum disk-cover problem when Q is contained in a (sufficiently narrow) annulus and present a nearly linear algorithm for this case, too.

In a typical range-emptiness searching (resp., reporting) problem, we are given a set P of n points in $\mathbb{R}^d$, and we wish to preprocess it into a data structure that supports efficient range-emptiness (resp., reporting) queries, in which we specify a range $\sigma$, which, in general, is a semialgebraic set in $\mathbb{R}^d$ of constant description complexity, and we wish to determine whether $P\cap\sigma=\emptyset$, or to report all the points in $P\cap\sigma$. Range-emptiness searching and reporting arise in many applications and have been treated by Matoušek [Comput. Geom. Theory Appl., 2 (1992), pp. 169–186] in the special case where the ranges are half-spaces bounded by hyperplanes. As shown in Matoušek's work, the two problems are closely related, and they have solutions (for the case of half-spaces) with similar performance bounds. In this paper we extend the analysis to general semialgebraic ranges and show how to adapt Matoušek's technique without the need to linearize the ranges into a higher-dimensional space. This yields more efficient solutions to several useful problems, and we demonstrate the new technique in four applications with the following results: (i) An algorithm for ray shooting amid balls in $\mathbb{R}^3$, which uses $O(n)$ storage and $O^*(n)$ preprocessing (we use the notation $O^*(n^\gamma)$ to mean an upper bound of the form $C(\varepsilon)n^{\gamma+\varepsilon}$, which holds for any $\varepsilon>0$, where $C(\varepsilon)$ is a constant that depends on $\varepsilon$) and answers a query in $O^*(n^{2/3})$ time, improving the previous bound of $O^*(n^{3/4})$. (ii) An algorithm that preprocesses, in $O^*(n)$ time, a set P of n points in $\mathbb{R}^3$ into a data structure with $O(n)$ storage, so that, for any query line $\ell$ (or, for that matter, any simply shaped convex set), the point of P farthest from $\ell$ can be computed in $O^*(n^{1/2})$ time. This in turn yields an algorithm that computes the largest-area triangle spanned by P in time $O^*(n^{26/11})$, as well as nontrivial algorithms for computing the largest-perimeter or largest-height triangle spanned by P. (iii) An algorithm that preprocesses, in $O^*(n)$ time, a set P of n points in $\mathbb{R}^2$ into a data structure with $O(n)$ storage, so that, for any query $\alpha$-fat triangle $\Delta$, we can determine, in $O^*(1)$ time, whether $\Delta\cap P$ is empty. Alternatively, we can report, in $O^*(1)+O(k)$ time, the points of $\Delta\cap P$, where $k=|\Delta\cap P|$. (iv) An algorithm that preprocesses, in $O^*(n)$ time, a set P of n points in $\mathbb{R}^2$ into a data structure with $O(n)$ storage, so that, given any query semidisk c, or a circular cap larger than a semidisk, we can determine, in $O^*(1)$ time, whether $c\cap P$ is empty, or report the k points in $c\cap P$ in $O^*(1)+O(k)$ time. Adapting the recent techniques of [B. Aronov and S. Har-Peled, SIAM J. Comput., 38 (2008), pp. 899–921, B. Aronov, S. Har-Peled, and M. Sharir, On approximate halfspace range counting and relative epsilon-approximations, in Proceedings of the 23rd ACM Symposium Comput. Geom., 2007, pp. 327–336, B. Aronov and M. Sharir, SIAM J. Comput., 39 (2010), pp. 2704–2725], we can turn our solutions into efficient algorithms for approximate range counting (with small relative error) for the cases mentioned above. Our technique is closely related to the notions of nearest- or farthest-neighbor generalized Voronoi diagrams and of the union or intersection of geometric objects, where sharper bounds on the combinatorial complexity of (decompositions of complements of) these structures yield faster range-emptiness searching or reporting algorithms.

Let P be a set of n points in ℜ3. The 2-center problem for P is to find two congruent balls of the minimum radius whose union covers P. We present two randomized algorithms for computing a 2-center of P. The first algorithm runs in O(n3 log8 n) expected time, and the second algorithm runs in O(n2 log8 n/(1--r*/r0)3) expected time, where r* is the radius of the 2-center of P and r0 is the radius of the smallest enclosing ball of P. The second algorithm is faster than the first one as long as r* is not very close to r0, which is equivalent to the condition of the centers of the two balls in the 2-center of P not being very close to each other.

The best known upper bound on the number of topological changes in the Delaunay triangulation of a set of moving points in ℜ2 is (nearly) cubic, even if each point is moving with a fixed velocity. We introduce the notion of a stable Delaunay graph (SDG in short), a dynamic subgraph of the Delaunay triangulation, that is less volatile in the sense that it undergoes fewer topological changes and yet retains many useful properties of the full Delaunay triangulation. SDG is defined in terms of a parameter ± > 0, and consists of Delaunay edges pq for which the (equal) angles at which p and q see the corresponding Voronoi edge epq are at least ±. We prove several interesting properties of SDG and describe two kinetic data structures for maintaining it. Both structures use O*(n) storage. They process O*(n2) events during the motion, each in O*(1) time, provided that the points of P move along algebraic trajectories of bounded degree; the O*(·) notation hides multiplicative factors that are polynomial in 1/± and polylogarithmic in n. The first structure is simpler but the dependency on 1/± in its performance is higher.

We first describe a reduction from the problem of lower-bounding the number of distinct distances determined by a set S of s points in the plane to an incidence problem between points and a certain class of helices (or parabolas) in three dimensions. We offer conjectures involving the new setup, but are still unable to fully resolve them.

We present a simple randomized scheme for triangulating a set P of n points in the plane, and construct a kinetic data structure which maintains the triangulation as the points of P move continuously along piecewise algebraic trajectories of constant description complexity. Our triangulation scheme experiences an expected number of O(n2βs+2(n) log2 n) discrete changes, and handles them in a manner that satisfies all the standard requirements from a kinetic data structure: compactness, efficiency, locality and responsiveness. Here s is the maximum number of times where any specific triple of points of P can become collinear, βs+2(q) = λs+2(q)/q, and λs+2(q) is the maximum length of Davenport-Schinzel sequences of order s + 2 on n symbols. Thus, compared to the previous solution of Agarwal et al. [4], we achieve a (slightly) improved bound on the number of discrete changes in the triangulation. In addition, we believe that our scheme is simpler to implement and analyze.

We study the expected number of interior vertices of degree i in a triangulation of a point set S, drawn uniformly at random from the set of all triangulations of S, and derive various bounds and inequalities for these expected values. One of our main results is: For any set S of N points in general position, and for any fixed i, the expected number of vertices of degree i in a random triangulation is at least γiN, for some fixed positive constant γi (assuming that N > i and that at least some fixed fraction of the points are interior).

We show that the number of geometric permutations of an arbitrary collection of n pairwise disjoint convex sets in Rd, for d ≥ 3, is O(n2d-3log n), improving Wenger's 20 years old bound of O(n2d-2).

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

We present a simple scheme extending the shallow partitioning data structures of Matoušek, which supports efficient approximate halfspace range-counting queries in $\mathbb{R}^d$ with relative error $\varepsilon$. Specifically, the problem is, given a set P of n points in $\mathbb{R}^d$, to preprocess them into a data structure that returns, for a query halfspace h, a number t so that $(1-\varepsilon)|h\cap P|\leq t\leq(1+\varepsilon)|h\cap P|$. One of our data structures requires linear storage and $O(n^{1+\delta})$ preprocessing time, for any $\delta>0$, and answers a query in time $O(\varepsilon^{-\gamma}n^{1-1/\lfloor d/2\rfloor}2^{b\log^\ast n})$ for any $\gamma>2/\lfloor d/2\rfloor$; the choice of $\gamma$ and $\delta$ affects b and the implied constants. Several variants and extensions are also discussed. As presented, the construction of the structure is mostly deterministic, except for one critical randomized step, and so are the query, storage, and preprocessing costs. The quality of approximation, for every query, is guaranteed with high probability. The construction can also be fully derandomized, at the expense of increasing preprocessing time.

We establish a bound of $O(n^2k^{1+\varepsilon})$, for any $\varepsilon>0$, on the combinatorial complexity of the set $\mathcal{T}$ of line transversals of a collection $\mathcal{P}$ of k convex polyhedra in $\mathbb{R}^3$ with a total of n facets, and we present a randomized algorithm which computes the boundary of $\mathcal{T}$ in comparable expected time. Thus, when $k\ll n$, the new bounds on the complexity (and construction cost) of $\mathcal{T}$ improve upon the previously best known bounds, which are nearly cubic in n. To obtain the above result, we study the set $\mathcal{T}_{\ell_0}$ of line transversals which emanate from a fixed line $\ell_0$, establish an almost tight bound of $O(nk^{1+\varepsilon})$ on the complexity of $\mathcal{T}_{\ell_0}$, and provide a randomized algorithm which computes $\mathcal{T}_{\ell_0}$ in comparable expected time. Slightly improved combinatorial bounds for the complexity of $\mathcal{T}_{\ell_0}$ and comparable improvements in the cost of constructing this set are established for two special cases, both assuming that the polyhedra of $\mathcal{P}$ are pairwise disjoint: the case where $\ell_0$ is disjoint from the polyhedra of $\mathcal{P}$, and the case where the polyhedra of $\mathcal{P}$ are unbounded in a direction parallel to $\ell_0$. Our result is related to the problem of bounding the number of geometric permutations of a collection $\mathcal{C}$ of k pairwise-disjoint convex sets in $\mathbb{R}^3$, namely, the number of distinct orders in which the line transversals of $\mathcal{C}$ visit its members. We obtain a new partial result on this problem.

We study the shape matching problem under the Hausdorff distance and its variants. In the first part of the article, we consider two sets A,B of balls in R d , d =2,3, and wish to find a translation t that minimizes the Hausdorff distance between A+t , the set of all balls in A shifted by t , and B . We consider several variants of this problem. First, we extend the notion of Hausdorff distance from sets of points to sets of balls, so that each ball has to be matched with the nearest ball in the other set. We also consider the problem in the standard setting, by computing the Hausdorff distance between the unions of the two sets (as point sets). Second, we consider either all possible translations t (as is the standard approach), or consider only translations that keep the balls of A+t disjoint from those of B . We propose several exact and approximation algorithms for these problems. In the second part of the article, we note that the Hausdorff distance is sensitive to outliers, and thus consider two variants that are more robust: the root-mean-square (rms) and the summed Hausdorff distance. We propose efficient approximation algorithms for computing the minimum rms and the minimum summed Hausdorff distances under translation, between two point sets in R d . In order to obtain a fast algorithm for the summed Hausdorff distance, we propose a deterministic efficient dynamic data structure for maintaining an ϵ-approximation of the 1-median of a set of points in R d , under insertions and deletions.

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

We show that the number of unit-area triangles determined by a set of n points in the plane is O(n9/4+ε), for any ε>0, improving the recent bound O(n44/19) of Dumitrescu et al.

We establish a bound of O(n2k1+∊), for any ∊ > 0, on the combinatorial complexity of the set Ƭ of line transversals of a collection of k convex polyhedra in ℝ3 with a total of n facets, and present a randomized algorithm which computes the boundary of Ƭ in comparable expected time. Thus, when k ≪ n, the new bounds on the complexity (and construction cost) of Ƭ improve upon the previously best known bounds, which are nearly cubic in n. To obtain the above result, we study the set Ƭℓ0 of line transversals which emanate from a fixed line ℓ0, establish an almost tight bound of O(nk1+∊) on the complexity of Ƭℓ0, and provide a randomized algorithm which computes Ƭℓ0 in comparable expected time. Slightly improved combinatorial bounds for the complexity of Ƭℓ0, and comparable improvements in the cost of constructing this set, are established for two special cases, both assuming that the polyhedra of are pairwise disjoint: the case where ℓ0 is disjoint from the polyhedra of , and the case where the polyhedra of are unbounded in a direction parallel to ℓ0.

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

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

We present randomized algorithms for online conflict-free coloring (CF in short) of points in the plane, with respect to halfplanes, congruent disks, and nearly-equal axis-parallel rectangles. In all three cases, the coloring algorithms use O (log n ) colors, with high probability. We also present a deterministic algorithm for online CF coloring of points in the plane with respect to nearly-equal axis-parallel rectangles, using O (log 3 n ) colors. This is the first efficient (i.e, using polylog( n ) colors) deterministic online CF coloring algorithm for this problem.

We investigate the complexity of the outer face in arrangements of line segments of a fixed length in the plane, drawn uniformly at random within a square. We derive upper bounds on the expected complexity of the outer face, and establish a certain phase transition phenomenon during which the expected complexity of the outer face drops sharply as a function of the total number of segments. In particular we show that up till the phase transition the complexity of the outer face is almost linear in n, and that after the phase transition, the complexity of the outer face is roughly proportional to pn. Our study is motivated by the analysis of a practical point-location algorithm (so-called walk-along-a-line point-location algorithm) and indeed, it explains experimental observations of the behavior of the algorithm on arrangements of random segments.

The study of extremal problems on triangle areas was initiated in a series of papers by Erdös and Purdy in the early 1970s. Here we present new results on such problems, concerning the number of triangles of the same area that are spanned by finite point sets in the plane and in 3-space, and the number of distinct areas determined by the triangles.

We investigate algorithmic questions that arise in the statistical problem of computing lines or hyperplanes of maximum regression depth among a set of n points. We work primarily with a dual representation and find points of maximum undirected depth in an arrangement of lines or hyperplanes. An O(n d ) time and O(n d−1) space algorithm computes undirected depth of all points in d dimensions. Properties of undirected depth lead to an O(nlog 2 n) time and O(n) space algorithm for computing a point of maximum depth in two dimensions, which has been improved to an O(nlog n) time algorithm by Langerman and Steiger (Discrete Comput. Geom. 30(2):299–309, [2003]). Furthermore, we describe the structure of depth in the plane and higher dimensions, leading to various other geometric and algorithmic results.

We construct weak ε-nets of almost linear size for certain types of point sets. Specifically, for planar point sets in convex position we construct weak 1/r-nets of size O(rα(r)), where α(r) denotes the inverse Ackermann function. For point sets along the moment curve in ℝ d we construct weak 1/r-nets of size r · 2 poly(α(r)) , where the degree of the polynomial in the exponent depends (quadratically) on d. Our constructions result from a reduction to a new problem, which we call stabbing interval chains with j-tuples. Given the range of integers N = [1, n], an interval chain of length k is a sequence of k consecutive, disjoint, nonempty intervals contained in N. A j-tuple $\bar{P}$ = (p1,…,pj) is said to stab an interval chain C = I 1 …I k if each p i falls on a different interval of C. The problem is to construct a small-size family Z of j-tuples that stabs all k-interval chains in N. Let z (j) k (n) denote the minimum size of such a family Z. We derive almost-tight upper and lower bounds for z (j) k (n) for every fixed j; our bounds involve functions α m (n) of the inverse Ackermann hierarchy. Specifically, we show that for j = 3 we have z (3) k (n) = Θ(nα $\lfloor$k/2$\rfloor$ (n)) for all k ≥ 6. For each j≥4, we construct a pair of functions Pʹ j (m), Qʹ j (m), almost equal asymptotically, such that z (j) Pʹ j(m)(n) = O(nα m (n)) and z (j) Qʹ j(m)(n) = Ω(nα m (n)).

Let P be a set of n points in $\mathbb{R}^d$, so that each point is colored by one of C given colors. We present algorithms for preprocessing P into a data structure that efficiently supports queries of the following form: Given an axis-parallel box Q, count the number of distinct colors of the points of $P\cap Q$. We present a general and relatively simple solution that has a polylogarithmic query time and worst-case storage about $O(n^d)$. It is based on several interesting structural properties of the problem, which we establish here. We also show that for random inputs, the data structure requires almost linear expected storage. We then present several techniques for achieving space-time tradeoff. In $\mathbb{R}^2$, the most efficient solution uses fast matrix multiplication in the preprocessing stage. In higher dimensions we use simpler tradeoff mechanisms, which behave just as well. We give a reduction from matrix multiplication to the off-line version of problem, which shows that in $\mathbb{R}^2$ our time-space tradeoffs are reasonably sharp, in the sense that improving them substantially would improve the best exponent of matrix multiplication. Finally, we present a generalized matrix multiplication problem and show its intimate relation to counting colors in boxes in higher dimension.

We present simple, fully dynamic and kinetic data structures, which are variants of a dynamic two-dimensional range tree, for maintaining the closest pair and all nearest neighbors for a set of n moving points in the plane; insertions and deletions of points are also allowed. If no insertions or deletions take place, the structure for the closest pair uses O ( n log n ) space, and processes O ( n 2 β s +2 ( n )log n ) critical events, each in O (log 2 n ) time. Here s is the maximum number of times where the distances between any two specific pairs of points can become equal, β s ( q ) = λ s ( q )/ q , and λ s ( q ) is the maximum length of Davenport-Schinzel sequences of order s on q symbols. The dynamic version of the problem incurs a slight degradation in performance: If m ≥ n insertions and deletions are performed, the structure still uses O ( n log n ) space, and processes O ( mn β s +2( n )log 3 n ) events, each in O (log 3 n ) time. Our kinetic data structure for all nearest neighbors uses O ( n log 2 n ) space, and processes O ( n 2 β 2 s +2 ( n )log 3 n ) critical events. The expected time to process all events is O ( n 2 β s +2 2 ( n ) log 4 n ), though processing a single event may take Θ( n ) expected time in the worst case. If m ≥ n insertions and deletions are performed, then the expected number of events is O ( mn β 2 s +2 ( n ) log 3 n ) and processing them all takes O ( mn β 2 s +2 ( n ) log 4 n ). An insertion or deletion takes O ( n ) expected time.

Given a set S of n points in R 3 , a point x in R 3 is called center point of S if every closed halfspace whose bounding hyperplane passes through x contains at least ⌈ n /4⌉ points from S . We present a near-quadratic algorithm for computing the center region , that is the set of all center points, of a set of n points in R 3 . This is nearly tight in the worst case since the center region can have Ω( n 2 ) complexity. We then consider sets S of 3 n points in the plane which are the union of three disjoint sets consisting respectively of n red, n blue, and n green points. A point x in R 2 is called a colored Tverberg point of S if there is a partition of S into n triples with one point of each color, so that x lies in all triangles spanned by these triples. We present a first polynomial-time algorithm for recognizing whether a given point is a colored Tverberg point of such a 3-colored set S .

We consider the problem of bounding the maximum possible number fk,d(n) of k-simplices that are spanned by a set of n pointsin Rd and are similar to a given simplex. We first show that f2,3(n) = O(n13/6), and then tacklethe general case, and show that fd-2, d(n) = O(nd-8/5) and fd-1,d(n) = O*(nd-72/55), for any d.Our technique extends to derive bounds for other valuesof k and d, and we illustrate this by showing that f2,5(n)=O(n8/3).

Let C be a set of n axis-aligned cubes in R3, and let U(C) denote the union of C. We present an algorithmthat can compute the volume of U(C) in time O(n4/3 log n). The previously best known algorithm, by Overmars and Yap, computes the volume of the union ofany n axis-aligned boxes in R3 in O(n3/2log n) time.

The paper consists of two major parts. In the first part, we re-examine relative ε-approximations, previously studied in [12, 13, 18, 25], and their relation to certain geometric problems, most notably to approximate range counting. We give a simple constructive proof of their existence in general range spaces with finite VC dimension, and of a sharp bound on their size, close to the best known one. We then give a construction of smaller-size relative ε-approximations for range spaces that involve points and halfspaces in two and higher dimensions. The planar construction is based on a new structure--spanning trees with small relative crossing number, which we believe to be of independent interest. In the second part, we consider the approximate halfspace range-counting problem in Rd with relative error ε, and show that relative ε-approximations, combined with the shallow partitioning data structures of Matoušek, yields efficient solutions to this problem. For example, one of our data structures requires linear storage and O(n1+δ) preprocessing time, for any δ>0, and answers a query in time O(ε-γn1-1/⌊ d/2 ⌋ 2b log* n), for any γ > 2/⌊ d/2⌋ the choice of γ and δ affects b and the implied constants. Several variants and extensions are also discussed.

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

We consider the problem of approximating a set P of n points in Rd by a collection of j-dimensional flats, andextensions thereof, under the standard median / mean / centermeasures, in which we wish to minimize, respectively, the sum of thedistances from each point of P to its nearest flat, the sum of thesquares of these distances, or the maximal such distance.Such problems cannot be approximated unless P=NP but do allowbi-criteria approximations where one allows some leeway in both the numberof flats and the quality of the objective function.We give a very simple bi-criteria approximation algorithm, which producesat most α(k,j,n) = (k j log n)O(j) flats, which exceeds the optimalobjective value for any k j-dimensional flats by a factor of nomore than β(j)= 2O(j). Given this bi-criteria approximation, wecan use it to reduce the approximation factor arbitrarily, at the costof increasing the number of flats. Our algorithm hasmany advantages over previous work, in that it is muchmore widely applicable (wider set of objective functions and classes ofclusters) and much more efficient -- reducing the running time bound from O(n Poly(k,j)) to nd · (jk)O(j).Our algorithm is randomized and successful with probability 1/2(easily boosted to probabilities arbitrary close to 1).

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

We consider an online version of the conflict‐free coloring of a set of points on the line, where each newly inserted point must be assigned a color upon insertion, and at all times the coloring has to be conflict‐free, in the sense that in every interval I there is a color that appears exactly once in I. We present deterministic and randomized algorithms for achieving this goal, and analyze their performance, that is, the maximum number of colors that they need to use, as a function of the number n of inserted points. We first show that a natural and simple (deterministic) approach may perform rather poorly, requiring $\Omega(\sqrt{n})$ colors in the worst case. We then derive two efficient variants of this simple algorithm. The first is deterministic and uses $O(\log^2 n)$ colors, and the second is randomized and uses $O(\log n)$ colors with high probability. We also show that the $O(\log^2 n)$ bound on the number of colors used by our deterministic algorithm is tight on the worst case. We also analyze the performance of the simplest proposed algorithm when the points are inserted in a random order and present an incomplete analysis that indicates that, with high probability, it uses only $O(\log n)$ colors. Finally, we show that in the extension of this problem to two dimensions, where the relevant ranges are disks, n colors may be required in the worst case.

We show that if the number I of incidences between m points and n planes in $\mathbb{R}^3$ is sufficiently large, then the incidence graph (which connects points to their incident planes) contains a large complete bipartite subgraph involving r points and s planes, so that $rs \ge \frac{I^2}{mn} - a(m+n)$, for some constant $a>0$. This is shown to be almost tight in the worst case because there are examples of arbitrarily large sets of points and planes where the largest complete bipartite incidence subgraph records only $\frac{I^2}{mn}-\frac{m+n}{16}$ incidences. We also take some steps towards generalizing this result to higher dimensions.

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

In a Batched Colored Intersection Searching Problem (CI), one is given a set of n geometric objects (of a certain class). Each object is colored by one of c colors, and the goal is to report all pairs of colors (c1,c2) such that there are two objects, one colored c1 and one colored c2, that intersect each other. We also consider the bipartite version of the problem, where we are interested in intersections between objects of one class with objects of another class (e.g., points and halfspaces).In a Sparse Rectangular Matrix Multiplication Problem (SRMM), one is given an n1×n2 matrix A and an n2×n3 matrix B, each containing at most m non-zero entries, and the goal is to compute their product AB.In this paper we present a technique for solving CI problems over a wide range of classes of geometric objects. The basic idea is first to use some decomposition method, such as geometric cuttings, to represent the intersection graph of the objects as a union of bi-cliques. Then, in each of these bi-cliques, contract all vertices of the same color. Finally, use an algorithm for sparse matrix multiplication (adapted from Yuster and Zwick [20]) to compute the union of the bi-cliques. We apply the technique to segments in R1, to segments in R2, to points and halfplanes in R2, and, more generally, to points and halfspaces in Rd, for any fixed d. However, the technique extends to colored intersection searching in any class (or pair of classes) of geometric objects of constant descriptive complexity.In particular, using our technique we obtain an algorithm that reports all the pairs of intersecting colors for n points and n halfplanes in R2, that are colored by c colors, in O(n4/3c0.46) time when n ≥ c1.44, and in O(n1.04c0.9 + c2) time when n≤c1.44.The algorithms that we give for CI use the algorithm for SRMM as a black box, which means that any improved algorithm for SRMM immediately leads to an improved algorithm for all colored intersection problems that our method applies to. We also show that the complexity of computing all intersecting colors in a set of segments on the real line is identical, up to a polylogarithmic multiplicative factor, to the complexity of SRMM with the appropriate parameters.

The overlay of 2≤m≤d minimization diagrams of n surfaces in Rd is isomorphic to a substructure of a suitably constructed minimization diagram of mn surfaces in Rd+m−1. This elementary observation leads to a new bound on the complexity of the overlay of minimization diagrams of collections of d-variate semi-algebraic surfaces, a tight bound on the compleity of the overlay of minimization diagrams of collections of hyperplanes, and faster algorithms for constructing such overlays. Further algoithmic implications are discussed.

We present an optimal-time algorithm for computing (an implicit representation of) the shortest-path map from a fixed source s on the surface of a convex polytope P in three dimensions. Our algorithm runs in O(n log n) timeandrequires O(n log n) space, where n is the number of edges of P. The algorithm is based on the O(n log n) algorithm of Hershberger and Suri for shortest paths in the plane [11], and similarly follows the continuous Dijkstra paradigm, which propagates a “wavefront ” from s along ∂P. Thisiseffected by generalizing the concept of conforming subdivision of the free space used in [11], and adapting it for the case of a convex polytope in R 3, allowing the algorithm to accomplish the propagation in discrete steps, between the “transparent” edges of the subdivision. The algorithm constructs a dynamic version of Mount’s data structure [16] that implicitly encodes the shortest paths from s to all other points of the surface. This structure allows us to answer single-source shortest-path queries, where the length of the path, as well as its combinatorial type, can be reported in O(log n) time; the actual path π can be reported in additional O(k) time, where k is the number of polytope edges crossed by π. The algorithm generalizes to the case of m source points to yield an implicit representation of the geodesic Voronoi diagram of m sites on the surface of P, in time O((n + m)log(n + m)), so that the site closest to a query point can be reported in time O(log(n + m)).

Let S be a finite set of n + 3 points in general position in the plane, with 3 extreme points and n interior points. We consider triangulations drawn uniformly at random from all triangulations of S, and investigate the expected number, ˆvi, of interior points of degree i in such a triangulation. We provide bounds that are linear in n on these numbers. In particular, n/43 ≤ ˆv3 ≤ (2n + 3)/5. Moreover, we relate these results to the question about the maximum and minimum possible number of triangulations in such a set S, and show that the number of triangulations of any set of n points in the plane is at most 43 n, thereby improving on a previous bound by Santos and Seidel.

We develop efficient (1 + epsiv)-approximation algorithms for generalized facility location problems. Such facilities are not restricted to being points in Ropf, and can represent more complex structures such as linear facilities (lines in Ropfd, j-dimensional flats), etc. We introduce coresets for weighted (point) facilities. These prove to be useful for such generalized facility location problems, and provide efficient algorithms for their construction. Applications include: k-mean and k-median generalizations, i.e., find k lines that minimize the sum (or sum of squares) of the distances from each input point to its nearest line. Other applications are generalizations of linear regression problems to multiple regression lines, new SVD/PCA generalizations, and many more. The results significantly improve on previous work, which deals efficiently only with special cases. Open source code for the algorithms in this paper is also available

Let S be a set of n points in $\reals^2$. Given an integer $1 \le k \le n$, we wish to find a maximally separated subset $I \subseteq S$ of size k; this is a subset for which the minimum among the ${k\choose 2}$ pairwise distances between its points is as large as possible. The decision problem associated with this problem is to determine whether there exists $I\subseteq S$, $|I|=k$, so that all ${k\choose 2}$ pairwise distances in I are at least 2. This problem can also be formulated in terms of disk‐intersection graphs: Let D be the set of unit disks centered at the points of S. The disk‐intersection graph G of D has as edges all pairs of disks with nonempty intersection. Any set I with the above properties is then the set of centers of disks that form an independent set in the graph G. This problem is known to be NP‐complete if k is part of the input. In this paper we first present a linear‐time $\eps$‐approximation algorithm for any constant k. Next we give exact algorithms for the cases $k=3$ and $k=4$ that run in time $O(n^{4/3}\polylog(n))$. We also present a simpler $n^{O(\sqrt{k})}$‐time exact algorithm (as compared with the recent algorithm in [J. Alber and J. Fiala, J. Algorithms, 52 (2004), pp. 134–151]) for arbitrary values of k.

We show that a set of n points in the plane has at most $O(10.05^n)$ perfect matchings with crossing‐free straight‐line embedding. The expected number of perfect crossing‐free matchings of a set of n points drawn independently and identically distributed from an arbitrary distribution in the plane is at most $O(9.24^n)$. Several related bounds are derived: (a) The number of all (not necessarily perfect) crossing‐free matchings is at most $O(10.43^n)$. (b) The number of red‐blue perfect crossing‐free matchings (where the points are colored red or blue and each edge of the matching must connect a red point with a blue point) is at most $O(7.61^n)$. (c) The number of left‐right perfect crossing‐free matchings (where the points are designated as left or right endpoints of the matching edges) is at most $O(5.38^n)$. (d) The number of perfect crossing‐free matchings across a line (where all the matching edges must cross a fixed halving line of the set) is at most $4^n$. These bounds are employed to infer that a set of n points in the plane has at most $O(86.81^n)$ crossing‐free spanning cycles (simple polygonizations) and at most $O(12.24^n)$ crossing‐free partitions (these are partitions of the point set so that the convex hulls of the individual parts are pairwise disjoint). We also derive lower bounds for some of these quantities.

A finite collection of x-monotone unbounded Jordan curves in the plane is called a family of pseudo-lines if every pair of curves intersect in at most one point, and the two curves cross each other there. Let L be such a collection of n pseudo-lines, and let P be a set of m points in $\reals^2$. Extending a result of Goodman [Discrete Math., 32 (1980), pp. 27--35], we define a duality transform that maps L to a set L* of points in $\reals^2$ and P to a set P* of (x-monotone) pseudo-lines in $\reals^2$, so that the incidence and the "above-below" relations between the points and the pseudo-lines are preserved. We present an efficient algorithm for computing the dual arrangement {\eus A}$(P^*)$ under an appropriate model of computation. We also present a dynamic data structure for reporting, in $O(m^\eps + k)$ time, all k points of P that lie below a query arc, which is either a circular arc or a portion of the graph of a polynomial of fixed degree. This result is needed for computing the dual arrangement for certain classes of pseudo-lines arising in several applications, but is also interesting in its own right. We present a few applications of our dual arrangement algorithm, such as computing incidences between points and pseudo-lines and computing a subset of faces in a pseudo-line arrangement. Next, we present an efficient algorithm for cutting a set of circles into arcs so that every pair of arcs intersect in at most one point, i.e., the resulting arcs constitute a collection of pseudo-segments. By combining this algorithm with our algorithm for computing the dual arrangement of pseudo-lines, we obtain efficient algorithms for several problems involving arrangements of circles or circular arcs, such as reporting or counting incidences between points and circles and computing a set of marked faces in arrangements of circles.

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

We introduce $(1/r)$-cuttings for collections of surfaces in 3-space, such that the cuttings are sensitive to an additional collection of curves. Specifically, let S be a set of n surfaces and let C be a set of m curves in $\mathbb{R}^3$, all of constant description complexity. Let $1\le r\le \min\{m,n\}$ be a given parameter. We show the existence of a $(1/r)$-cutting $\Xi$ of S of size $O(r^{3+\varepsilon})$, for any $\varepsilon>0$, such that the number of crossings between the curves of C and the cells of $\Xi$ is $O(mr^{1+\varepsilon})$. The latter bound improves, by roughly a factor of r, the bound that can be obtained for cuttings based on vertical decompositions. We view curve-sensitive cuttings as a powerful tool for various scenarios that involve curves and surfaces in three dimensions. As a preliminary application, we use the construction to obtain a bound of $O(m^{1/2}n^{2+\varepsilon})$, for any $\varepsilon>0$, on the complexity of the multiple zone of m curves in the arrangement of n surfaces in 3-space. After the conference publication of this paper [V. Koltun and M. Sharir, Proceedings of the 19th ACM Symposium on Computational Geometry, 2003, pp. 136--143], curve-sensitive cuttings were applied to derive an algorithm for efficiently counting triple intersections among planar convex objects in three dimensions [E. Ezra and M. Sharir, Proceedings of the 20th ACM Symposium onComputational Geometry, 2004, pp. 210--219], and we expect additional applications to arise in the future.

We present a new analysis of the worst-case cost of path compression, which is an operation that is used in various well-known "union-find" algorithms. In contrast to previous analyses which are essentially based on bottom-up approaches, our method proceeds top-down, yielding recurrence relations from which the various bounds arise naturally. In particular the famous quasi-linear bound involving the inverse Ackermann function can be derived without having to introduce the Ackermann function itself.

We show that the maximum number of occurrences of a given angle in a set of n points in $\mathbb{R}^3$ is $O(n^{7/3})$ and that a right angle can actually occur $\Omega(n^{7/3})$ times. We then show that the maximum number of occurrences of any angle different from $\pi/2$ in a set of n points in $\mathbb{R}^4$ is $O(n^{5/2}\beta(n))$, where $\beta(n) = 2^{O(\alpha(n)^2)}$ and $\alpha(n)$ is the inverse Ackermann function.

Let B be a set of n unit balls in ℝ3. We show that the combinatorial complexity of the space of lines in ℝ3 that avoid all the balls of B is O(n 3+e), for any ε0. This result has connections toproblems in visibility, ray shooting, motion planning andgeometric optimization.

We present a near-quadratic algorithm for computing the center regionof a set of n points in three dimensions. This is nearly tight inthe worst case since the center region can have Ω(n2) complexity. We then consider the problem of recognizing whether a given point q is a colored Tverberg point of a set of n colored points in the plane, and present the first polynomial-time algorithm for this problem.

A compact body c in ℝd is κ-round if for every point p∈ ∂c there exists a closed ball that contains p, is contained in c, and has radius κ diam c. We show that, for any fixed κ>0, the combinatorial complexity of the union of n κ-round, not necessarily convex objects in ℝ3 (resp., in ℝ4) of constant description complexity is O(n2+ε) (resp., O(n3+ε)) for any ε>0, where the constant of proportionality depends on ε, κ, and the algebraic complexity of the objects. The bound is almost tight.

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

We revisit the problem of computing shortest obstacle-avoiding paths among obstacles in three dimensions. We prove new hardness results, showing, e.g., that computing Euclidean shortest paths among sets of "stacked" axis-aligned rectangles is NP-complete, and that computing L1-shortest paths among disjoint balls is NP-complete. On the positive side, we present an efficient algorithm for computing an L1-shortest path between two given points that lies on or above a given polyhedral terrain. We also give polynomial-time algorithms for some versions of stacked polygonal obstacles that are "terrain-like" and analyze the complexity of shortest path maps in the presence of parallel halfplane "walls.

Let P be a set of n points in ℝ3, not all in a common plane. We solve a problem of Scott (1970) by showing that the connecting lines of P assume at least 2n-7 different directions if n is even and at least 2n-5 if n is odd. The bound for odd n is sharp.

Let P be a set of n points in general position in the plane. Let Xk(P) denote the number of empty convex κ-gons determined by P. We derive, using elementary proof techniques, several equalities and inequalities involving the quantities Xk(P) and several related quantities. Most of these equalities and inequalities are new, except for a couple that have been proved earlier using a considerablymore complex machinery from matroid and polytope theory,algebraic topology and commutative algebra. Some of these relationships are also extended to higher dimensions. We present several implications of these relationships, and discuss their connection with several long-standing open problems, the most notorious of which is the existence of an empty convex hexagon in any point set with sufficiently many points.

Some of the first routing algorithms for position-aware wireless networks used the Delaunay triangulation of the point-locations of the network's nodes as the underlying connectivity graph. Later on these solutions were considered impractical because the Delaunay triangulation may in general contain arbitrarily long edges and because calculating the Delaunay triangulation may require a global view of the network. Many other algorithms were then suggested for geometric routing, often assuming random placement of network nodes for analysis or simulation [27, 5, 28, 15]. But as we show, when the nodes are uniformly placed in the unit disk the Delaunay triangulation does not contain long edges, it is easy to compute locally and it is in many ways optimal for geometric routing and flooding.In particular, we prove that with high probability the maximal length of an edge in Del(P), the Delaunay triangulation of a set P of n nodes uniformly placed in the unit disk, is O(3√3log novern), and that the expected sum of squares of all the edges in Del(P) is O(1). These geometric results imply that for wireless networks, randomly distributed in a unit disk (1) computing the Delaunay triangulation locally is asymptotically easy; (2) simple "face routing" through the Delaunay triangulation optimizes, up to poly-logarithmic factors, the energy load on the nodes, and (3) flooding the network, an operation quite common in sensor nets, is with high probability optimal up to a constant factor. The last property is particularly important for geocasting because the Delaunay triangulation is known to be a spanner.

A collection of simple closed Jordan curves in the plane is called a family of pseudo-circles if any two of its members intersect at most twice. A closed curve composed of two subarcs of distinct pseudo-circles is said to be an empty lens if the closed Jordan region that it bounds does not intersect any other member of the family. We establish a linear upper bound on the number of empty lenses in an arrangement of n pseudo-circles with the property that any two curves intersect precisely twice. We use this bound to show that any collection of n x -monotone pseudo-circles can be cut into O ( n 8/5 ) arcs so that any two intersect at most once; this improves a previous bound of O ( n 5/3 ) due to Tamaki and Tokuyama. If, in addition, the given collection admits an algebraic representation by three real parameters that satisfies some simple conditions, then the number of cuts can be further reduced to O ( n 3/2 (log n ) O (α( s ( n )) ), where α( n ) is the inverse Ackermann function, and s is a constant that depends on the the representation of the pseudo-circles. For arbitrary collections of pseudo-circles, any two of which intersect exactly twice, the number of necessary cuts reduces still further to O ( n 4/3 ). As applications, we obtain improved bounds for the number of incidences, the complexity of a single level, and the complexity of many faces in arrangements of circles, of pairwise intersecting pseudo-circles, of arbitrary x -monotone pseudo-circles, of parabolas, and of homothetic copies of any fixed simply shaped convex curve. We also obtain a variant of the Gallai--Sylvester theorem for arrangements of pairwise intersecting pseudo-circles, and a new lower bound on the number of distinct distances under any well-behaved norm.

We investigate the worst-case behavior of the simplex algorithm on linear programs with three variables, that is, on 3-dimensional simple polytopes. Among the pivot rules that we consider, the "random edge" rule yields the best asymptotic behavior as well as the most complicated analysis. All other rules turn out to be much easier to study, but also produce worse results: Most of them show essentially worst-possible behavior; this includes both Kalai's "random-facet" rule, which without dimension restriction is known to be subexponential, and Zadeh's deterministic history-dependent rule, for which no nonpolynomial instances in general dimensions have been found so far.

We study the shape matching problem under the Hausdorff distance and its variants. Specifically, we consider two sets A,B of balls in Rd, d=2,3, and wish to find a translation t that minimizes the Hausdorff distance between A+t, the set of all balls in A shifted by t, and B. We consider several variants of this problem. First, we extend the notion of Hausdorff distance from sets of points to sets of balls, so that each ball has to be matched with the nearest ball in the other set. We also consider the problem in the standard setting, by computing the Hausdorff distance between the unions of the two sets (as point sets). Second, we consider either all possible translates t (as is the standard approach), or consider only translations that keep the balls of A+t disjoint from those of B. We propose several exact and approximation algorithms for these problems. Since the Hausdorff distance is sensitive to outliers, we also propose efficient approximation algorithms for computing the minimum root mean-square (rms) and the minimum summed Hausdorff distance, under translation, between two point sets in Rd. In order to obtain a fast algorithm for the summed Hausdorff distance, we propose a deterministic efficient dynamic data structure for maintaining an e-approximation of the 1-median of a set of points, under insertion and deletion.

We introduce (1/r)-cuttings for collections of surfaces in 3-space that are sensitive to an additional collection of curves. Specifically, let S be a set of n surfaces in R 3 of constant description complexity, and let C be a set of m curves in R 3 of constant description complexity. Let 1= r = min{ m,n } be a given parameter. We show the existence of a (1/ r )-cutting ? of S of size O ( r 3+e ), for any e > 0 , such that the number of crossings between the curves of C and the cells of ? is O ( m 1+e ). The latter bound improves, by roughly a factor of r , the bound that can be obtained for cuttings based on vertical decompositions.We view curve-sensitive cuttings as a powerful tool that is potentially useful in various scenarios that involve curves and surfaces in three dimensions. As a preliminary application, we use the construction to obtain a bound of O ( m 1/2+e n 2+e ), for any e > 0 , on the complexity of the multiple zone of m curves in the arrangement of n surfaces in 3-space

Let P be a set of n points in R3, not all of which are in a plane and no three on a line. We partially answer a question of Scott (1970) by showing that the connecting lines of P assume at least 2n-3 different directions if n is even and at least 2n-2 if n is odd. These bounds are sharp. The proof is based on a far-reaching generalization of Ungar's theorem concerning the analogous problem in the plane.

We show that a collection of lines in 3-space can be cut into a subquadratic number of pieces, such that all depth cycles defined by triples of lines are eliminated. This partially resolves a long-standing open problem in computational geometry, motivated by hidden-surface removal in computer graphics.

Improving an old result of Clarkson et al., we show that the number of distinct distances determined by a set P of n points in three-dimensional space is Ω(n77/141-ε)=Ω(n0.546), for any ε>0. Moreover, there always exists a point p ∈ P from which there are at least these many distinct distances to the remaining elements of P. The same result holds for points on the three-dimensional sphere. As a consequence, we obtain analogous results in higher dimensions.

We show that the combinatorial complexity of the Euclidean Voronoi diagram of n lines in $\mathbb{R}^3$ that have at most c distinct orientations is $O(c^3n^{2+\varepsilon})$ for any $\varepsilon>0$. This result is a step toward proving the long-standing conjecture that the Euclidean Voronoi diagram of lines in three dimensions has near-quadratic complexity. It provides the first natural instance in which this conjecture is shown to hold. In a broader context, our result adds a natural instance to the (rather small) pool of instances of general 3-dimensional Voronoi diagrams for which near-quadratic complexity bounds are known.

We obtain a near-tight bound of $O(n^{3+\varepsilon})$ for any $\varepsilon>0$ on the complexity of the overlay of the minimization diagrams of two collections of surfaces in four dimensions. This settles a long-standing problem in the theory of arrangements, most recently cited by Agarwal and Sharir [in Handbook of Computational Geometry, North--Holland, Amsterdam, 2000, pp. 49--119, Open Problem 2], and substantially improves and simplifies a result previously published by the authors [in Proceedings of the rm13th ACM--SIAM Symposium on Discrete Algorithms, ACM, New York, SIAM, Philadelphia, 2002, pp. 810--819]. Our bound is obtained by introducing a new approach to the analysis of combinatorial structures arising in geometric arrangements of surfaces. This approach, which we call the "partition technique," is based on k-fold divide and conquer, in which a given collection ${\cal F}$ of n surfaces is partitioned into k subcollections ${\cal F}_i$ of n/k surfaces each, and the complexity of the relevant combinatorial structure in ${\cal F}$ is recursively related to the complexities of the corresponding structures in each of the ${\cal F}_i$'s. We introduce this approach by applying it first to obtain a new simple proof for the known near-quadratic bound on the complexity of an overlay of two minimization diagrams of collections of surfaces in $\mathbb{R}^3$, thereby simplifying the previously available proof [P. K. Agarwal, O. Schwarzkopf, and M. Sharir, Discrete Comput. Geom., 15 (1996), pp. 1--13]. The main new bound on overlays has numerous algorithmic and combinatorial applications, some of which are presented in this paper.

(MATH) We show that the number of incidences between m distinct points and n distinct circles in $\reals^3$ is O(m 4/7 n 17/21+m 2/3 n 2/3+m+n); the bound is optimal for m n 3/2. This result extends recent work on point-circle incidences in the plane, but its proof requires a different analysis. The bound improves upon a previous bound, noted by Akutsu et al. [2] and by Agarwal and Sharir [1], but it is not as sharp (when m is small) as the recent planar bound of Aronov and Sharir [3]. Our analysis extends to yield the same bound (a) on the number of incidences between m points and n circles in any dimension d≥ 3, and (b) on the number of incidences between m points and n arbitrary convex plane curves in $\reals^d$, for any d≥ 3, provided that no two curves are coplanar. Our results improve the upper bound on the number of congruent copies of a fixed tetrahedron in a set of n points in 4-space, and were already used to obtain a lower bound for the number of distinct distances in a set of n points in 3-space.

(MATH) We show that the combinatorial complexity of the Euclidean Voronoi diagram of n lines in $\reals3 that have at most c distinct orientations, is O(c 4 n 2+ε), for any ε>0. This result is a step towards proving the long-standing conjecture that the Euclidean Voronoi diagram of lines in three dimensions has near-quadratic complexity. It provides the first natural instance in which this conjecture is shown to hold. In a broader context, our result adds a natural instance to the (rather small) pool of instances of general 3-dimensional Voronoi diagrams for which near-quadratic complexity bounds are known.

We show that that the complexity of the Voronoi diagram of a collection of disjoint polyhedra in 3-space that have n vertices overall, under a convex distance function induced by a polyhedron with O(1) facets, is O(n 2+ε), for any ε>0. We also show that when the sites are n segments in 3-space, this complexity is O(n 2 α(n) log n). This generalizes previous results by Chew et al. [9] and by Aronov and Sharir [4], and solves an open problem put forward by Agarwal and Sharir [2]. Specific distance functions for which our results hold are the L 1 and the L ∞ metrics. These results imply that we can preprocess a collection of polyhedra as above into a near-quadratic data structure that can answer δ-approximate Euclidean nearest-neighbor queries amidst the polyhedra in time O(log (n/δ)), for an arbitrarily small δ>0.

(MATH) A collection of simple closed Jordan curves in the plane is called a family of pseudo-circles if any two of its members intersect at most twice. A closed curve composed of two subarcs of distinct pseudo-circles is said to be an empty lens if it does not intersect any other member of the family. We establish a linear upper bound on the number of empty lenses in an arrangement of n pseudo-circles with the property that any two curves intersect precisely twice. Enhancing this bound in several ways, and combining it with the technique of Tamaki and Tokuyama [16], we show that any collection of n pseudo-circles can be cut into $\bx$ arcs so that any two intersect at most once, provided that the given pseudo-circles are x-monotone and admit an algebraic representation by three real parameters; here $\alpha(n)$ is the inverse Ackermann function, and s is a constant that depends on the algebraic degree of the representation of the pseudo-circles (s=2 for circles and parabolas). For arbitrary collections of pseudo-circles, any two of which intersect twice, the number of necessary cuts reduces to O(n 4/3). As applications, we obtain improved bounds for the number of point-curve incidences, the complexity of a single level, and the complexity of many faces in arrangements of circles, pairwise intersecting pseudo-circles, parabolas, and families of homothetic copies of a fixed convex curve. We also obtain a variant of the Gallai-Sylvester theorem for arrangements of pairwise intersecting pseudo-circles, and a new lower bound for the number of distinct distances among n points in the plane under any simply-defined norm or convex distance function.

(MATH) Given a set L of n lines in $\reals^3$, let JL denote the set of all joints of L; joints are points in $\reals^3$ that are incident to at least three non-coplanar lines in L. We show that there are at most O(n 5/3) incidences between JL and L.(MATH) This result leads to related questions about incidences between L and a set P of m points in $\reals^3$: First, we associate with every point p ε P the minimum number of planes it takes to cover all lines incident to p. Then the sum of these numbers is at most $$ O(m^4/7n^5/7+m+n) ~. $$ Second, if each line forms a fixed given non-zero angle with the xy-plane---we say the lines are equally inclined--- then the number of (real) incidences is at most $$ O(\min\m^3/4n^1/2\kappa(m),m^4/7n^5/7\ + m + n) ~, $$ where $\kappa(m) = (\log m)^O(\alpha^2(m))$, and $\alpha(m)$ is the slowly growing inverse Ackermann function. These bounds are smaller than the tight Szemerédi-Trotter bound for point-line incidences in $\reals^2$, unless both bounds are linear. They are the first results of that type on incidences between points and 1-dimensional objects in $\reals^3$. This research was stimulated by a question raised by G. Elekes.

We obtain a near-tight bound of O(n/sup 3+/spl epsiv//), for any /spl epsiv/ > 0, on the complexity of the overlay of the minimization diagrams of two collections of surfaces in four dimensions. This settles a long-standing problem in the theory of arrangements, most recently cited by Agarwal and Sharir (2000), and substantially improves and simplifies a result previously published by the authors (2002). Our bound has numerous algorithmic and combinatorial applications, some of which are presented in this paper. Our result is obtained by introducing a new approach to the analysis of combinatorial structures arising in geometric arrangements of surfaces. This approach, which we call the 'partition technique', is based on k-fold divide and conquer, in which a given collection /spl Fscr/ of n surfaces is partitioned into k subcollections /spl Fscr//sub i/ of n/k surfaces each, and the complexity of the relevant combinatorial structure in /spl Fscr/ is recursively related to the complexities of the corresponding structures in each of the /spl Fscr//sub i/'s. We introduce this approach by applying it first to obtain a new simple proof for the known near-quadratic bound on the complexity of an overlay of two minimization diagrams of collections of surfaces in /spl Ropf//sup 3/, thereby simplifying the previously available proof (1996).

We derive improved bounds on the number of k-dimensional simplices spa nned by a set of n points in $\reals^d$ that are congruent to a given $k$-simplex, for $k\le d-1$. Let $f_k^{(d)} (n)$ be the maximum number of $k$-simplices spanned by a set of $n$ points in $\reals^d$ that are congruent to a given $k$-simplex. We prove that $f_2^{(3)}(n) = O(n^{5/3}\cdot 2^{O(\alpha^2(n))})$, $f_2^{(4)} (n) = O(n^{2+\eps})$, $f_2^{(5)} (n) = \Theta(n^{7/3})$, and $f_3^{(4)} (n) = O(n^{9/4+\eps})$. We also derive a recurrence to bound $f_k^{(d)} (n)$ for arbitrary values of $k$ and $d$, and use it to derive the bound $f_k^{(d)} (n) = O(n^{d/2})$ for $d \le 7$ and $k \le d-2$. Following Erd{\H o}s and Purdy, we conjecture that this bound holds for larger values of $d$ as well, and for $k\le d-2$.

We provide a variety of new results, including upper and lower bounds, as well as simpler proof techniques for the efficient construction of binary space partitions (BSP's) of axis-parallel segments, rectangles, and hyperrectangles. (a) A consequence of the analysis in \cite{dAF} is that any set of $n$ axis-parallel and pairwise-disjoint line segments in the plane admits a binary space partition of size at most $2n-1$. We establish a worst-case lower bound of $2n-o(n)$ for the size of such a BSP, thus showing that this bound is almost tight in the worst case. (b) We give an improved worst-case lower bound of $\frac{9}{4}n-o(n)$ on the size of a BSP for isothetic pairwise disjoint rectangles. (c) We present simple methods, with equally simple analysis, for constructing BSP's for axis-parallel segments in higher dimensions, simplifying the technique of \cite{PY2} and improving the constants. (d) We obtain an alternative construction (to that in \cite{PY2}) of BSP's for collections of axis-parallel rectangles in 3-space. (e) We present a construction of BSP's of size $O(n^{5/3})$ for $n$ axis-parallel pairwise disjoint 2-rectangles in $\reals^4$, and give a matching worst-case lower bound of $\Omega(n^{5/3})$ for the size of such a BSP. (f) We extend the results of \cite{PY2} to axis-parallel $k$-dimensional rectangles in $\reals^d$, for $k

A {\em dihedral (trihedral) wedge} is the intersection of two (resp. t hree) half-spaces in $\reals^3$. It is called {\em $\alpha$-fat} if the angle (resp., solid angle) determined by these half-spaces is at least $\alpha>0$. If, in addition, the sum of the three face angles of a trihedral wedge is at least $\gamma >4\pi/3$, then it is called {\em $(\gamma,\alpha)$-substantially fat}. We prove that, for any fixed $\gamma>4\pi/3, \alpha>0$, the combinatorial complexity of the union of $n$ (a) $\alpha$-fat dihedral wedges, (b) $(\gamma,\alpha)$-substantially fat trihedral wedges is at most $O(n^{2+\eps})$, for any $\eps>0$, where the constants of proportionality depend on $\eps$, $\alpha$ (and $\gamma$).

We provide an alternative simpler and more general deriva- tion of the Clarkson-Shor probabilistic technique [4] and use it to obtain in addition several extensions and new combi- natorial bounds.

A recent result by Pach and Pinchasi on so-called balanced lines of a finite two-colored point set in the plane is related to other facts on halving triangles in 3-space and to a special case of the Generalized Lower Bound Theorem for convex polytopes.

We obtain improved bounds on the complexity of m distinct faces in an arrangement of n circles and in an arrangement of n unit circles. The bounds are worst-case tight for unit circles, and, for general circles, they nearly coincide with the best known bounds for the number of incidences between m points and n circles.

Article The 2-center problem with obstacles Share on Authors: Dan Halperin Department of Computer Science, Tel Aviv University, Tel-Aviv, 69978, Israel Department of Computer Science, Tel Aviv University, Tel-Aviv, 69978, IsraelView Profile , Micha Sharir School of Mathematical Sciences, Tel Aviv University, Tel-Aviv, 69978, Israel, and Courant Institute of Mathematical Sciences, New York, University, New York, NY School of Mathematical Sciences, Tel Aviv University, Tel-Aviv, 69978, Israel, and Courant Institute of Mathematical Sciences, New York, University, New York, NYView Profile , Ken Goldberg Department of Industrial Engineering and Operations Research, University of California, Berkeley, CA Department of Industrial Engineering and Operations Research, University of California, Berkeley, CAView Profile Authors Info & Claims SCG '00: Proceedings of the sixteenth annual symposium on Computational geometryMay 2000 Pages 80–90https://doi.org/10.1145/336154.336184Online:01 May 2000Publication History 3citation299DownloadsMetricsTotal Citations3Total Downloads299Last 12 Months2Last 6 weeks0 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

We prove that the maximum number of k-sets in a set S of n points in IR 3 is O(nk3/2).This improves substantially the previous best known upper bound of O(nk 5/3) (see [7] and [1]). IntroductionLet S be a set of n points in ]R d, A k-set of S is a subset S' c S such that S' = S N H for some halfspace H and IS'] --k.The problem of determining tight asymptotic bounds on the maximum number of k-sets is one of the most intriguing open problems in combinatorial geometry.Due to its importance in analyzing geometric algorithms [5,9], the problem has caught the attention of computational geometers as well [3,7,8,14,16].A close to optimal solution for the problem remains elusive even in the plane.The best asymptotic upper and lower bounds in the plane are O(nkU3) (see [6]) and n. 2 n(v/iS--~) (see [15]), respectively.In this

Let S be a set of n points in R d . The "roundness" of S can be measured by computing the width ! = ! (S) of the thinnest spherical shell (or annulus in R 2 ) that contains S. This paper contains three main results related to computing ! : (i) For d = 2, we can compute in O(n log n) time an annulus containing S whose width is at most 2! (S). We extend this algorithm, so that for any given parameter " ? 0, an annulus containing S whose width is at most (1 + ")! , is computed in time O(n log n + n=" 2 ). (ii) For d 3, given a parameter " ? 0, we can compute a shell containing S of width at most (1+ ")! either in time O \\Gamma n " d log( \\Delta ! " ) \\Delta or in time O \\Gamma n " d\\Gamma2 \\Gamma log n + 1 " \\Delta log \\Gamma \\Delta ! " \\Delta\\Delta . Work by P.A. was supported by Army Research Office MURI grant DAAH04-96-1-0013, by a Sloan fellowship, by NSF grants EIA--9870724, and CCR--9732787, by an NYI award, and by a grant from ...

Article Free Access Share on Pipes, cigars, and kreplach: the union of Minkowski sums in three dimensions Authors: Pankaj K. Agarwal Center for Geometric Computing, Department of Computer Science, Box 90129, Duke University, Durham, NC Center for Geometric Computing, Department of Computer Science, Box 90129, Duke University, Durham, NCView Profile , Micha Sharir School of Mathematical Sciences, Tel-Aviv University, Tel-Aviv 69978, Israel and Courant Institute of Mathematical Sciences, New York University, New York, NY School of Mathematical Sciences, Tel-Aviv University, Tel-Aviv 69978, Israel and Courant Institute of Mathematical Sciences, New York University, New York, NYView Profile Authors Info & Claims SCG '99: Proceedings of the fifteenth annual symposium on Computational geometryJune 1999 Pages 143–153https://doi.org/10.1145/304893.304960Published:13 June 1999Publication History 5citation287DownloadsMetricsTotal Citations5Total Downloads287Last 12 Months8Last 6 weeks2 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 SiteeReaderPDF

We investigate algorithmic questions that arise in the statistical problem of computing lines or hyperplanes of maximum regression depth among a set of n points.We work primarily with a dual representation and find points of maximum undirected depth in an arrangement of lines or hyperplanes.An O(nd) time and space algorithm computes directed depth of all points in d dimensions.Properties of undirected depth lead to an O(n log2 n) time and O(n) space algorithm for computing a point of maximum depth in two dimensions.We also give approximation algorithms for hyperplane arrangements and degenerate line arrangements.

We prove that the maximum number of geometric permutations, induced by line transversals to a collection of n pairwise disjoint balls in IRd, is O(nd-l).This improves substantially the upper bound of O(n2d-2) known for general convex sets [9].We show that the maximum number of geometric permutations of a sufficiently large collection of pairwise disjoint unit discs in the plane is 2, improving the previous upper bound of 3 given in [5].

In this paper we present a new technique for partial surface and volume matching of images in three dimensions. In this problem, we are given two objects in 3-space, each represented as a set of points, scattered uniformly along its boundary or inside its volume. The goal is to find a rigid motion of one object which makes a sufficiently large portion of its boundary lying sufficiently close to a corresponding portion of the boundary of the second object. This is an important problem in pattern recognition and in computer vision, with many industrial, medical, and chemical applications. Our algorithm is based on assigning a directed footprint to every point of the two sets, and locating all the pairs of points (one of each set) whose undirected components of the footprints are sufficiently similar. The algorithm then computes for each such pair of points all the rigid transformations that map the first point to the second, while making the respective direction components of their footprints coincide. A voting scheme is employed for computing transformations which map significantly large number of points of the first set to points of the second set. Experimental results on various examples are presented and show the accurate and robust performance of our algorithm.

Let ${\cal F}$ be a collection of n bivariate algebraic functions of constant maximum degree. We show that the combinatorial complexity of the vertical decomposition of the $({\le}k)$-level of the arrangement $\A({\cal F})$ is $O(k^{3+\varepsilon}\psi({n/k}))$ for any $\varepsilon>0$, where $\psi (r)$ is the maximum complexity of the lower envelope of a subset of at most r functions of ${\cal F}$. This bound is nearly optimal in the worst case and implies the existence of shallow cuttings, in the sense of [J. Matousek, Comput. Geom., 2 (1992), pp. 169--186], of small size in arrangements of bivariate algebraic functions. We also present numerous applications of these results, including (i) data structures for several generalized 3-dimensional range-searching problems; (ii) dynamic data structures for planar nearest- and farthest-neighbor searching under various fairly general distance functions; (iii) an improved (near-quadratic) algorithm for minimum-weight bipartite Euclidean matching in the plane; and (iv) efficient algorithms for certain geometric optimization problems in static and dynamic settings.

We consider the problem of bounding the complexity of the k-th level in an arrangement of n curves or surfaces, a problem dual to, and extending, the well-known k-set problem.(a) We review sad simplifi some old proofs in new dwguise and give new proofs of the bound O(n~) for the complexity of the k-th level in an arrangement of n lines.(b) We derive an improved version of Lcn%az Lemma in any dimension, and use it to prove a new bound, 0(n2k2/3), on the complexity of the k-th level in an mangement of n planes in lR3, or on the number of k-sets in a set of n points in three dimensions.(c) We show that the complexity of any single level in an arrangement of n line segments in the plane is O(n312 ), and that the complexity of any single level in an arrangement of n triangles in 3-space is O(n17'6 ).

Article Free Access Share on The discrete 2-center problem Authors: Pankaj K. Agarwal Center for Geometric Computing, Department of Computer Science, Box 90129, Duke University, Durham, NC Center for Geometric Computing, Department of Computer Science, Box 90129, Duke University, Durham, NCView Profile , Micha Sharir School of Mathematical Sciences, Tel Aviv University, Tel Aviv 69978, Israel and Courant Institute of Mathematical Sciences, New York University, New York, NY School of Mathematical Sciences, Tel Aviv University, Tel Aviv 69978, Israel and Courant Institute of Mathematical Sciences, New York University, New York, NYView Profile , Emo Welzl Institut für Theoretische Informatik, ETH Zürich, CH-8092, Zürich, Switzerland Institut für Theoretische Informatik, ETH Zürich, CH-8092, Zürich, SwitzerlandView Profile Authors Info & Claims SCG '97: Proceedings of the thirteenth annual symposium on Computational geometryAugust 1997 Pages 147–155https://doi.org/10.1145/262839.262921Published:01 August 1997Publication History 17citation328DownloadsMetricsTotal Citations17Total Downloads328Last 12 Months29Last 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 SiteeReaderPDF

We prove a near-linear bound on the combutorial complexity of the union of n fat convex objects in the plane, each pair of whose boundaries cross at most a constant number of times.

We establish several combinatorial bounds on the complexity (number of vertices and edges) of the complement of the union (also known as the common exterior) of k convex polygons in the plane, with a total of n edges. We show: (1) The maximum complexity of the entire common exterior is Θ(nα(k) + k2). 2 (2) The maximum complexity of a single cell of the common exterior is Θ(nα(k)). (3) The complexity of m distinct cells in the common exterior is O(m23k23log13(k2m) + nlogk) and can be Ω(m23k23 + nα(k)) in the worst case.

Given a convex polytope P with n faces in ℝ 3 , points ∈ ∂P, and a parameter 0 < ϵ ≤ 1, we present an algorithm that constructs a path on ∂P from s to t whose length is at most (1 + ϵ) d p (s, t) , where d p (s, t) is the length of the shortest path between s and t on ∂P. The algorithm runs in O(n log 1/ϵ + 1/ϵ 3 ) time, and is relatively simple. The running time is O(n + 1/ϵ 3 ) if we only want the approximate shortest path distance and not the path itself. We also present an extension of the algorithm that computes approximate shortest path distances from a given source point on ∂P to all vertices of P .

Let ${\cal F}$ be a collection of nd-variate, possibly partially defined, functions, all algebraic of some constant maximum degree. We present a randomized algorithm that computes the vertices, edges, and 2-faces of the lower envelope (i.e., pointwise minimum) of ${\cal F}$ in expected time $O(n^{d+\epsilon})$ for any $\epsilon > 0$. For d = 3, by combining this algorithm with the point-location technique of Preparata and Tamassia, we can compute, in randomized expected time $O(n^{3+\epsilon})$, for any $\epsilon > 0$, a data structure of size $O(n^{3+\epsilon})$ that, for any query point q, can determine in O(log2n) time the function(s) of ${\cal F}$ that attain the lower envelope at q. As a consequence, we obtain improved algorithmic solutions to several problems in computational geometry, including (a) computing the width of a point set in 3-space, (b) computing the "biggest stick" in a simple polygon in the plane, and (c) computing the smallest-width annulus covering a planar point set. The solutions to these problems run in randomized expected time $O(n^{17/11+\epsilon})$, for any $\epsilon > 0$, improving previous solutions that run in time $O(n^{8/5+\epsilon})$. We also present data structures for (i) performing nearest-neighbor and related queries for fairly general collections of objects in 3-space and for collections of moving objects in the plane and (ii) performing ray-shooting and related queries among n spheres or more general objects in 3-space. Both of these data structures require $O(n^{3+\epsilon})$ storage and preprocessing time, for any $\epsilon > 0$, and support polylogarithmic-time queries. These structures improve previous solutions to these problems.

Let B be a convex polyhedron translating in 3-space amidst k convex polyhedral obstacles A1,...,Ak with pairwise disjoint interiors. The free configuration space (space of all collision-free placements) of B can be represented as the complement of the union of the Minkowski sums $P_i=A_i\oplus (-B)$, for i= 1,...,k. We show that the combinatorial complexity of the free configuration space of B is O(nk log k), and that it can be $\Omega(nk\alpha(k))$ in the worst case, where n is the total complexity of the individual Minkowski sums P1,...,Pk. We also derive an efficient randomized algorithm that constructs this configuration space in expected time O(nk log k log n).

We show that the number of vertices, edges, and faces of the union of k convex polyhedra in 3-space, having a total of n faces, is O(k3 + kn log k). This bound is almost tight in the worst case, as there exist collections of polyhedra with $\Omega(k^3+kn\alpha(k))$ union complexity. We also describe a rather simple randomized incremental algorithm for computing the boundary of the union in O(k3 + kn log k log n) expected time.

We present a new approach to problems in geometric optimization that are traditionally solved using the parametric-searching technique of Megiddo [J. ACM, 30 (1983), pp. 852--865]. Our new approach is based on expander graphs and range-searching techniques. It is conceptually simpler, has more explicit geometric flavor, and does not require parallelization or randomization. In certain cases, our approach yields algorithms that are asymptotically faster than those currently known (e.g., the second and third problems below) by incorporating into our (basic) technique a subtechnique that is equivalent to (though much more flexible than) Cole's technique for speeding up parametric searching [J. ACM, 34 (1987), pp. 200--208]. We exemplify the technique on three main problems---the slope selection problem, the planar distance selection problem, and the planar {\em two-line center} problem. For the first problem we develop an $O(n\log^3 n)$ solution, which, although suboptimal, is very simple. The other two problems are more typical examples of our approach. Our solutions have running time $O(n^{4/3}\log^2n)$ and $O(n^2 \log^4 n)$, respectively, slightly better than the previous respective solutions of [Agarwal et al., Algorithmica, 9 (1993), pp. 495--514], [Agarwal and Sharir, Algorithmica, 11 (1994), pp. 185--195]. We also briefly mention two other problems that can be solved efficiently by our technique. In solving these problems, we also obtain some auxiliary results concerning batched range searching, where the ranges are congruent discs or annuli. For example, we show that it is possible to compute deterministically a compact representation of the set of all point-disc incidences among a set of n congruent discs and a set of m points in the plane in time $O((m^{2/3} n^{2/3}+m+n)\log n)$, again slightly better than what was previously known.

We consider the problem of ray shooting amidst spheres in 3-space: given n arbitrary (possibly intersecting) spheres in 3-space and any $\epsilon$ > 0, we show how to preprocess the spheres in time $O(n^{3+\epsilon})$ into a data structure of size $O(n^{3+\epsilon})$ so that any ray-shooting query can be answered in time $O(n^\epsilon)$. Our result improves previous techniques (see [P. K. Aggarwal, L. Guibas, M. Pellegrini, and M. Sharir, "Ray shooting amidst spheres," unpublished note] and [P. K. Aggarwal and J. Matousek, Discrete Comput. Geom., 11 (1994), pp. 393-418]), where roughly $O(n^4)$ storage was required to support fast queries. Our result shows that ray shooting amidst spheres has complexity comparable with that of ray shooting amidst planes in 3-space. Our technique applies to more general (convex) objects in 3-space, and we also discuss those extensions.

No abstract available.

We present an approximation algorithm that, given a convex polytope P with n faces in lR3, points s, t c 8P, and a parameter O < & <1, constructs a path on t3P from s to t whose length is at most (1 +E)dP(S, t), where dp (s, t) is the length of the shortest path between s and t on 8P.The algorithm runs intime. and is relatively simple to implement.We also present an extension of the algorithm that computes approximate shortest paths from a given source point on 8P to all vertices of P.

Let X be a collection of n algebraic surface patches of constant maximum degree in IR3.We show that the combinatorial complexity of the vertical decomposition of a single cell in the arrangement A(Z) is 0(n2+E ), for my E > CI, where the constant of proportionality de pends on E and on the maximum degree of the surfaces and of their boundaries.As an application, we obt~"n a near-quadratic motion planning algorithm for general systems with three degrees of freedom.

We present an \(O(n\log^{9}n)\) -time algorithm for computing the 2-center of a set S of n points in the plane (that is, a pair of congruent disks of smallest radius whose union covers S), improving the previous \(O(n^2\log n)\) -time algorithm of [10].

Weconsiderthep-piercingproblem,inwhichwearegiven acollectionofregions,andwishtodeterminewhetherthere existsasetofppointsthatintersectseachofthegivenregions.Wegivelinearornear-linearalgorithmsforsmall valuesofpincaseswherethegivenregionsareeitheraxisparallelrectanglesorconvexc-orientedpolygonsintheplane (i.e.,convexpolygonswithsidesfromaxednitesetofdirections). Wealsoinvestigatetheplanarrectilinear(andpolygonal) p-centerproblem,inwhichwearegivenasetSofnpointsin theplane,andwishtondpaxis-parallelcongruentsquares (isotheticcopiesofsomegivenconvexpolygon,respectively) ofsmallestpossiblesizewhoseunioncoversS.Wealsostudy severalgeneralizationsoftheseproblems. Newresultsarealinear-timesolutionfortherectilinear3-centerproblem(byshowingthatthisproblemcan beformulatedasanLP-typeproblemandbyexhibitinga relationtoHellynumbers).WegiveO(nlogn)-timesolutionsfor4-piercingoftranslatesofasquare,aswellasfor therectilinear4-centerproblem;thisisworst-caseoptimal. WegiveO(npolylogn)-timesolutionsfor4-and5-piercing ofaxis-parallelrectangles,formoregeneralrectilinear4centerproblems,andforrectilinear5-centerproblems.2pierceabilityofasetofnconvexc-orientedpolygonscanbe decidedintimeO(c2nlogn),andthe2-centerproblemfor aconvexc-goncanbesolvedinO(c5nlogn)time.Therst solutionisworst-caseoptimalwhencisxed. BothauthorsacknowledgesupportbyG.I.F.|theGerman IsraeliFoundationforScienticResearchandDevelopment,and byaMaxPlanckResearchAward.WorkbyMichaSharirhasalso beensupportedbyNationalScienceFoundationGrantsCCR-94-

In this paper we present a new technique for piecewise-linear surface reconstruction from a series of parallel polygonal cross sections. This is an important problem in medical imaging, surface reconstruction from topographic data, and other applications. We reduce the problem, as in most previous works, to a series of problems of piecewise-linear interpolation between each pair of successive slices. Our algorithm uses a partial curve matching technique for matching parts of the contours, an optimal triangulation of 3-D polygons for resolving the unmatched parts, and a minimum spanning tree heuristic for interpolating between nonsimply connected regions. Unlike previous attempts at solving this problem, our algorithm seems to handle successfully in practice any kind of data. It allows multiple contours in each slice, with any hierarchy of contour nesting, and avoids the introduction of counterintuitive bridges between contours, proposed in some earlier papers to handle interpolation between multiply connected regions. Experimental results on various complex examples, involving actual medical imaging data, are presented and show the good and robust performance of our algorithm.

We consider the problem of ray shooting in a three-dimensional scene consisting of m (possibly intersecting) convex polyhedra or polyhedral terrains with a total of n faces, i.e., we want to preprocess them into a data structure, so that the first intersection point of a query ray and the given polyhedra can be determined quickly. We present a technique that requires $O((mn)^{2 + \varepsilon } )$ preprocessing time and storage, and can answer ray-shooting queries in $O(\log ^2 n)$ time. This is a significant improvement over previously known techniques (which require $O(n^{4 + \varepsilon }) $ space and preprocessing) if m is much smaller than n, which is often the case in practice. Next, we present a variant of the technique that requires $O(n^{1 + \varepsilon }) $ space and preprocessing, and answers queries in time $O(m^{{1 / 4}} n^{{1 / 2} + \varepsilon } )$, again a significant improvement over previous techniques when $m \ll n$.

Let 3 be a collection of n bivariate algebraic functions of constant maximum degree.We show that the combinatorial complexity of the vertical decomposition of the 0, where @(~) is the maximum complexity of the lower envelope of a subset of at most ~functions of 7.This result implies the existence of shallow cuttings, in the sense of [3, 31], of small size in arrangements of bivariate algebraic functions.We also present numerous applications of these results, including: (i) data structures for several generalized threedimensional range searching problems; (ii) dynamic data structures for planar nearest and farthest neighbor searching under various fairly general distance functions; (iii) an improved (near-quadratic) algorithm for minimum-weight bipartite Euclidean matching in the plane; and (iv) efficient algorithms for certain geometric optimization problems in static and dynamic settings.

. In this paper we first prove the following combinatorial bound, concerning the complexity of the vertical decomposition of the minimization diagram of trivariate functions: Let F be a collection of n totally or partially defined algebraic trivariate functions of constant maximum degree, with the additional property that, for a given pair of functions f, f # # F , the surface f (x, y, z) = f # (x, y, z) is xy-monotone (actually, we need a somewhat weaker property). We show that the vertical decomposition of the minimization diagram of F consists of O(n 3+# ) cells (each of constant description complexity), for any #>0. In the second part of the paper, we present a general technique that yields faster randomized algorithms for solving a number of geometric optimization problems, including (i) computing the width of a point set in 3-space, (ii) computing the minimum-width annulus enclosing a set of n points in the plane, and (iii) computing the "biggest stick" inside a simpl...

The paper bounds the combinatorial complexity of the Voronoi diagram of a set of points under certain polyhedral distance functions.Specifically, if S is a set of n points in general position in Jf?-d, the complexity of its Voronoi diagram under the Lm metric, and also under a simplicial distance function, are both shown to be qn[dlzl ).The upper bound for the case of the Lm metric folIows from a new upper bound, also proved in this paper, on the complexity of the union of n axis-parallel hypercubes in Eld.This complexity is @(n ~d/21 ), for d > 1, and it improves to @(nld/2J ), for d ~2, if all the hypercubes have the same size.Under the L1 metric, the complexity of the Voronoi diagram of a set of n points in general position in IR3 is shown to be @(n2 ).We also show that the general position assumption is essential, and give examples where the complexity of the diagram increases significantly when the points are in degenerate configurations.

In this paper we present an algorithm for detecting and repairing defects in the boundary of a polyhedron. These defects, usually caused by problems in CAD software, consist of small gaps bounded by edges that are incident to only one polyhedron face. The algorithm uses a partial curve matching technique for matching parts of the defects, and an optimal triangulation of 3-D polygons for resolving the unmatched parts. It is also shown that finding a consistent set of partial curve matches with maximum score, a subproblem which is related to our repairing process, is NP-hard. Experimental results on several polyhedra are presented.

Let K be a set of n non-intersecting objects in 3-space. A depth order of K, if it exists, is a linear order < of the objects in K such that if K, L ϵ K and K lies vertically below L then K < L. We present a new technique for computing depth orders, and apply it to several special classes of objects. Our results include: (i) If K is a set of n triangles whose xy-projections are all ‘fat’, then a depth order for K can be computed in time O(n log5n). (ii) If K is a set of n convex and simply-shaped objects whose xy-projections are all ‘fat’ and their sizes are within a constant ratio from one another, then a depth order for K can be computed in time O(nλs12(n) log4n), where s is the maximum number of intersections between the boundaries of the xy-projections of any pair of objects in K, and λs(n) is the maximum length of (n,s) Davenport-Schinzel sequences.

We study two problems related to planar motion planning for robots with imperfect control, where, if the robot starts a linear movement in a certain commanded direction, we only know that its actual movement will be confined in a cone of angle α centered around the specified direction. First, we consider a single goal region, namely the “region at infinity”, and a set of polygonal obstacles, modeled as a set S of n line segments. We are interested in the region Rα(S) from where we can reach infinity with a directional uncertainty of α. We prove that the maximum complexity of Rα(S) is O(nα5). Second, we consider a collection of k polygonal goal regions of total complexity m, but without any obstacles. Here we prove an O(k3m) bound on the complexity of the region from where we can reach a goal region with a directional uncertainty of α. For both situations we also prove lower bounds on the maximum complexity, and we give efficient algorithms for computing the regions.

Let F be a collection of n d-variate, possibly partially defined, functions, all algebraic of some constant maximum degree. We present a randomized algorithm that computes the vertices, edges, and 2-faces of the lower envelope (i.e., pointwise minimum) of F in expected time O(nd+ϵ), for any ϵ>0. For d=3, by combining this algorithm with the point location technique of Preparata and Tamassia, we can compute, in randomized expected time O(n3+ϵ) for any ϵ>0, a data structure of size O(n3+ϵ) that, given any query point q, can determine in O(log2n) time whether q lies above, below or on the envelope. As a consequence, we obtain improved algorithmic solutions to many problems in computational geometry, including (a) computing the width of a point set in 3-space, (b) computing the biggest stick in a simple polygon in the plane, and (c) computing the smallest-width annulus covering a planar point set. The solutions to these problems run in time O(n17/11+ϵ), for any ϵ>0 improving previous solutions that run in time O(n8/5+ϵ). We also present data structures for (i) performing nearest-neighbor and related queries for fairly general collections of objects in 3-space and for collections of moving objects in the plane, and (ii) performing ray-shooting and related queries among n spheres or more general objects in 3-space. Both of these data structures require O(n3+ϵ) storage and preprocessing time, for any ϵ>0, and support polylogarithmic-time queries. These structures improve previous solutions to these problems.

Let B be a convex polyhedron translating in 3-space amidst k convex polyhedral obstacles A1,…,Ak with pairwise disjoint interiors. The free configuration space (space of all collision-free placements) of B can be represented as the complement of the union of the Minkowski sums Pi=Ai⊕(-B), for i=1,…,k. We show that the combinatorial complexity of the free configuration space of B is O(nklog2k), where n is the total complexity of the individual Minkowski sums P1,…,Pk. The bound is almost tight in the worst case. We also derive an efficient randomized algorithm that constructs this configuration space in expected time O(nklog3k).

In this paper we present a new technique for piecewise-linear surface reconstruction from a series of parallel polygonal cross-sections. This is an important problem in medical imaging, surface reconstruction from topographic data, and other applications. We reduce the problem, as in most previous works, to a series of problems of piecewise-linear interpolation between each pair of successive slices. Our algorithm uses a partial curve matching technique for matching parts of the contours, an optimal triangulation of 3-D polygons for resolving the unmatched parts, and a minimum spanning tree heuristic for interpolating between non simply connected regions. Unlike previous attempts at solving this problem, our algorithm seems to handle successfully any kind of data. It allows multiple contours in each slice, with any hierarchy of contour nesting, and avoids the introduction of counter-intuitive bridges between contours, proposed in some earlier papers to handle interpolation between multiply connected regions. Experimental results on various complex examples, involving actual medical imaging data, are presented, and show the good and robust performance of our algorithm.

We consider the problem of bounding the combinatorial complexity of a single cell in an arrangement of n low-degree algebraic surface patches in 3-space. We show that this complexity is O(n2+ε), for any ε>0, where the constant of proportionality depends on ε and on the maximum degree of the given surfaces and of their boundaries. This extends several previous results, almost settles a 7-year-old open problem, and has applications to motion planning of general robot systems with three degrees of freedom. As a corollary of the above result, we show that the overall complexity of all the three-dimensional cells of an arrangement of n low-degree algebraic surface patches, intersected by an additional low-degree algebraic surface patch σ (the so-called zone of σ in the arrangement) is O(n2+ε), for any ε>0, where the constant of proportionality depends on ε and on the maximum degree of the given surfaces and of their boundaries.

In this paper we present a new technique for partial surface and volume matching of images in three dimensions. In this problem, we are given two objects in 3-space, each represented as a set of points, scattered uniformly along its boundary or inside its volume. The goal is to find a rigid motion of one object which makes a sufficiently large portion of its boundary lying sufficiently close to a corresponding portion of the boundary of the second object. Our method treats separately the rotation and the translation components of the Euclidean motion that we seek, and compares favorably with previous techniques. Experimental results on various examples, involving data from industrial applications and from molecular biology, are presented and show the accurate performance of our algorithm.

This paper investigates the computational complexity of planning the motion of a body B in 2-D or 3-D space, so as to avoid collision with moving obstacles of known, easily computed, trajectories. Dynamic movement problems are of fundamental importance to robotics, but their computational complexity has not previously been investigated. We provide evidence that the 3-D dynamic movement problem is intractable even if B has only a constant number of degrees of freedom of movement. In particular, we prove the problem is PSPACE-hard if B is given a velocity modulus bound on its movements and is NP-hard even if B has no velocity modulus bound, where, in both cases, B has 6 degrees of freedom. To prove these results, we use a unique method of simulation of a Turing machine that uses time to encode configurations (whereas previous lower bound proofs in robotic motion planning used the system position to encode configurations and so required unbounded number of degrees of freedom). We also investigate a natural class of dynamic problems that we call asteroid avoidance problems : B, the object we wish to move, is a convex polyhedron that is free to move by translation with bounded velocity modulus, and the polyhedral obstacles have known translational trajectories but cannot rotate. This problem has many applications to robot, automobile, and aircraft collision avoidance. Our main positive results are polynomial time algorithms for the 2-D asteroid avoidance problem, where B is a moving polygon and we assume a constant number of obstacles, as well as single exponential time or polynomial space algorithms for the 3-D asteroid avoidance problem, where B is a convex polyhedron and there are arbitrarily many obstacles. Our techniques for solving these asteroid avoidance problems use “normal path” arguments, which are an intereting generalization of techniques previously used to solve static shortest path problems. We also give some additional positive results for various other dynamic movers problems, and in particular give polynomial time algorithms for the case in which B has no velocity bounds and the movements of obstacles are algebraic in space-time.

A collection of geometric selection lemmas is proved, such as the following: For any set P of n points in three-dimensional space and any set S of m spheres, where each sphere passes through a distinct point pair in P, there exists a point x, not necessarily in P, that is enclosed by $\Omega ({{m^2 } / {(n^2 \log ^6 \tfrac{{n^2 }}{m})}})$ of the spheres in S. Similar results apply in arbitrary fixed dimensions, and for geometric bodies other than spheres. The results have applications in reducing the size of geometric structures, such as three-dimensional Delaunay triangulations and Gabriel graphs, by adding extra points to their defining sets.

The authors show that for every fixed $\delta > 0$ the following holds: If F is a union of n triangles, all of whose angles are at least $\delta $, then the complement of F has $O(n)$ connected components and the boundary of F consists of $O(n\log \log n)$ straight segments (where the constants of proportionality depend on $\delta $). This latter complexity becomes linear if all triangles are of roughly the same size or if they are all infinite wedges.

We consider the problem of bounding the complexity of the lower envelope of n surface patches in 3-space, all algebraic of constant maximum degree, and bounded by algebraic arcs of constant maximum degree, with the additional property that the interiors of any triple of these surfaces intersect in at most two points. We show that the number of vertices on the lower envelope of n such surface patches is O(n2˙2c√log n), for some constant c depending on the shape and degree of the surface patches. We apply this result to obtain an upper bound on the combinatorial complexity of the “lower envelope” of the space of all rays in 3-space that lie above a given polyhedral terrain K with n edges. This envelope consists of all rays that touch the terrain (but otherwise lie above it). We show that the combinatorial complexity of this ray-envelope is O(n2˙2c√log n) for some constant c; in particular, there are at most that many rays that pass above the terrain and touch it in 4 edges. This bound, combined with the analysis of de Berg et al. [2], gives an upper bound (which is almost tight in the worst case) on the number of topologically-different orthographic views of such a terrain.

Continuing our earlier study [12], we present optical algorithms for solving a variety of basic problems in computational geometry, each requiring only a constant number of basic optical operations. The main tools that we use are based on optical computational tricks that involve geometric duality and Minkowski sums of geometric figures.

We present a new approach to problems in geometric optimization that are traditionally solved using the parametric searching technique of Megiddo. Our new approach is based on expander graphs and is conceptually much simpler and has more explicit geometric flavor. It does not require parallelization or randomization, and it exploits recent range-searching techniques of Matousˇek and others. We exemplify the technique on three problems, the slope selection problem, the planar distance selection problem, and the planar two-center problem. For the first problem we develop an O(n log3n)) solution, which, although suboptimal, is very simple. The second and third problems are more typical examples of our approach. Our solutions have, respectively, running time O(n4/3 log3+δ n), for any δ > 0, and O(n2 log3 n), comparable with the respective solutions of [2, 5].

No abstract available.

We show that the number of vertices, edges, and faces of the union of k convex polyhedra in 3-space, having a total of n faces, is O(k/sup 3/+knlog/sup 2/ k). This bound is almost tight in the worst case. We also describe a rather simple randomized incremental algorithm for computing the boundary of the union in O(k/sup 3/+knlog/sup 3/ k) expected time.>

We consider the problem of planning the motion of an arbitrary k-sided polygonal robot B, free to translate and rotate in a polygonal environment V bounded by n edges. We show that the combinatorial complexity of a single connected component of the free configuration space of B is k/sup 3/n/sup 2/2/sup O(log(2/3)/ n). This is a significant improvement of the naive bound O((kn)/sup 3/); when k is constant, which is often the case in practice, this yields a near-quadratic bound on the complexity of such a component, which almost settles (in this special case) a long-standing conjecture regarding the complexity of a single cell in a three-dimensional arrangement of surfaces. We also present an algorithm that constructs a single component of the free configuration space of B in time O(n/sup 2+/spl epsi//), for any /spl epsi/>0, assuming B has a constant number of sides. This algorithm, combined with some standard techniques in motion planning, yields a solution to the underlying motion planning problem, within the same asymptotic running time.>

We show that the combinatorial complexity of the lower envelope of n surfaces or surface patches in d-space (d/spl ges/3), all algebraic of constant maximum degree, and bounded by algebraic surfaces of constant maximum degree, is O(n/sup d-1+/spl epsi//), for any /spl epsi/>0; the constant of proportionality depends on /spl epsi/, d, and the shape and degree of the surface patches and of their boundaries. This is the first nontrivial general upper bound for this problem, and it almost establishes a long-standing conjecture that the complexity of the envelope is O(n/sup d-2//spl lambda//sub q/(n)) for some constant q depending on the shape and degree of the surfaces (where /spl lambda//sub q/(n) is the maximum length of (n,q) Davenport-Schinzel sequences). We also present a randomized algorithm for computing the envelope in three dimensions, with expected running time O(n/sup 2+/spl epsi//), and give several applications of the new bounds.>

Let S be a set of n points in IR d . A set W is a weak "-net for (convex ranges of) S if for any T ` S containing "n points, the convex hull of T intersects W . We show the existence of weak "-nets of size O i 1 " d log fi d 1 " j , where fi 2 = 0, fi 3 = 1, and fi d 0:149 \\Delta 2 d\\Gamma1 (d \\Gamma 1)!, improving a previous bound of Alon et al. We present a deterministic algorithm for computing such a net in time n(1=") O(1) . We also consider two special cases: when S is in convex position, we prove the existence of a net of size O( 1 " log 1:6 1 " ); for the case where S consists of the vertices of a regular polygon, we use an argument from hyperbolic geometry to exhibit an optimal net of size O(1=").

Given n points in the plane and an integer k, the slope selection problem is to find the pair of points whose connecting line has the kth smallest slope. (In dual setting, given n lines in the plane, we want to find the vertex of their arrangement with the kth smallest x-coordinate.) Cole et al. have given an O(n log n) solution (which is optimal), using the parametric searching technique of Megiddo. We obtain another optimal (deterministic) solution that does not depend on parametric searching and uses expander graphs instead. Our solution is somewhat simpler than that of [6] and has a more explicit geometric interpretation.

In this paper efficient algorithms for counting intersections in a collection of circles or circular arcs are presented. An algorithm for counting intersections in a collection of n circles is presented whose running time is $O(n^{{3 / {2 + \epsilon }}} )$, for any $\epsilon > 0$ is presented. Using this algorithm as a subroutine, it is shown that the intersections in a set of n circular arcs can also be counted in time $O(n^{{3 / {2 + \epsilon }}} )$. If all arcs have the same radius, the running time can be improved to $O(n^{{4 / {3 + \epsilon }}} )$, for any $\epsilon > 0$.

This paper presents a randomized incremental algorithm for computing a single face in an arrangement of n line segments in the plane that is fairly simple to implement. The expected running time of the algorithm is $O(n\alpha (n)\log n)$. The analysis of the algorithm uses a novel approach that generalizes and extends the Clarkson–Shor analysis technique [in Discrete Comput. Geom., 4 (1989), pp. 387–421]. A few extensions of the technique, obtaining efficient randomized incremental algorithms for constructing the entire arrangement of a collection of line segments and for computing a single face in an arrangement of Jordan arcs are also presented.

The zone theorem for an arrangement of n hyperplanes in d-dimensional real space says that the total number of faces bounding the cells intersected by another hyperplane is $O(n^{d - 1} )$. This result is the basis of a time-optimal incremental algorithm that constructs a hyperplane arrangement and has a host of other algorithmic and combinatorial applications. Unfortunately, the original proof of the zone theorem, for $d \geqslant 3$, turned out to contain a serious and irreparable error. This paper presents a new proof of the theorem. The proof is based on an inductive argument, which also applies in the case of pseudohyperplane arrangements. The fallacies of the old proof along with some ways of partially saving that approach are briefly discussed.

We show that the total number of faces bounding any single cell in an arrangement of n (d–1)-simplices in IRd is O(nd–1 log n), thus almost settling a conjecture of Pach and Sharir. We present several applications of this result, mainly to translational motion planning in polyhedral environments. We then extend our analysis technique to derive other results on complexity in simplex arrangements. For example, we show that the number of vertices in such an arrangement, which are incident to the same cell on more than one “side,” is O(nd-1 log n). We also show that the number of repetitons of a “k-flap,” formed by intersecting d–k simplices, along the boundary of the same cell, summed over all cells and all k-flaps, is O(nd-1 log n). We use this quantity, which we call the excess of the arrangement, to derive bounds on the complexity of m distinct cells of such an arrangement.

We apply Megiddo's parametric searching technique to several geometric optimization problems and derive significantly improve solutions for them. We obtain, for any fixed ε > 0, an O(n1+ε) algorithm for computing the diameter of a point set in 3-space, an O(n8/5+ε) algorithm for computing the closest pair in a set of n lines in space. All these algorithms are deterministic. We also look at the problem of computing the k-th smallest slope formed by the lines joining n points in the plane. In 1989 Cole, Salowe, Steiger, and Szemere´di gave an optimal but very complicated O(n log n) solution based on Megiddo's technique. We follow a different route and give a very simple O(n log2 n) solution which bypasses parametric searching altogether.

Article Optical computational geometry Share on Authors: Y. B. Karasik View Profile , M. Sharir View Profile Authors Info & Claims SCG '92: Proceedings of the eighth annual symposium on Computational geometryJuly 1992 Pages 232–241https://doi.org/10.1145/142675.142723Online:01 July 1992Publication History 2citation486DownloadsMetricsTotal Citations2Total Downloads486Last 12 Months9Last 6 weeks0 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

We present a simple randomized algorithm which solves linear programs with n constraints and d variables in expected O(nde(d ln(n+1))1/4) time in the unit cost model (where we count the number of arithmetic operations on the numbers in the input). The expectation is over the internal randomizations performed by the algorithm, and holds for any input. The algorithm is presented in an abstract framework, which facilitates its application to several other related problems. The algorithm has been presented in a previous work by the authors [ShW], but its analysis and the subexponential complexity bound are new.

An algorithm that solves the following motion-planning problem is presented. Given an L-shaped body L and a two-dimensional region with n point obstacles, decide whether there is a continuous motion connecting two given positions and orientations of L during which L avoids collision with the obstacles. The algorithm requires $O(n^2 \log ^2 n)$ time and $O(n^2 )$ storage. The algorithm is a variant of the cell-decomposition technique of the configuration space [D. Leven and M. Sharir, J. Algorithms, 8 (1987), pp. 192–215], [J. T. Schwartz and M. Sharir, Comm. Pure Appl. Math., 36 (1983), pp. 345–398], but it employs a new and efficient technique for obtaining a compact representation of the free space, which results in a saving of nearly an order of magnitude. The approach used in our algorithm is also applicable to motion planning of certain robotic arms whose spaces of free placements have a structure similar to that of the L-shaped body.

We derive a simple output-sensitive algorithm for hidden surface removal in a collection of n triangles in space for which a (partial) depth order is known. If k is the combinatorial complexity of the output visibility map , the method runs in time O(n √k log n). The method is extended to work for other classes of objects as well, sometimes with even improved time bounds. For example, we obtain an algorithm that performs hidden surface removal for n (nonintersecting) balls in time O(n 3/2 log n + k).

In this paper we present efficient algorithms for counting intersections in a collection of circles or circular arcs.YVe present a randomized algorithm to count intersections in a collection of n circles whose expected running time is 0(n3i2+C), for any c > 0. We also develop another randomized algorithm to count intersections in a set of n circular arcs whose expected running time is O(n513+C), for any ~> 0. If all arcs have the same radius, the (expected) running time can he improved to 0(n312+C), for any c > 0.

Article On the sum of squares of cell complexities in hyperplane arrangements Share on Authors: Boris Aronov Department of Computer Science, Polytechnic University, Brooklyn, NY Department of Computer Science, Polytechnic University, Brooklyn, NYView Profile , Jiří Matoušek Department of Applied Mathematics, Charles University, 118 00 Praha 1, Czechoslovakia Department of Applied Mathematics, Charles University, 118 00 Praha 1, CzechoslovakiaView Profile , Micha Sharir School of Mathematical Sciences, Tel Aviv University, Tel Aviv, Israel and Courant Institute of Mathematical Sciences, New York University, NY School of Mathematical Sciences, Tel Aviv University, Tel Aviv, Israel and Courant Institute of Mathematical Sciences, New York University, NYView Profile Authors Info & Claims SCG '91: Proceedings of the seventh annual symposium on Computational geometryJune 1991 Pages 307–313https://doi.org/10.1145/109648.109682Online:01 June 1991Publication History 12citation204DownloadsMetricsTotal Citations12Total Downloads204Last 12 Months3Last 6 weeks0 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 a set S of sources (points or segments), we consider the surface that is the graph of the functien d(z) = minPcS p(z, p), for some metric p.This surface is closely related to the Voronoi diagram, Vor(S), of S under the metric p.The upper envelope of a set of these Voronoi surfaces, each defined for a differ-

methods also apply to computing the vi;lbility map for a polyhedral terrain viewed from a fixed point, and yield O((rm(n) + k) log n) algorithms.

It is shown that for every fixed delta >0 the following holds: if F is a union of n triangles, all of whose angles are at least delta , then the complement of F has O(n) connected components, and the boundary of F consists of O(n log log n) segments. This latter complexity becomes linear if all triangles are of roughly the same size or if they are all infinite wedges. A randomized algorithm that computes F in expected time O(n2/sup alpha (n)/ log n) is given. Several applications of these results are presented.>