We show that the following algorithmic problem is decidable: given a 2-dimensional simplicial complex, can it be embedded (topologically, or equivalently, piecewise linearly) in R 3 ? By a known reduction, it suffices to decide the embeddability of a given triangulated 3-manifold X into the 3-sphere S 3 . The main step, which allows us to simplify X and recurse, is in proving that if X can be embedded in S 3 , then there is also an embedding in which X has a short meridian , that is, an essential curve in the boundary of X bounding a disk in S 3 \ X with length bounded by a computable function of the number of tetrahedra of X .

The gamma_2 norm of a real m by n matrix A is the minimum number t such that the column vectors of A are contained in a 0-centered ellipsoid E that in turn is contained in the hypercube [-t, t]^m. This classical quantity is polynomial-time computable and was proved by the second author and Talwar to approximate the hereditary discrepancy: it bounds the hereditary discrepancy from above and from below, up to logarithmic factors. Here we provided a simplified proof of the upper bound and show that both the upper and the lower bound are asymptotically tight in the worst case. We then demonstrate on several examples the power of the gamma_2 norm as a tool for proving lower and upper bounds in discrepancy theory. Most notably, we prove a new lower bound of log(n)^(d-1) (up to constant factors) for the d-dimensional Tusnady problem, asking for the combinatorial discrepancy of an n-point set in d-dimensional space with respect to axis-parallel boxes. For d>2, this improves the previous best lower bound, which was of order approximately log(n)^((d-1)/2), and it comes close to the best known upper bound of O(log(n)^(d+1/2)), for which we also obtain a new, very simple proof. Applications to lower bounds for dynamic range searching and lower bounds in differential privacy are given.

By a curve in Rd we mean a continuous map γ: I → Rd, where I ⊂ R is a closed interval. We call a curve γ in Rd (≤ k)-crossing if it intersects every hyperplane at most k times (counted with multiplicity). The (≤ d)-crossing curves in Rd are often called convex curves and they form an important class; a primary example is the moment curve {(t, t2, …, td): t ∈ [0, 1]}. They are also closely related to Chebyshev systems, which is a notion of considerable importance, e.g., in approximation theory. Our main result is that for every d there is M = M(d) such that every (≤ d + 1)-crossing curve in Rd can be subdivided into at most M(≤ d)-crossing curve segments. As a consequence, based on the work of Eliáš, Roldán, Safernová, and the second author, we obtain an essentially tight lower bound for a geometric Ramsey-type problem in Rd concerning order-type homogeneous sequences of points, investigated in several previous papers.

We continue a sequence of recent works studying Ramsey functions for semialgebraic predicates in Rd. A k-ary semialgebraic predicate Φ(x1, …, xk) on Rd is a Boolean combination of polynomial equations and inequalities in the kd coordinates of k points x1, …, xk ∈ Rd. A sequence P = (p1, …, pn) of points in Rd is called Φ-homogeneous if either Φ(pi1, …,pik) holds for all choices 1 ≤ i1 < … < ik ≤ n, or it holds for no such choice. The Ramsey function RΦ (n) is the smallest N such that every point sequence of length N contains a Φ-homogeneous subsequence of length n.

We show that the following algorithmic problem is decidable: given a 2-dimensional simplicial complex, can it be embedded (topologically, or equivalently, piecewise linearly) in R3? By a known reduction, it suffices to decide the embeddability of a given triangulated 3-manifold X into the 3-sphere S3. The main step, which allows us to simplify X and recurse, is in proving that if X can be embedded in S3, then there is also an embedding in which X has a short meridian, i.e., an essential curve in the boundary of X bounding a disk in S3 \ X with length bounded by a computable function of the number of tetrahedra of X.

Given topological spaces X , Y , a fundamental problem of algebraic topology is understanding the structure of all continuous maps X → Y . We consider a computational version, where X , Y are given as finite simplicial complexes, and the goal is to compute [ X , Y ], that is, all homotopy classes of such maps. We solve this problem in the stable range , where for some d ≥ 2, we have dim X ≤ 2 d −2 and Y is ( d -1)- connected ; in particular, Y can be the d -dimensional sphere S d . The algorithm combines classical tools and ideas from homotopy theory (obstruction theory, Postnikov systems, and simplicial sets) with algorithmic tools from effective algebraic topology (locally effective simplicial sets and objects with effective homology). In contrast, [ X , Y ] is known to be uncomputable for general X , Y , since for X = S 1 it includes a well known undecidable problem: testing triviality of the fundamental group of Y . In follow-up papers, the algorithm is shown to run in polynomial time for d fixed, and extended to other problems, such as the extension problem , where we are given a subspace A ⊂ X and a map A → Y and ask whether it extends to a map X → Y , or computing the ℤ 2 - index —everything in the stable range. Outside the stable range, the extension problem is undecidable.

For several computational problems in homotopy theory, we obtain algorithms with running time polynomial in the input size. In particular, for every fixed $k\ge 2$, there is a polynomial-time algorithm that, for a $1$-connected topological space $X$ given as a finite simplicial complex, or more generally, as a simplicial set with polynomial-time homology, computes the $k$th homotopy group $\pi_k(X)$, as well as the first $k$ stages of a Postnikov system of $X$. Combined with results of an earlier paper, this yields a polynomial-time computation of $[X,Y]$, i.e., all homotopy classes of continuous mappings $X\to Y$, under the assumption that $Y$ is $(k-1)$-connected and $\dim X\le 2k-2$. We also obtain a polynomial-time solution of the extension problem, where the input consists of finite simplicial complexes $X$, $Y$, where $Y$ is $(k-1)$-connected and $\dim X\le 2k-1$, plus a subspace $A\subseteq X$ and a (simplicial) map $f:A\to Y$, and the question is the extendability of $f$ to all of $X$. The algorithms are based on the notion of a simplicial set with polynomial-time homology, which is an enhancement of the notion of a simplicial set with effective homology developed earlier by Sergeraert and his coworkers. Our polynomial-time algorithms are obtained by showing that simplicial sets with polynomial-time homology are closed under various operations, most notably Cartesian products, twisted Cartesian products, and classifying space. One of the key components is also polynomial-time homology for the Eilenberg--MacLane space $K(\mathbb{Z},1)$, provided in another recent paper by Krčál, Matoušek, and Sergeraert. (A corrected file is attached.)

We continue a sequence of recent works studying Ramsey functions for semialgebraic predicates in $\mathbb{R}^d$. A $k$-ary semialgebraic predicate $\Phi(x_1,\ldots,x_k)$ on $\mathbb{R}^d$ is a Boolean combination of polynomial equations and inequalities in the $kd$ coordinates of $k$ points $x_1,\ldots,x_k\in\mathbb{R}^d$. A sequence $P=(p_1,\ldots,p_n)$ of points in $\mathbb{R}^d$ is called $\Phi$-homogeneous if either $\Phi(p_{i_1}, \ldots,p_{i_k})$ holds for all choices $1\le i_1<\cdots

We consider several basic problems of algebraic topology, with connections to combinatorial and geometric questions, from the point of view of computational complexity.

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=(p1,p2,...,pN) be a sequence of points in the plane, where pi=(xi,yi) and x1

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 present an algorithm for computing [X, Y], i.e., all homotopy classes of continuous maps X → Y, where X, Y are topological spaces given as finite simplicial complexes, Y is (d − 1)-connected for some d ≥ 2 (for example, Y can be the d-dimensional sphere Sd), and dim X ≤ 2d − 2. These conditions on X, Y guarantee that [X, Y] has a natural structure of a finitely generated Abelian group, and the algorithm finds generators and relations for it. We combine several tools and ideas from homotopy theory (such as Postnikov systems, simplicial sets, and obstruction theory) with algorithmic tools from effective algebraic topology (objects with effective homology). We hope that a further extension of the methods developed here will yield an algorithm for computing, in some cases of interest, the ℤ2-index, which is a quantity playing a prominent role in Borsuk–Ulam style applications of topology in combinatorics and geometry, e.g., in topological lower bounds for the chromatic number of a graph. In a certain range of dimensions, deciding the embeddability of a simplicial complex into ℝd also amounts to a ℤ2-index computation. This is the main motivation of our work. We believe that investigating the computational complexity of questions in homotopy theory and similar areas presents a fascinating research area, and we hope that our work may help bridge the cultural gap between algebraic topology and theoretical computer science.

The bisector of two nonempty sets P and Q in a metric space is the set of all points with equal distance to P and to Q. A distance k-sector of P and Q, where k ≥ 2 is an integer, is a (k-1)-tuple (C1, C2, ..., Ck-1) such that Ci is the bisector of Ci-1 and Ci+1 for every i= 1, 2, ..., k-1, where C0 = P and Ck = Q. This notion, for the case where P and Q are points in Euclidean plane, was introduced by Asano, Matousek, and Tokuyama, motivated by a question of Murata in VLSI design. They established the existence and uniqueness of the distance trisector in this special case. We prove the existence of a distance k-sector for all k and for every two disjoint, nonempty, closed sets P and Q in Euclidean spaces of any (finite) dimension, or more generally, in proper geodesic spaces (uniqueness remains open). The core of the proof is a new notion of k-gradation for P and Q, whose existence (even in an arbitrary metric space) is proved using the Knaster-Tarski fixed point theorem, by a method introduced by Reem and Reich for a slightly different purpose.

Zone diagram is a variation on the classical concept of a Voronoi diagram. Given n sites in a metric space that compete for territory, the zone diagram is an equilibrium state in the competition. Formally it is defined as a fixed point of a certain "dominance" map.

A set N ⊂ Rd is called a weak ε-net (with respect to convex sets) for a finite X ⊂ Rd if N intersects every convex set C with |X ∩ C|≥ε|X|. For every fixed d≥ 2 and every r≥ 1 we construct sets X⊂ Rd for which every weak 1/r-net has at least Ω(r logd-1 r) points; this is the first superlinear lower bound for weak ε-nets in a fixed dimension.

Let EMBEDk→d be the following algorithmic problem: Given a finite simplicial complex K of dimension at most k, does there exist a (piecewise linear) embedding of K into ℝd? Known results easily imply polynomiality of EMBEDk→2 (k = 1,2; the case k = 1, d = 2 is graph planarity) and of EMBEDk→2k for all k ≥ 3 (even if k is not considered fixed). We show that the celebrated result of Novikov on the algorithmic unsolvability of recognizing the 5-sphere implies that EMBEDd→d and EMBED(d−1)→d are undecidable for each d ≥ 5. Our main result is NP-hardness of EMBED2→4 and, more generally, of EMBEDk→d for all k, d with d ≥ 4 and d ≥ k ≥ (2d − 2)/3.

We consider the problem of computing the smallest possible distortion for embedding of a given n-point metric space into R.d, where d is fixed (and small). For d = 1, it was known that approximating the minimum distortion with a factor better than roughly n1/12is NP-hard. From this result we derive inapproximability with factor roughly n1/(22d-10)for every fixed d ges 2, by a conceptually very simple reduction. However, the proof of correctness involves a nontrivial result in geometric topology (whose current proof is based on ideas due to Jussi Vaisala). For d ges 3,we obtain a stronger inapproximability result by a different reduction: assuming PneNP, no polynomial- time algorithm can distinguish between spaces embeddable in R.d with constant distortion from spaces requiring distortion at least nc/d, for a constant c > 0. The exponent c/d has the correct order of magnitude, since every n-point metric space can be embedded in Rdwith distortion O(n2/dlog3/2n) and such an embedding can be constructed in polynomial time by random projection. For d = 2, we give an example of a metric space that requires a large distortion for embedding in R2, while all not too large subspaces of it embed almost isometrically.

Let $D^d_n$ denote the d-dimensional grid with diagonals, that is, the graph with vertex set $\{1,2,\ldots,n\}^d$ and with edges connecting every two vertices that differ by at most 1 in every coordinate. We prove that for an arbitrary coloring of the vertices of $D^d_n$ by two colors there exists a monochromatic connected subgraph with at least $n^{d-1}-d^2n^{d-2}$ vertices; and thus the “horizontal layer” coloring (by the parity of the first coordinate) is almost optimal. We also consider a d-dimensional triangulated grid; this is the graph (1-skeleton) of a triangulation of the solid cube $[1,n]^d$ that refines the subdivision of $[1,n]^d$ into the grid of unit cubes. Here every two-coloring has a monochromatic connected subgraph with $\Omega(n^{d-1}/\sqrt d)$ vertices. These results are proved by combining combinatorial and topological arguments with suitable isoperimetric inequalities, and they can be viewed as d-dimensional generalizations of the planar HEX lemma.

Let A be an n-point set in the plane. A discrete X-ray of A in direction u gives the number of points of A on each line parallel to u. We define $F(k)$ as the maximum number n such that there exist k directions $u_1,\dots,u_k$ such that every set of at most n points in the plane can be uniquely reconstructed from its discrete X-rays in these directions. A simple “cube” construction shows $F(k)\le2^{k-1}$. We establish the lower bound $F(k)\ge2^{\Omega(k/\log k)}$ by reducing the problem through linear algebra to a graph-theoretic question, for which we then obtain an almost tight bound. As a part of the proof we establish a result in extremal theory that allows one to conclude that, under certain conditions, a graph has only at most a logarithmic density, which may be of independent interest. We also improve the upper bound to $F(k)\le O(1.81712^k)$ (or $O(1.79964^k)$ if we allow A to be a multiset).

A zone diagram is a new variation of the classical notion of the Voronoi diagram. Given points (sites) ${\mathbf p}_1,\ldots,{\mathbf p}_n$ in the plane, each ${\mathbf p}_i$ is assigned a region $R_i$, but in contrast to the ordinary Voronoi diagrams, the union of the $R_i$ has a nonempty complement, the neutral zone. The defining property is that each $R_i$ consists of all ${\mathbf x}\in{\mathbb{R}}^2$ that lie closer (nonstrictly) to ${\mathbf p}_i$ than to the union of all the other $R_j$, $j\ne i$. Thus, the zone diagram is defined implicitly, by a “fixed-point property,” and neither its existence nor its uniqueness seem obvious. We establish existence using a general fixed-point result (a consequence of Schauder's theorem or Kakutani's theorem); this proof should generalize easily to related settings, say higher dimensions. Then we prove uniqueness of the zone diagram, as well as convergence of a natural iterative algorithm for computing it, by a geometric argument, which also relies on a result for the case of two sites in an earlier paper. Many challenging questions remain open.

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.

The colorful Carathéodory theorem asserts that if $X_1,X_2,\ldots,X_{d+1}$ are sets in ${\bf R}^d$, each containing the origin 0 in its convex hull, then there exists a set $S \subseteq X_1 \cup \cdots \cup X_{d+1}$ with $|S \cap X_i| = 1$ for all $i=1,2,\ldots,d+1$ and $0 \in conv(S)$ (we call $conv(S)$ a colorful covering simplex). Deza et al. [Discrete Comput. Geom., 35 (2006), pp. 597–615] proved that if the $X_i$ are in general position with respect to 0 (consequently, each $X_i$ has at least $d+1$ points), then there are at least $2d$ colorful covering simplices, and they constructed an example with no more than $d^2+1$ such simplices. Under the same assumption, we show that there are at least $\frac{1}{5}d(d+1)$ colorful covering simplices, thus determining the order of magnitude. A similar result was proved independently by Stephen and Thomas [http://www.arxiv.org/abs/math.CO/0512400 (2005)]. We also obtain a lower bound of $3d$ for $d \geq 3$, which is better for small d and, in particular, together with a parity argument it settles the case $d=3$, where the minimum possible number of colorful covering simplices is 10.

Given points P and Q in the plane, we are interested in separating them by two curves C1 and C2 such that every point of C1 has equal distance to P and to C2, and every point of C2 has equal distance to C1 and to Q. We show by elementary geometric means that such C1 and C2 exist and are unique. Moreover, for P = (0,1) and Q = (0,-1), C1 is the graph of a function ƒ: R → R, C2 is the graph of -f, and f is convex and analytic (i.e., given by a convergent power series at a neighborhood of every point). We conjecture that f is not expressible by elementary functions and, in particular, not algebraic. We provide an algorithm that, given x ∈ R and ε > 0, computes an approximation to f(x) with error at most ε in time polynomial in log 1+|x|/ε.The separation of two points by two "trisector" curves considered here is a special (two-point) case of a new kind of Voronoi diagram, which we call the Voronoi diagram with neutral zone and which we investigate in a companion paper.

A model for segmentation of an object space by an array of binary, radiation-field sensors and geometric reference structures is described. Given a family of binary, radiation-field sensors and a geometric reference structure, we refer to the set of sensor states induced by a source at point p as the signature of p . We study the segmentation of an object space into signature cells and prove near optimal bounds on the number of distinct signatures induced by a point source, as a function of sensor and reference structure complexity. We also show that almost any family of signatures can be implemented under this model.

There has been considerable recent interest in probabilistic packet marking schemes for sending information from nodes (routers) along one or more paths traveled by a stream of packets to the end-host receiving that stream. A central consideration for such schemes is the tradeoff between the number B of possible states of the marking bits in a packet, the number of bits n of information being sent by the nodes, and the expected number of packets T required to reconstruct this information. For the case where the packets all travel along the same path, we prove a lower bound of T ≥ Ω(B22n/(B-1)), roughly the square of an earlier lower bound of Adler.For an upper bound, we consider a model where each of m nodes along a single path must send one of s possible messages (thus n = m log2 s total bits are sent). We prove that T ≤ O(m • 22m(log2 s)/(B-1)) suffices (the implicit constant depends on B and s); this almost matches the lower bound, and is roughly the square root of an earlier upper bound of Adler. The new bound holds for all B and s in two slightly relaxed models, while under the strictest requirements we prove it only for some special values of B and s. This is related to a challenging geometric problem: the existence of an s-reptile (B-1)-dimensional simplex, i.e. a simplex S that can be tiled by s congruent simplices similar to S.We also consider the case where the packets travel along multiple paths to the same destination. In this case, we present a new protocol and analysis technique that together allow us to significantly generalize over previous work the scenarios where the protocol is effective.

We prove that random edge, the simplex algorithm that always chooses a random improving edge to proceed on, can take a mildly exponential number of steps in the model of abstract objective functions (introduced by K. W. Hoke (1998) and by G. Kalai (1988) under different names). We define an abstract objective function on the n-dimensional cube for which the algorithm, started at a random vertex, needs at least exp(const /spl middot/ n/sup 1/3/) steps with high probability. The best previous lower bound was quadratic. So in order for random edge to succeed in polynomial time, geometry must help.

A finite set ? ? Rd is a weak e-net for an n -point set X ? R d (with respect to convex sets) if N intersects every convex set K with | K n X |= en. We give an alternative, and arguably simpler, proof of the fact, first shown by Chazelle et al. [7], that every point set X in R d admits a weak e-net of cardinality O (e -d polylog(1/e)). Moreover, for a number of special point sets (e.g., for points on the moment curve), our method gives substantially better bounds. The construction yields an algorithm to construct such weak eps-nets in time O ( n ln(1e)). We also prove, by a different method, a near-linear upper bound for points uniformly distributed on the (d--1)-dimensional sphere.

(MATH) In the one-round Voronoi game, the first player chooses an n-point set $\PFRST$ in a square $Q$, and then the second player places another n-point set $\PSCND$ into $Q$. The payoff for the second player is the fraction of the area of $Q$ occupied by the regions of the points of $\PSCND$ in the Voronoi diagram of $\PFRST\cup\PSCND$. We give a strategy for the second player that always guarantees him a payoff of at least $\frac12+\alpha$, for a constant $\alpha>0$ independent of n. This contrasts with the one-dimensional situation, with $Q=[0,1]$, where the first player can always win more than 1/2.

Let B be a point robot moving in the plane, whose path is constrained to forward motions with a curvature at most 1, and let P be a convex polygon with n vertices.Given a starting configuration (a location and a direction of travel) for B inside P, we characterize the region of all points of P that can be reached by B, and show that it has linear complexity.

We introduce the concept of a {\em sensitive $\varepsilon$-approximation} and use it to derive a more efficient algorithm for computing $\varepsilon$-nets. We define and investigate product range spaces, for which we establish sampling theorems analogous to the standard finite VC-dimensional case. This generalizes and simplifies results from previous works. Using these tools, we give a new deterministic algorithm for computing the convex hull of n points in $\mbox{\smallBbb R}^d$. The algorithm is obtained by derandomization of a randomized incremental algorithm, and its running time of O(nlog n + n{\lfloor d/2\rfloor})$ is optimal for any fixed dimension $d\geq 2$.

We give simple randomized incremental algorithms for computing the Amk-level in an arrangement of n lines in the plane or in an arrangement of n planes in $\Reals^3$. The expected running time of our algorithms is $O(nk+n\alpha(n)\log n)$ for the planarcase and O(nk 2 + n log 3 n) for the three-dimensional case. Both bounds are optimal unless k is very small. The algorithm generalizes to computing the Amk-level in an arrangement of discs or x-monotone Jordan curves in the plane. Our approach can also compute the k-level; this yields a randomized algorithm for computing the order-k Voronoi diagram of n points in the plane in expected time O(k(n-k)log n + n log 3 n).

We present randomized algorithms for computing many faces in an arrangement of lines or of segments in the plane, which are considerably simpler and slightly faster than the previously known ones. The main new idea is a simple randomized $O(n \log n)$ expected time algorithm for computing $\sqrt{n}$ cells in an arrangement of n lines.

In casting, liquid is poured into a cast that has a cavity with the shape of the object to be manufactured. The liquid then hardens, after which the cast is removed. We consider the case where the cast consists of two parts and address the following problems. (1) Given a cast for an object and a direction , can the cast be partitioned into two parts such that the parts can be removed in directions and - , respectively, without colliding with the object or the other cast part? (2) How can one find a direction such that the above cast partitioning can be done? We give necessary and sufficient conditions for both problems, as well as algorithms to decide them for polyhedral objects. We also give some evidence that the case where the cast parts need not be removed in opposite directions is considerably harder.

No abstract available.

We give a simple lazy randomized incremental algorithm to compute ≤k-levels in arrangements of x-monotone Jordan curves in the plane, and in arrangements of planes in three-dimensional space. If each pair of curves intersects in at most s points, the expected running time of the algorithm is O(k2λs(n/k)+min(λs(n)log2n,k2λs(n/k)logn)). For the three-dimensional case the expected running time is O(nk2+min(nlog3n,nk2logn)). The algorithm also works for computing the ≤k-level in a set of discs, with an expected running time of O(nk+min(nlog2n,nklogn)). Furthermore, we give a simple algorithm for computing the order-k Voronoi diagram of a set of n points in the plane that runs in expected time O(k(n−k)logn+nlog3n).

We present randomized algorithms for computing many faces in an arrangement of lines or of segments in the plane, which are considerably simpler and slightly faster than the previously known ones. The main new idea is a simple randomized O(nlogn) expected time algorithm for computing √n cells in an arrangement of n lines.

We investigate the problem of finding the best solution satisfying all but k of the given constraints, for an abstract class of optimization problems introduced by Sharir and Welzl—the so-called LP-type problems. We give a general algorithm and discuss its efficient implementations for specific geometric problems. For instance, for the problem of computing the smallest circle enclosing all but k of the given n points in the plane, we obtain an O(nlogn+k3nε) algorithm; this improves previous results for k small compared ton but moderately growing.

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 introduce the concept of a sensitive /spl epsi/-approximation, and use it to derive a more efficient algorithm for computing /spl epsi/-nets. We define and investigate product range spaces, for which we establish sampling theorems analogous to the standard finite VC-dimensional case. This generalizes and simplifies results from previous works. We derive a simpler optimal deterministic convex hull algorithm, and by extending the method to the intersection of a set of balls with the same radius, we obtain an O(nlog/sup 3/ n) deterministic algorithm for computing the diameter of an n-point set in 3-dimensional space.>

Let B be a set of n arbitrary (possibly intersecting) convex obstacles in Rd.It is shown that any two points which can be connected by a path avoiding the obstacles can also be connected by a path consisting of 0(nId-l)ld/2+1~) segments.The bound cannot be improved below Q(nd); thus in R3, the answer is between n3 and n4.For disjoint obstacles, a ~(n) bound is proved.By a well-known reduction, thegeneralca.seresult also upper bounds the complexity for a translational motion of an arbitrary convex robot among convex obstacles.In the planar case, asymptotically tight bounds and efficient algorithms are given.1

We give a deterministic algorithm for computing the diameter of an n point set in ti~ree dimensions with O(n log' n) running time, c a constant.

Efficient algorithms for the ray shooting problem are presented: Given a collection $\Gamma $ of objects in $\mathbb{R}^d $, build a data structure so that, for a query ray, the first object of $\Gamma $ hit by the ray can be quickly determined. Using the parametric search technique, this problem is reduced to the segment emptiness problem. For various ray shooting problems, space/query-time trade-offs of the following type are achieved: For some integer b and a parameter $m(n \leqslant m \leqslant n^b )$ the queries are answered in time $O(({n / {m^{{1 / b}} }})\log ^{O(1)} n)$, with $O(m^{1 + \varepsilon } )$ space and preprocessing time ($\varepsilon > 0$ is arbitrarily small but fixed constant). $b = \lfloor {{d / 2}} \rfloor $ is obtained for ray shooting in a convex d-polytope defined as an intersection of n half spaces, $b = d$ for an arrangement of n hyperplanes in $\mathbb{R}^d $, and $b = 3$ for an arrangement of n half planes in $\mathbb{R}^3 $. This approach also yields fast procedures for finding the first k objects hit by a query ray, for searching nearest and farthest neighbors, and for the hidden surface removal. All the data structures can be maintained dynamically in amortized time $O({{m^{1 + \varepsilon } } / n})$ per insert/delete operation.

We present an improved space/query time tradeoff for the general simplex range searching problem, matching known lower bounds up to small polylogarithmic factors. In particular, we construct a linear-space simplex range searching data structure with O(n1–1/d) query time, which is optimal for d=2 and probably also for d>2. Further we show that multilevel range searching data structures can be built with only a polylogarithmic overhead in space and query time per level (the previous solutions require at least a small fixed power of n). We show that Hopcroft's problem (detecting an incidence among n lines and n points) can be solved in time n4/32O(log n). In all these algorithms, we apply Chazelle's results on computing optimal cuttings.

Article Free Access Share on Linear optimization queries Authors: Jiří Matoušek View Profile , Otfried Schwarzkopf View Profile Authors Info & Claims SCG '92: Proceedings of the eighth annual symposium on Computational geometryJuly 1992 Pages 16–25https://doi.org/10.1145/142675.142683Online:01 July 1992Publication History 42citation441DownloadsMetricsTotal Citations42Total Downloads441Last 12 Months23Last 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 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.

The authors describe dynamic data structures for half-space range reporting and for maintaining the minima of a decomposable function. Using these data structures, they obtain efficient dynamic algorithms for a number of geometric problems, including closest/farthest neighbor searching, fixed dimension linear programming, bi-chromatic closest pair, diameter, and Euclidean minimum spanning tree.>

Efficient algorithms for the ray shooting problem are presented: Given a collection F of objects in d, build a data structure so that, for a query ray, the first object of F hit by the ray can be quickly determined. Using the parametric search technique, this problem is reduced to the segment emptiness problem. For various ray shooting problems, space/query-time trade-offs of the following type are achieved: For some integer b and a parameter m (n _< m < n b) the queries are answered in time O((n/m /b) log <) n), with O(m!+) space and preprocessing time (t> 0 is arbitrarily small but fixed constant), b Ld/2J is obtained for ray shooting in a convex d-polytope defined as an intersection of n half spaces, b d for an arrangement of n hyperplanes in d, and b 3 for an arrangement of n half planes in 3. This approach also yields fast procedures for finding the first k objects hit by a query ray, for searching nearest and farthest neighbors, and for the hidden surface removal. All the data structures can be maintained dynamically in amortized time O (m + / n) per insert/delete operation.

Lo and Steiger resolved the complexity question for computing a planar ham-sandwich cut by giving an optimal linear-time algorithm. We show how to generalize the ideas to every fixed dimension d > 2 by describing an algorithm that computes a ham-sandwich cut in Rd in time O(nd–1–a(d)), for some a(d) > 0 (going to zero as d increases). For d = 3,4, the running time is almost proportional to ed–1(n;n/2), where dd(k;n) denotes the maximal number of k-sets over sets of n points in Rd, and with the current best bounds, we get O(n3/2 log2n/log n) running time for d = 3 and O(n8/3+e) for d=4. We also give a linear time algorithm for three dimensional ham-sandwich cuts when the three sets are suitably separated.

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

We prove a theorem on partitioning point sets in Ed (d fixed) and give an efficient construction of partition trees based on it. Such a partition tree for n points uses O(n) space, can be constructed in O(n log n) de-terministic time, and it can be used to answer simplex range queries (counting or general semigroup ones) in time O(nl–lld(log n) O[lJ). If we allow O(nl+d) pre-processing time, where 6 is some positive constant, a more complicated data structure yields query time O(nl-lld(loglog n) O(lJ). J?or dimensions d = 2,3 and if the weights of the points lie in a group, we get query time 0(nl-11d20(10g ” ‘)). This attains the lower bounds due to [Chazelle 89] upto polylogarithrnic factors, im-proving the results of [Chazelle et al. 90], making the preprocessing deterministic without loss of efficiency and simplifying the query answering algorithm. Dy-namization of our data structures and tradeoffs between preprocessing (and storage) and query time are also possible. The partition result is also applied for a deterministic computation of c-cuttings. E.g., given a collection of n lines in the plane and a parameter r < nl- $ for a fixed 6>0, the plane can be subdivided into O(r2) triangles, each intersected by at most n/r of the given lines, in time O(nl/2r3/2 + n log r), thus in almost linear time for r < n113. ●Part of thk research waa performed while the author was visiting at the Freie Universit5t Berlin.

The author considers the halfspace range reporting problem: Given a finite set P of points in E/sup d/, preprocess it so that given a query halfspace gamma , the points of p intersection gamma can be reported efficiently. It is shown that, with almost linear storage, this problem can be solved substantially more efficiently than the more general simplex range searching problem. A data structure for halfspace range reporting in dimensions d>or=4 is given. It uses O(n log log n) space and O (n log n) deterministic preprocessing time. The query time is also given. Results for the halfspace emptiness problem, where one only wants to know whether P intersection gamma is empty, are also presented.>

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

Let (X, R) be a set system on an n-point set X. For a two-coloring on X, its discrepancy is defined as the maximum number by which the occurrences of the two colors differ in any set in R. It is shown that if for any m-point subset Y contained in X the number of distinct subsets induced by R on Y is bounded by O(m/sup d/) for a fixed integer d is a coloring with discrepancy bounded by O(n/sup 1/2-1/2d/ (log n)/sup 1+1/2d/). Also, if any subcollection of m sets of R partitions the points into at most O(m/sup d/) classes, then there is a coloring with discrepancy at most O(n/sup 1/2-1/2d/ n). These bounds imply improved upper bounds on the size of in -approximations for (X, R). All of the bounds are tight up to polylogarithmic factors in the worst case. The results allow the generalization of several results of J. Beck (1984) bounding the discrepancy in certain geometric settings to the case when the discrepancy is taken relative to an arbitrary measure.>

Article Free Access Share on Approximations and optimal geometric divide-and-conquer Author: Jiří Matoušek Charles Univ., Prague, Czechoslovakia Charles Univ., Prague, CzechoslovakiaView Profile Authors Info & Claims STOC '91: Proceedings of the twenty-third annual ACM symposium on Theory of ComputingJanuary 1991 Pages 505–511https://doi.org/10.1145/103418.103470Published:03 January 1991Publication History 69citation528DownloadsMetricsTotal Citations69Total Downloads528Last 12 Months27Last 6 weeks4 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

An arrangement L of n lines in the plane is considered. A d-approximate level k for L is a polygonal line meeting every vertical exactly once, such that for its every point p there are at least $k - d$ and at most $k + d$ lines of L above p. A d-approximate leveling for L is a collection $P_1 ,P_2 , \cdots ,P_{\lfloor n / 2d \rfloor }$, where every $P_i $ is a d-approximate level $2di$. A deterministic algorithm is given that, for a given L and a parameter $r \leqq n$, computes an $(n / r)$-approximate leveling for L, whose approximate levels consist of $O(r^2 )$ segments in total. The time complexity of this algorithm is $O(nr^{4 / 3} (\log n)^{4 / 3} (\log \log n + \log r)^c )$ (c a small constant), which is now outperformed by algorithms of Matoušek [Proc. 5th Annual ACM Symposium on Computational Geometry, 1989, pp. 1–10] and Agarwal [Proc. 5th Annual ACM Symposium on Computational Geometry, 1989, pp. 11#8211;21]. A substantially different and elementary method is used here. An approximate leveling can be directly used for approximate halfplanar range counting, but it can also be used for plane partitioning applications, and thus as a subroutine in many recent computational geometry algorithms.

We will consider an arrangement H of n hyperplanes in Ed (where the dimension d is fixed). An ε-cutting for H will be a collection of (possibly unbounded) d-dimensional simplices with disjoint interiors, which cover all Ed and such that the interior of any simplex is intersected by at most εn hyperplanes of H. We give a deterministic algorithm, finding a (1/r)-cutting with 𝒪(rd(log r)C) simplices in time 𝒪(n(log n)Ard-1 (log r)B) (A,B,C are constants dependent on dimension). In a similar time bound (with an additional 𝒪(r𝒪(1)) overhead) we can also find a (1/r)-net for the range space (X, H(X)), where X is a n-point set in Ed and H(X) denotes the set of all subsets of X which can be cut by a halfspace. This (1/r)-net has size 𝒪(r log r), which matches the best known existence result; in fact, the method gives a constructive existence proof.

It is known that in general range spaces of VC-dimension d > 1 require ε-nets to be of size at least Ω(d/ε log 1/ε). We investigate the question whether this general lower bound is valid for the special range spaces that typically arise in computational geometry. We show that disks and pseudo-disks in the plane as well as halfspaces in R3 allow ε-nets of size only Ο(1/ε), which is best possible up to a multiplicative constant. The analogous questions for higher-dimensional spaces remain open.

Article Free Access Share on Construction of epsilon nets Author: J. Matoušek Dept. of Comp. Science, Charles University, Malostranské nám. 25, 118 00 Praha 1, Czechoslovakia Dept. of Comp. Science, Charles University, Malostranské nám. 25, 118 00 Praha 1, CzechoslovakiaView Profile Authors Info & Claims SCG '89: Proceedings of the fifth annual symposium on Computational geometryJune 1989Pages 1–10https://doi.org/10.1145/73833.73834Published:05 June 1989Publication History 15citation924DownloadsMetricsTotal Citations15Total Downloads924Last 12 Months60Last 6 weeks12 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

A set A of n points in the plane has to be stored in such a way that for any query triangle t the number of points of A inside t can be computed efficiently. For this problem a solution is presented with Ο(√n log n) query time, Ο (n log n) space and Ο(n3/2 log n) preprocessing time. The constants in the asymptotic bounds are small, and the method is easy to implement.