A plank is the part of space between two parallel planes. The following open problem, posed 45 years ago, can be viewed as the converse of Tarski’s plank problem (Bang’s theorem): Is it true that if the total width of a collection of planks is sufficiently large, then the planks can be individually translated to cover a unit ball B? A translative covering of B by planks is said to be non-dissective if the planks can be added one by one, in some order, such that the uncovered part remains connected at each step and is empty at the end. Improving a classical result of Groemer, we show that every set of C/ε^{7/4} planks of width ε admits a non-dissective translative covering of a 3-dimensional ball B³, provided C is large enough. Our proof yields a low-complexity algorithm. We also show that c/ε^{4/3} planks are, in general, insufficient for a non-dissective covering of B³. This provides the first non-trivial lower bound for this problem.

According to a classical result of Spencer, Szemerédi, and Trotter (1984), the maximum number of times the unit distance can occur among n points in the plane is O(n^{4/3}). This is far from Erdős’s lower bound, n^{1+O(1/log log n)}, which is conjectured to be optimal. We prove a structural result for point sets with nearly n^{4/3} unit distances and use it to reduce the problem to a conjecture on rigid frameworks. This conjecture, if true, would yield the first improvement on the bound of Spencer et al. A weaker version of this conjecture has been established by Raz and Solymosi.

We study the problem of reconfiguring a crossing-free embedding of a graph on a surface, with edges represented as curves, into another crossing-free embedding of the same graph on the same surface with the same fixed vertex positions. In this process, we reroute one edge at a time while maintaining crossing-free intermediate embeddings. This problem was introduced by Ito et al. [TALG 2025], who showed that even if the graph is a matching of two edges, reconfiguration is not always possible in the plane, but is always possible on the torus. For matchings of two or more edges, they gave a necessary and sufficient condition for reconfigurable embeddings in the plane, but not on the torus. Our main result is that for matchings, trees and forests, reconfiguration is always possible on the torus, and consequently, on any orientable surface of genus at least one. In addition, we provide sufficient conditions for reconfiguration on orientable surfaces of genus at least one and in the projective plane. For more general graphs, we show that reconfiguration is not always possible.

Abstract The Upper Bound Theorem for convex polytopes implies that the p -th Betti number of the Čech complex of any set of N points in $${{\mathbb R}}^d$$ R d and any radius satisfies $${\beta }_{p}{} = O(N^{m})$$ β p = O ( N m ) , with $$m = \min \{ p+1, {\big \lceil d/2 \big \rceil } \}$$ m = min { p + 1 , ⌈ d / 2 ⌉ } . We construct sets in even and odd dimensions that prove this upper bound is asymptotically tight. For example, we describe a set of $$N = 2(n+1)$$ N = 2 ( n + 1 ) points in $${{\mathbb R}}^3$$ R 3 and two radii such that the first Betti number of the Čech complex at one radius is $$(n+1)^2 - 1$$ ( n + 1 ) 2 - 1 , and the second Betti number of the Čech complex at the other radius is $$n^2$$ n 2 .

We prove that if a graph can be drawn in the plane such that each edge crosses at most k other edges, then it can be redrawn so that each edge participates in at most k³+O(k²) crossings. This improves the previous exponential bound that follows from a result of Schaefer and Štefankovič and answers a question of Ackerman and Schaefer.

Abstract. We consider partitions of a point set into two parts, and the lengths of the minimum spanning trees (MSTs) of the original set and of the two parts. If [Formula: see text] denotes the length of an MST of [Formula: see text], we show that every set [Formula: see text] of [Formula: see text] points admits a nontrivial bipartition [Formula: see text] for which the MST-ratio [Formula: see text] is strictly larger than 1 and that 1 is the largest number with this property. Furthermore, we provide a fast algorithm that computes such a bipartition in [Formula: see text] time and one that computes the corresponding MST-ratio in [Formula: see text] time. In certain settings, a much better MST-ratio can be guaranteed. For example, if [Formula: see text] is a set of [Formula: see text] random points uniformly distributed in [Formula: see text], then for any [Formula: see text], the MST-ratio in a maximizing partition is at least [Formula: see text] with probability tending to 1 as [Formula: see text]. Our results and techniques are extendable to higher dimensions.

The Upper Bound Theorem for convex polytopes implies that the p-th Betti number of the Čech complex of any set of N points in ℝ^d and any radius satisfies β_p = O(N^m), with m = min{p+1, ⌈d/2⌉}. We construct sets in even and odd dimensions, which prove that this upper bound is asymptotically tight. For example, we describe a set of N = 2(n+1) points in ℝ³ and two radii such that the first Betti number of the Čech complex at one radius is (n+1)² - 1, and the second Betti number of the Čech complex at the other radius is n². In particular, there is an arrangement of n contruent balls in ℝ³ that enclose a quadratic number of voids, which answers a long-standing open question in computational geometry.

We prove a far-reaching strengthening of Szemerédi's regularity lemma for intersection graphs of pseudo-segments. It shows that the vertex set of such a graph can be partitioned into a bounded number of parts of roughly the same size such that almost all bipartite graphs between different pairs of parts are complete or empty. We use this to get an improved bound on disjoint edges in simple topological graphs, showing that every $n$-vertex simple topological graph with no $k$ pairwise disjoint edges has at most $n(\log n)^{O(\log k)}$ edges.

A complete geometric graph consists of a set P of n points in the plane, in general position, and all segments (edges) connecting them. It is a well known question of Bose, Hurtado, Rivera-Campo, and Wood, whether there exists a positive constant c < 1, such that every complete geometric graph on n points can be partitioned into at most cn plane graphs (that is, noncrossing subgraphs). We answer this question in the affirmative in the special case where the underlying point set P is dense, which means that the ratio between the maximum and the minimum distances in P is of the order of Θ(√n).

Abstract. It is known that any open necklace with beads of [Formula: see text] types, in which the number of beads of each type is divisible by [Formula: see text], can be partitioned by at most [Formula: see text] cuts into intervals that can be distributed into [Formula: see text] collections, each containing the same number of beads of each type. This is tight for all values of [Formula: see text] and [Formula: see text]. Here, we consider the case of random necklaces, where the number of beads of each type is [Formula: see text]. Then the minimum number of cuts required for a “fair” partition with the above property is a random variable [Formula: see text]. We prove that for fixed [Formula: see text] and large [Formula: see text], this random variable is at least [Formula: see text] with high probability. For [Formula: see text], fixed [Formula: see text], and large [Formula: see text], we determine the asymptotic behavior of the probability that [Formula: see text] for all values of [Formula: see text]. We show that this probability is polynomially small when [Formula: see text], is bounded away from zero when [Formula: see text], and decays like [Formula: see text] when [Formula: see text]. We also show that for large [Formula: see text], [Formula: see text] is at most [Formula: see text] with high probability and that for large [Formula: see text] and large ratio [Formula: see text], [Formula: see text] is [Formula: see text] with high probability.

The disjointness graph of a set system is a graph whose vertices are the sets, two being connected by an edge if and only if they are disjoint. It is known that the disjointness graph G of any system of segments in the plane is χ-bounded, that is, its chromatic number χ(G) is upper bounded by a function of its clique number ω(G). Here we show that this statement does not remain true for systems of polygonal chains of length 2. We also construct systems of polygonal chains of length 3 such that their disjointness graphs have arbitrarily large girth and chromatic number. In the opposite direction, we show that the class of disjointness graphs of (possibly self-intersecting) 2-way infinite polygonal chains of length 3 is χ-bounded: for every such graph G, we have χ(G) ≤ (ω(G))³+ω(G).

An r-quasiplanar graph is a graph drawn in the plane with no r pairwise crossing edges. Let s≥3 be an integer and r=2s. We prove that there is a constant C such that every r-quasiplanar graph with n≥r vertices has at most nCs−1logn2s−4 edges. A graph whose vertices are continuous curves in the plane, two being connected by an edge if and only if they intersect, is called a string graph. We show that for every ϵ>0, there exists δ>0 such that every string graph with n vertices whose chromatic number is at least nϵ contains a clique of size at least nδ. A clique of this size or a coloring using fewer than nϵ colors can be found by a polynomial time algorithm in terms of the size of the geometric representation of the set of strings. In the process, we use, generalize, and strengthen previous results of Lee, Tomon, and others. All of our theorems are related to geometric variants of the following classical graph-theoretic problem of Erdős, Gallai, and Rogers. Given a Kr-free graph on n vertices and an integer s

In a recent breakthrough, Adiprasito, Avvakumov, and Karasev constructed a triangulation of the $n$-dimensional real projective space with a subexponential number of vertices. They reduced the problem to finding a small downward closed set-system $\cal F$ covering an $n$-element ground set which satisfies the following condition: for any two disjoint members $A, B\in\cal F$, there exist $a\in A$ and $b\in B$ such that either $B\cup\{a\}\in\cal F$ and $A\cup\{b\}\setminus\{a\}\in\cal F$, or $A\cup\{b\}\in\cal F$ and $B\cup\{a\}\setminus\{b\}\in\cal F$. Denoting by $f(n)$ the smallest cardinality of such a family $\cal F$, they proved that $f(n)<2^{O(\sqrt{n}\log n)}$, and they asked for a nontrivial lower bound. It turns out that the construction of Adiprasito, Avvakumov, and Karasev is not far from optimal; we show that $2^{(1.42+o(1))\sqrt{n}}\le f(n)\le 2^{(1+o(1))\sqrt{2n\log n}}$. We also study a variant of the above problem, where the condition is strengthened by also requiring that for any two disjoint members $A, B\in\cal F$ with $|A|>|B|$, there exists $a\in A$ such that $B\cup\{a\}\in\cal F$. In this case, we prove that the size of the smallest $\cal F$ satisfying this stronger condition lies between $2^{\Omega(\sqrt{n}\log n)}$ and $2^{O(n\log\log n/\log n)}$.

Given a family F of k-element sets, S₁,…,S_r ∈ F form an r-sunflower if S_i ∩ S_j = S_{i'} ∩ S_{j'} for all i ≠ j and i' ≠ j'. According to a famous conjecture of Erdős and Rado (1960), there is a constant c = c(r) such that if |F| ≥ c^k, then F contains an r-sunflower. We come close to proving this conjecture for families of bounded Vapnik-Chervonenkis dimension, VC-dim(F) ≤ d. In this case, we show that r-sunflowers exist under the slightly stronger assumption |F| ≥ 2^{10k(dr)^{2log^{*} k}}. Here, log^* denotes the iterated logarithm function. We also verify the Erdős-Rado conjecture for families F of bounded Littlestone dimension and for some geometrically defined set systems.

A string graph is the intersection graph of a family of continuous arcs in the plane. The intersection graph of a family of plane convex sets is a string graph, but not all string graphs can be obtained in this way. We prove the following structure theorem conjectured by Janson and Uzzell: The vertex set of almost all string graphs on n vertices can be partitioned into five cliques such that some pair of them is not connected by any edge ( \(n\rightarrow \infty \) ). We also show that every graph with the above property is an intersection graph of plane convex sets. As a corollary, we obtain that almost all string graphs on n vertices are intersection graphs of plane convex sets.

Let G be a drawing of a graph with n vertices and $$e>4n$$ edges, in which no two adjacent edges cross and any pair of independent edges cross at most once. According to the celebrated Crossing Lemma of Ajtai, Chvátal, Newborn, Szemerédi and Leighton, the number of crossings in G is at least $$c\,{e^3\over n^2}$$ , for a suitable constant $$c>0$$ . In a seminal paper, Székely generalized this result to multigraphs, establishing the lower bound $$c\,{e^3\over mn^2}$$ , where m denotes the maximum multiplicity of an edge in G. We get rid of the dependence on m by showing that, as in the original Crossing Lemma, the number of crossings is at least $$c'{e^3\over n^2}$$ for some $$c'>0$$ , provided that the “lens” enclosed by every pair of parallel edges in G contains at least one vertex. This settles a conjecture of Bekos, Kaufmann, and Raftopoulou.

A matrix is homogeneous if all of its entries are equal. Let $P$ be a $2\times 2$ zero-one matrix that is not homogeneous. We prove that if an $n\times n$ zero-one matrix $A$ does not contain $P$ as a submatrix, then $A$ has a $cn\times cn$ homogeneous submatrix for a suitable constant $c>0$. We further provide an almost complete characterization of the matrices $P$ (missing only finitely many cases) such that forbidding $P$ in $A$ guarantees an $n^{1-o(1)}\times n^{1-o(1)}$ homogeneous submatrix. We apply our results to chordal bipartite graphs, totally balanced matrices, halfplane arrangements, and string graphs.

We consider m-colorings of the edges of a complete graph, where each color class is defined semi-algebraically with bounded complexity. The case m = 2 was first studied by Alon et al., who applied this framework to obtain surprisingly strong Ramsey-type results for intersection graphs of geometric objects and for other graphs arising in computational geometry. Considering larger values of m is relevant, e.g., to problems concerning the number of distinct distances determined by a point set. For p >= 3 and m >= 2, the classical Ramsey number R(p;m) is the smallest positive integer n such that any m-coloring of the edges of K_n, the complete graph on n vertices, contains a monochromatic K_p. It is a longstanding open problem that goes back to Schur (1916) to decide whether R(p;m)=2^{O(m)}, for a fixed p. We prove that this is true if each color class is defined semi-algebraically with bounded complexity, and that the order of magnitude of this bound is tight. Our proof is based on the Cutting Lemma of Chazelle et al., and on a Szemerédi-type regularity lemma for multicolored semi-algebraic graphs, which is of independent interest. The same technique is used to address the semi-algebraic variant of a more general Ramsey-type problem of Erdős and Shelah.

The Vapnik–Chervonenkis dimension (in short, VC-dimension) of a graph is defined as the VC-dimension of the set system induced by the neighborhoods of its vertices. We show that every n-vertex graph with bounded VC-dimension contains a clique or an independent set of size at least $$e^{(\log n)^{1 - o(1)}}$$ . The dependence on the VC-dimension is hidden in the o(1) term. This improves the general lower bound, $$e^{c\sqrt{\log n}}$$ , due to Erdős and Hajnal, which is valid in the class of graphs satisfying any fixed nontrivial hereditary property. Our result is almost optimal and nearly matches the celebrated Erdős–Hajnal conjecture, according to which one can always find a clique or an independent set of size at least $$e^{\Omega (\log n)}$$ . Our results partially explain why most geometric intersection graphs arising in discrete and computational geometry have exceptionally favorable Ramsey-type properties. Our main tool is a partitioning result found by Lovász–Szegedy and Alon–Fischer–Newman, which is called the “ultra-strong regularity lemma” for graphs with bounded VC-dimension. We extend this lemma to k-uniform hypergraphs, and prove that the number of parts in the partition can be taken to be $$(1/\varepsilon )^{O(d)}$$ , improving the original bound of $$(1/\varepsilon )^{O(d^2)}$$ in the graph setting. We show that this bound is tight up to an absolute constant factor in the exponent. Moreover, we give an $$O(n^k)$$ -time algorithm for finding a partition meeting the requirements. Finally, we establish tight bounds on Ramsey–Turán numbers for graphs with bounded VC-dimension.

The disjointness graph G=G(S) of a set of segments S in R^d, d>1 is a graph whose vertex set is S and two vertices are connected by an edge if and only if the corresponding segments are disjoint. We prove that the chromatic number of G satisfies chi(G)<=omega(G)^4+omega(G)^3 where omega(G) denotes the clique number of G. It follows, that S has at least cn^{1/5} pairwise intersecting or pairwise disjoint elements. Stronger bounds are established for lines in space, instead of segments. We show that computing omega(G) and chi(G) for disjointness graphs of lines in space are NP-hard tasks. However, we can design efficient algorithms to compute proper colorings of G in which the number of colors satisfies the above upper bounds. One cannot expect similar results for sets of continuous arcs, instead of segments, even in the plane. We construct families of arcs whose disjointness graphs are triangle-free (omega(G)=2), but whose chromatic numbers are arbitrarily large.

It is proved that the total length of any set of countably many rectifiable curves, whose union meets all straight lines that intersect the unit square U, is at least 2.00002. This is the first improvement on the lower bound of 2 by Jones in 1964. A similar bound is proved for all convex sets U other than a triangle.

Following groundbreaking work by Haussler and Welzl (1987), the use of small epsilon-nets has become a standard technique for solving algorithmic and extremal problems in geometry and learning theory. Two significant recent developments are: (i) an upper bound on the size of the smallest epsilon-nets for set systems, as a function of their so-called shallow-cell complexity (Chan, Grant, Konemann, and Sharpe); and (ii) the construction of a set system whose members can be obtained by intersecting a point set in R^4 by a family of half-spaces such that the size of any epsilon-net for them is at least (1/(9*epsilon)) log (1/epsilon) (Pach and Tardos). The present paper completes both of these avenues of research. We (i) give a lower bound, matching the result of Chan et al., and (ii) generalize the construction of Pach and Tardos to half-spaces in R^d, for any d >= 4, to show that the general upper bound of Haussler and Welzl for the size of the smallest epsilon-nets is tight.

If two closed Jordan curves in the plane have precisely one point in common, then it is called a touching point. All other intersection points are called crossing points. The main result of this paper is a Crossing Lemma for closed curves: In any family of n pairwise intersecting simple closed curves in the plane, no three of which pass through the same point, the number of crossing points exceeds the number of touching points by a factor of Ω((log log n)1/8). As a corollary, we prove the following long-standing conjecture of Richter and Thomassen: The total number of intersection points between any n pairwise intersecting simple closed curves in the plane, no three of which pass through the same point, is at least (1 – o(1))n2.

In this paper, we prove several extremal results for geometrically defined hypergraphs. In particular, we establish an improved lower bound, single exponentially decreasing in $k$, on the best constant $\delta>0$ such that the vertex classes $P_1,\ldots,P_k$ of every $k$-partite $k$-uniform semialgebraic hypergraph $H=(P_1\cup\cdots\cup P_k, E)$ with $|E|\ge\varepsilon\Pi_{j=1}^k|P_i|$ have, for $1 \leq i \leq k$, $\delta|P_i|$-element subsets $P'_i\subseteq P_i$ satisfying $P_{1}'\times\cdots\times P_{k}'\subseteq E$. The best previously known lower bound on $\delta$ due to Bukh and Hubard decreased triple exponentially fast in $k$. We give three geometric applications of our results. In particular, we establish the following strengthening of the so-called same-type lemma of Bárány and Valtr: Any disjoint finite sets $P_1,\ldots,P_k\subset \mathbb{R}^d\; (k>d)$ have, for $1 \leq i \leq k$, subsets $P'_i$ of size at least $2^{-O(d^3k\log k)}|P_i|$ with the property that every $k$-tuple formed by taking one point from each $P'_i$ has the same order type. We also improve a result of Fox, Gromov, Lafforgue, Naor, and Pach, who established a regularity lemma for semialgebraic $k$-uniform hypergraphs of bounded complexity, showing that for each $\varepsilon>0$ the vertex set can be equitably partitioned into a bounded number of parts (in terms of $\varepsilon$ and the complexity) so that all but an $\varepsilon$-fraction of the $k$-tuples of parts are homogeneous. Here, we prove that the number of parts can be taken to be polynomial in $1/\varepsilon$. Our improved regularity lemma can be applied to geometric problems and to the following general question on property testing: is it possible to decide, with query complexity polynomial in the reciprocal of the approximation parameter, whether a hypergraph has a given hereditary property? We give an affirmative answer for testing typical hereditary properties for semialgebraic hypergraphs of bounded complexity.

A k-uniform semi-algebraic hypergraph H is a pair (P, E), where P is a subset of ℝd and E is a collection of k-tuples {p1, …, pk} ⊂ P such that (p1, …, pk) ∊ E if and only if the kd coordinates of the pi-s satisfy a boolean combination of a finite number of polynomial inequalities. The complexity of H can be measured by the number and the degrees of these inequalities and the number of variables (coordinates) kd. Several classical results in extremal hypergraph theory can be substantially improved when restricted to semi-algebraic hypergraphs. Substantially improving a theorem of Fox, Gromov, Lafforgue, Naor, and Pach, we establish the following “polynomial regularity lemma”: For any 0 < ε < 1/2, the vertex set of every k-uniform semi-algebraic hypergraph H = (P, E) can be partitioned into at most (1/ε)c parts P1, P2, …, as equal as possible, such that all but at most an ε-fraction of the k-tuples of parts (Pi1, …, Pik) are homogeneous in the sense that either every k-tuple (pi1, …, pik) ∊ Pi1 × … × Pik belongs to E or none of them do. Here c > 0 is a constant that depends on the complexity of H. We also establish an improved lower bound, single exponentially decreasing in k, on the best constant δ > 0 such that the vertex classes P1, …, Pk of every k-partite k-uniform semi-algebraic hypergraph H = (P1 ∪ … ∪ Pk, E) with |E| ≥ εΠkj=1|Pi| have, for 1 ≤ i ≤ k, δ|Pi|-element subsets P′i ⊆ Pi satisfying P′1 × … × P′k ⊆ E. The best previously known lower bound on δ due to Bukh and Hubard decreased double exponentially fast in k. We give three geometric applications of our results. In particular, we establish the following strengthening of the so-called same-type lemma of Bárány and Valtr: Any disjoint finite sets P1, …, Pk ⊂ ℝd (k > d) have for 1 ≤ i ≤ k subsets P′i of size at least 2−O(d3k log k)|Pi| with the property that every k-tuple formed by taking one point from each P′i has the same order type. The above techniques carry over to property testing. We show that for any typical hereditary hypergraph property , there is a randomized algorithm with query complexity ) to determine (with probability at least .99) whether a k-uniform semi-algebraic hypergraph H = (P,E) with constant description complexity is ε-near to having property , that is, whether one can change at most ε|P|k hyperedges of H in order to obtain a hypergraph that has the property. The testability of such properties for general k-uniform hypergraphs was first shown by Alon and Shapira (for graphs) and by Rödl and Schacht (for k > 2). The query complexity time of their algorithms is enormous, growing considerably faster than a tower function.

A long standing conjecture of Richter and Thomassen states that the total number of intersection points between any n simple closed Jordan curves in the plane, so that any two of them intersect and no three curves pass through the same point, is at least (1 – o(1))n2. We confirm the above conjecture in several important cases, including the case (1) when all curves are convex, and (2) when the family of curves can be partitioned into two equal classes such that each curve from the first class is touching every curve from the second class. (Two curves are said to be touching if they have precisely one point in common, at which they do not properly cross.) An important ingredient of our proofs is the following statement: Let S be a family of the graphs of n continuous real functions defined on ℝ, no three of which pass through the same point. If there are nt pairs of touching curves in S, then the number of crossing points is .

We consider the variation of Ramsey numbers introduced by Erdös and Pach [J. Graph Theory, 7 (1983), pp. 137--147], where instead of seeking complete or independent sets we only seek a $t$-homogeneous set, a vertex subset that induces a subgraph of minimum degree at least $t$ or the complement of such a graph. For any $\nu > 0$ and positive integer $k$, we show that any graph $G$ or its complement contains as an induced subgraph some graph $H$ on $\ell \ge k$ vertices with minimum degree at least $\frac12(\ell-1) + \nu$ provided that $G$ has at least $k^{\Omega(\nu^2)}$ vertices. We also show this to be the best possible in a sense. This may be viewed as correction to a result claimed in [P. Erdös and J. Pach, J. Graph Theory, 7 (1983), pp. 137--147]. For the above result, we permit $H$ to have order at least $k$. In the harder problem, where we insist that $H$ have exactly $k$ vertices, we do not obtain sharp results, although we show a way to translate results of one form of the problem to the other.

Given a polygonal region containing a target point (which we assume is the origin), it is not hard to see that there are two points on the perimeter that are antipodal, i.e., whose midpoint is the origin. We prove three generalizations of this fact. (1) For any polygon (or any bounded closed region with connected boundary) containing the origin, it is possible to place a given set of weights on the boundary so that their barycenter (center of mass) coincides with the origin, provided that the largest weight does not exceed the sum of the other weights. (2) On the boundary of any 3-dimensional bounded polyhedron containing the origin, there exist three points that form an equilateral triangle centered at the origin. (3) On the 1-skeleton of any 3-dimensional bounded convex polyhedron containing the origin, there exist three points whose center of mass coincides with the origin.

Let S be a set of n points in R2 contained in an algebraic curve C of degree d. We prove that the number of distinct distances determined by S is at least cdn4/3, unless C contains a line or a circle.

For natural numbers d and t there exists a positive C such that if F is a family of nC semi-algebraic sets in Rd of description complexity at most t, then there is a subset F' of F of size $n$ such that either every pair of elements in F' intersect or the elements of F' are pairwise disjoint. This result, which also holds if the intersection relation is replaced by any semi-algebraic relation of bounded description complexity, was proved by Alon, Pach, Pinchasi, Radoicic, and Sharir and improves on a bound of 4n for the family F which follows from a straightforward application of Ramsey's theorem. We extend this semi-algebraic version of Ramsey's theorem to k-ary relations and give matching upper and lower bounds for the corresponding Ramsey function, showing that it grows as a tower of height k-1. This improves on a direct application of Ramsey's theorem by one exponential. We apply this result to obtain new estimates for some geometric Ramsey-type problems relating to order types and one-sided sets of hyperplanes. We also study the off-diagonal case, achieving some partial results.

We prove that planar graphs have $O(\log^2 n)$ queue number, thus improving upon the previous $O(\sqrt n)$ upper bound. Consequently, planar graphs admit three-dimensional straight-line crossing-free grid drawings in $O(n \log^8 n)$ volume, thus improving upon the previous $O(n^{3/2})$ upper bound.

A graph drawn in the plane is called $k$-quasi-planar if it does not contain $k$ pairwise crossing edges. It has been conjectured for a long time that for every fixed $k$, the maximum number of edges of a $k$-quasi-planar graph with $n$ vertices is $O(n)$. The best known upper bound is $n(\log n)^{O(\log k)}$. In the present paper, we improve this bound to $(n\log n )2^{\alpha(n)^{c_k}}$ in the special case where the graph is drawn in such a way that every pair of edges meet at most once. Here $\alpha(n)$ denotes the (extremely slowly growing) inverse of the Ackermann function. We also make further progress on the conjecture for $k$-quasi-planar graphs in which every edge is drawn as an $x$-monotone curve. Extending some ideas of Valtr, we prove that the maximum number of edges of such graphs is at most $2^{ck^6}n\log n$.

We settle a problem of Dujmović, Eppstein, Suderman, and Wood by showing that there exists a function $f$ with the property that every planar graph $G$ with maximum degree $d$ admits a drawing with noncrossing straight-line edges, using at most $f(d)$ different slopes. If we allow the edges to be represented by polygonal paths with one bend, then $2d$ slopes suffice. Allowing two bends per edge, every planar graph with maximum degree $d\ge 3$ can be drawn using segments of at most $\lceil d/2\rceil$ different slopes. There is only one exception: the graph formed by the edges of an octahedron is 4-regular, yet it requires 3 slopes. Every other planar graph requires exactly $\lceil d/2\rceil$ slopes.

Given a collection C of curves in the plane, its string graph is defined as the graph with vertex set C, in which two curves in C are adjacent if and only if they intersect. Given a partially ordered set (P,<), its incomparability graph is the graph with vertex set P, in which two elements of P are adjacent if and only if they are incomparable.

According to a well known theorem of Haussler and Welzl (1987), any range space of bounded VC-dimension admits an epsilon-net of size O (1/epsilon log 1/epsilon). Using probabilistic techniques, Pach and Woeginger (1990) showed that there exist range spaces of VC-dimension 2, for which the above bound is sharp. The only known range spaces of small VC-dimension, in which the ranges are geometric objects in some Euclidean space and the size of the smallest epsilon-nets is superlinear in 1/epsilon, were found by Alon (2010). In his examples, every epsilon-net is of size Omega (1/epsilon g(1/epsilon)), where g is an extremely slowly growing function, related to the inverse Ackermann function.

The overlap number of a finite (d + 1)-uniform hypergraph H is the largest constant c(H) ∊ (0, 1] such that no matter how we map the vertices of H into ℝd, there is a point covered by at least a c(H)-fraction of the simplices induced by the images of its hyperedges. In [18], motivated by the search for an analogue of the notion of graph expansion for higher dimensional simplicial complexes, it was asked whether or not there exists a sequence {Hn}n=1∞ of arbitrarily large (d + 1)-uniform hypergraphs with bounded degree, for which infn ≥1 c(Hn) > 0. Using both random methods and explicit constructions, we answer this question positively by constructing infinite families of (d + 1)-uniform hypergraphs with bounded degree such that their overlap numbers are bounded from below by a positive constant c = c(d). We also show that, for every d, the best value of the constant c = c(d) that can be achieved by such a construction is asymptotically equal to the limit of the overlap numbers of the complete (d + 1)-uniform hypergraphs with n vertices, as n → • ∞. For the proof of the latter statement, we establish the following geometric partitioning result of independent interest. For any d and any ε > 0, there exists K = K(ε,d) ≥ d + 1 satisfying the following condition. For any k ≥ K, for any point q ∊ ℝd and for any finite Borel measure μ on ℝd with respect to which every hyperplane has measure 0, there is a partition ℝ = A1 U … U Ak into k measurable parts of equal measure such that all but at most an ε-fraction of the (d + 1)-tuples Ai1, …, Aid+1 have the property that either all simplices with one vertex in each Aij contain q or none of these simplices contain q.

Computing the maximum number of disjoint elements in a collection C of geometric objects is a classical problem in computational geometry with applications ranging from frequency assignment in cellular networks to map labeling in computational cartography. The problem is equivalent to finding the independence number, α(GC), of the intersection graph GC of C, obtained by connecting two elements of C with an edge if and only if their intersection is nonempty. This is known to be an NP-hard task even for systems of segments in the plane with at most two different slopes. The best known polynomial time approximation algorithm for systems of arbitrary segments is due to Agarwal and Mustafa, and returns in the worst case an n1/2 + o(1)-approximation for α. Using extensions of the Lipton-Tarjan separator theorem, we improve this result and present, for every ε > 0, a polynomial time algorithm for computing α(GC) with approximation ratio at most nε. In contrast, for general graphs, for any ε > 0 it is NP-hard to approximate the independence number within a factor of n1–ε. We also give a subexponential time exact algorithm for computing the independence number of intersection graphs of arcwise connected sets in the plane.

Let C be a family of n convex bodies in the plane, which can be decomposed into k subfamilies of pairwise disjoint sets. It is shown that the number of tangencies between the members of C is at most O(kn), and that this bound cannot be improved. If we only assume that our sets are connected and vertically convex, that is, their intersection with any vertical line is either a segment or the empty set, then the number of tangencies can be superlinear in n, but it cannot exceed n(n log2 n). Our results imply a new upper bound on the number of regular intersection points on the boundary of *C.

We prove that planar graphs have poly-logarithmic queue number, thus improving upon the previous polynomial upper bound. Consequently, planar graphs admit 3D straight-line crossing-free grid drawings in small volume.

A topological graph is a graph drawn in the plane with vertices represented by points and edges as arcs connecting its vertices. A k-grid in a topological graph is a pair of subsets of the edge set, each of size k, such that every edge in one subset crosses every edge in the other subset. It is known that for a fixed constant k, every n-vertex topological graph with no k-grid has O(n) edges.

The intersection graph of a collection C of sets is a graph on the vertex set C, in which C1,C2 ∈ C are joined by an edge if and only if C1 ∩ C2 ≠ Ø. Erdös conjectured that the chromatic number of triangle-free intersection graphs of n segments in the plane is bounded from above by a constant. Here we show that it is bounded by a polylogarithmic function of n, which is the first nontrivial bound for this problem. More generally, we prove that for any t and k, the chromatic number of every Kk-free intersection graph of n curves in the plane, every pair of which have at most t points in common, is at most (ct log n/log k)c log k, where c is an absolute constant and ct only depends on t. We establish analogous results for intersection graphs of convex sets, x-monotone curves, semialgebraic sets of constant description complexity, and sets that can be obtained as the union of a bounded number of sets homeomorphic to a disk.

What is the smallest number τ = τ(n) such that for any collection of n pairwise disjoint convex sets in d-dimensional Euclidean space, there is a point such that any ray (half-line) emanating from it meets at most τ sets of the collection? This question of Urrutia is closely related to the notion of regression depth introduced by Rousseeuw and Hubert (1996). We show the following:

Let G be a connected graph, and let V and $V'$ be two n-element subsets of its vertex set $V(G)$. Imagine that we place a chip at each element of V and we want to move them into the positions of $V'$ (V and $V'$ may have common elements). A move is defined as shifting a chip from $v_1$ to $v_2$ ($v_1,v_2 \in V(G)$) on a path formed by edges of G so that no intermediate vertices are occupied. We give upper and lower bounds on the number of moves that are necessary and analyze the computational complexity of this problem under various assumptions: labeled versus unlabeled chips, arbitrary graphs versus the case when the graph is the rectangular (infinite) planar grid, etc. We prove hardness and inapproximability results for several variants of the problem. We also give a linear time algorithm which performs an optimal (minimum) number of moves for the unlabeled version in a tree, and a constant-ratio approximation algorithm for the unlabeled version in a graph. The graph algorithm uses the tree algorithm as a subroutine.

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.

Suppose that the whole plane (or a large region) is monitored by aset S of stationary sensors such that each element s ∈ S canobserve an axis-parallel unit square R(s) centered at s, whichis called the range of s. Each sensor s is equipped witha battery of unit lifetime. Is it true that if every point of theplane belongs to the range of many sensors, then we can monitorthe plane for a long time without running out of power? If S canbe partitioned into k parts S1, S2,..., Sk such that, foreach i, the sensors in Si together can observe the wholeplane, then the plane can be monitored with no interruption fork units of time. Indeed, we can first switch on all sensorsbelonging to S1. After these sensors run out of battery, we canswitch on all elements of S2, etc.We arrive at the following problem. Let m(k) denote the smallestpositive integer m such that any m-fold covering of the planewith axis-parallel unit squares splits into at least kcoverings. We show that m(k)=O(k2), and generalize this resultto translates of any centrally symmetric convex polygon in theplace of squares. From the other direction, we know only that m(k) ≥ ⌊4k/3⌋ -1.

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.

Let G be a graph with n vertices and e ≥ 4n edges, drawn in the plane in such a way that if two or more edges (arcs) share an interior point p ,then they must properly cross one another at p. It is shown that the number of crossing points, counted without multiplicity, is at least constant times e and that the order of magnitude of this bound cannot be improved. If, in addition, two edges are allowed to cross only at most once, then the number of crossing points must exceed constant times (e/n)4.

At most how many edges (hyperedges, nonzero entries, characters) can a graph (hypergraph, zero-one matrix, string) have if it does not contain a fixed forbidden pattern? Turán-type extremal graph theory, Erdős--Ko--Rado-type extremal set theory, Ramsey theory, the theory of Davenport--Schinzel sequences, etc. have been developed to address questions of this kind. They produced a number of results that found important applications in discrete and computational geometry.In the present paper, we discuss an extension of extremal graph theory to ordered graphs, i.e., to graphs whose vertex set is linearly ordered. In the most interesting cases, the forbidden ordered graphs are bipartite, and the basic problem can be reformulated as an extremal problem for zero-one matrices avoiding a certain submatrix P. We disprove a general conjecture of Füredi and Hajnal related to the latter problem, and replace it by some weaker alternatives. We verify our conjectures in a few special cases when P is the adjacency matrix of an acyclic graph and discuss the same question when the forbidden patterns are adjacency matrices of cycles.Our results lead to a new proof of the celebrated theorem of Spencer, Szemerédi, and Trotter [15] stating that the number of times that the unit distance can occur among n points in the plane is O(n4/3). This is the first proof that does not use any tool other than a forbidden pattern argument. We present another geometric application, where the forbidden pattern P is the adjacency matrix of an acyclic graph. A hippodrome is a c x d rectangle with two semidisks of diameter d attached to its sides of length d. Improving a result of Efrat and Sharir [5] we show that the number of "free" placements of a convex n-gon in general position in a hippodrome H such that simultaneously three vertices of the polygon lie on the boundary of H, is O(n). This result is related to the Planar Segment-Center Problem.

We study dynamic self-reconfiguration of modular metamorphicsystems. We guarantee the feasibility of motion planning in a rectangular model consisting of square modules that are allowed to slide along or rotate about one another. That is, we show that any two connected configurations of the same numberof modules can be transformed into each other by a sequence ofmoves so that all intermediate configurations are connected. This settles a conjecture formulated in [6].

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.

Twenty years ago, Ajtai, Chvatal, Newborn, Szemeredi, and, independently, Leighton discovered that the crossing number of any graph with v vertices and e>4v edgesis at least ce3/v2, where c>0 is an absolute constant. This result, known as the 'Crossing Lemma,' has found many important applications in discrete and computational geometry. It is tightup to a multiplicative constant. Here we improve the best known value of the constant by showing that the result holds with c>1024/31827>0.032. The proof has two new ingredients, interesting on their own right. We show that (1) if a graph can be drawn in the plane so that every edge crosses at most 3 others, then its number of edges cannot exceed 5.5(v-2); and (2) the crossing number of any graph is at least 73e - 253(v-2). Both bounds are tight up to anadditive constant (the latter one in the range 4v ≤ e ≤ 5v).

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.

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.

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.

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

A triangle is said to be {\it $\delta$-fat\/} if its smallest angle is at least $\delta>0$. A connected component of the complement of the union of a family of triangles is called a {\it hole}. It is shown that any family of n $\delta$-fat triangles in the plane determines at most $O\left(\frac{n}{\delta}\log\frac{2}{\delta}\right)$ holes. This improves on some earlier bounds of Efrat, Rote, Sharir, and Matousek, et al. Solving a problem of Agarwal and Bern, we also give a general upper bound for the number of holes determined by n triangles in the plane with given angles. As a corollary, we obtain improved upper bounds for the boundary complexity of the union of fat polygons in the plane, which, in turn, leads to better upper bounds for the running times of some known algorithms for motion planning, for finding a separator line for a set of segments, etc.

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

Article Cutting glass Share on Authors: János Pach Courant Institute, NYU and Rényi Institute, Hungarian Academy Courant Institute, NYU and Rényi Institute, Hungarian AcademyView Profile , Gábor Tardos Rényi Institute, Hungarian Academy Rényi Institute, Hungarian AcademyView Profile Authors Info & Claims SCG '00: Proceedings of the sixteenth annual symposium on Computational geometryMay 2000 Pages 360–369https://doi.org/10.1145/336154.336223Online:01 May 2000Publication History 1citation359DownloadsMetricsTotal Citations1Total Downloads359Last 12 Months11Last 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 SiteGet Access

A triangle is said to be /spl delta/-fat if its smallest angle is at least /spl delta/>0. A connected component of the complement of the union of a family of triangles is called hole. It is shown that any family of /spl delta/-far triangles in the plane determines at most O (n//spl delta/ log 2//spl delta/) holes. This improves on some earlier bounds of (Efrat et al., 1993; Matousek et al., 1994). Solving a problem of (Agarwal and Bern, 1999) we also give a general upper bound for the number of holes determined by n triangles in the plane with given angles. As a corollary, we obtain improved upper bounds for the boundary complexity of the union of fat polygons in the plane, which, in turn, leads to better upper bounds for the running times of some known algorithms for motion planning, for finding a separator line for a set of segments, etc.

The crossing number , cr(G) , of a graph G is the least number of crossing points in any drawing of G in the plane. Denote by κ(n,e) the minimum of cr(G) taken over all graphs with n vertices and at least e edges. We prove a conjecture of Erdos os and Guy by showing that κ(n,e)n 2 /e 3 tends to a positive constant as n→∈fty and n l e l n 2 . Similar results hold for graph drawings on any other surface of fixed genus.

A drawing of a graph G is a mapping which assigns to each vertex a point of the plane and to each edge a simple continuous arc connecting the corresponding two points. The crossing number of G is the minimum number of crossing points in any drawing of G. We define two new parameters, as follows. The pairwise crossing number (resp. the odd-crossing number) of G is the minimum number of pairs of edges that cross (resp. cross an odd number of times) over all drawings of G. We prove that the determination of each of these parameters is an NP-complete problem. We also prove that the largest of these numbers (the crossing number) cannot exceed twice the square of the smallest (the odd-crossing number). Our proof is based on the following generalization of an old result of Hanani, which is of independent interest. Let G be a graph and let E/sub 0/ be a subset of its edges such that there is a drawing of G, in which every edge belonging E/sub 0/ crosses any other edge an even number of times. Then G can be redrawn so that the element of E/sub 0/ are not involved in any crossing.

Let P1, P2,…, Pd+1 be pairwise disjoint n-element point sets in general position in d-space. It is shown that there exist a point O and suitable subsets Qi ⊆ Pi (i = 1, 2,…, d + 1) such that Qi ≥ cdPi, an every d-dimensional simplex with exactly one vertex in each Qi contains Q in its interior. Here cd is a positive constant depending only on d.

We show that for any 2-coloring of the ~) segments determined by n points in the plane, one of the color classes contains non-crossing cycles of lengths 3,4,.... [ ~j.This result is tight up to a multiplicative constant.Under the same assumptions, we also prove that there is a non-crossing path of length Q(n2f3), all of whose edges are of the same color.In the special case when the n points are in convex position, we find longer monochromatic non-crossing paths, of length [ ~1.This bound cannot be improved.All of these cycles and paths can be found by O(n2) time algorithms.We also discuss some related problems and generalizations.In particular, we give sharp estimates for the largest number of disjoint monochromatic triangles that can always be selected from our segments.

Given a geometric graph, i.e., a collection of segments (edges) between n points in the plane, does it contain a non-crossing configuration of a certain type? It is widely conjectured that all such problems are NP--hard. This has been verified in many special cases, including the existence of a non-crossing spanning tree or k disjoint segments. Here we show that these problems become computationally simpler if we are allowed to choose where to find a non-crossing spanning tree (or k disjoint edges): in the graph or in its complement. We prove that for any 2-coloring of the \\Gamma n 2 \\Delta segments determined by n points in the plane, at least one of the color classes contains a non-crossing spanning tree, and it can be found in O(n log log n+O(1) ) time. Under the same assumptions, we also prove that there exist b n+1 3 c pairwise disjoint segments of the same color, and they can be found with the same efficiency. The nonalgorithmic parts of the above theorems were conjec...

A thrackte is a graph that can be drawn in the plane so that its edges are represented by Jordan arcs and any two distinct arcs either meet at exactly one common vertex or cross at exactly one point interior to both arcs.About thirty years ago, J. H. Conway conjectured that the number of edges of a thrackle cannot exceed the number of its vertices.We show that a thrackle has at most twice as many edges as vert ices.Some related problems and generalizations are also considered.

We show that any graph of n vertices that can be drawn in the plane with no k+1 pairwise crossing edges has at most cknlog2k−2n edges. This gives a partial answer to a dual version of a well-known problem of Avital-Hanani, Erdős, Kupitz, Perles, and others. We also construct two point sets {p1,…,pn}, {q1,…,qn} in the plane such that any piecewise linear one-to-one mapping f:R2→R2 with f(pi)=qi (1≤i≤n) is composed of at least Ω(n2) linear pieces. It follows from a recent result of Souvaine and Wenger that this bound is asymptotically tight. Both proofs are based on a relation between the crossing number and the bisection width of a graph.

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.

A geometric graph is a graph drawn in the plane such that its edges are closed line segments and no 3 vertices are collinear. We settle an old question of Avital, Hanani, Erdös, Kupitz and Perles by showing that every geometric graph with n vertices and m > k4n edges contains k+1 pairwise disjoint edges. We also prove that, given a set of points V and a set of axis-parallel rectangles in the plane, then either there are k+1 rectangles such that no point of V belongs to more than one of them, or we can find an at most 2˙105k8 element subset of V meeting all rectangles. This improves a result of Ding, Seymour and Winkler. Both proofs are based on Dilworth's theorem on partially ordered sets.

Given n points in the plane, a crossing family is a collection of line segments, each joining two of the points, such that any two line segments intersect internally.We show that any n points in general position possess a crossing family of size at least ~, and describe an O(n log n)-time algorithm for finding one.

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 $S = \{ e_1 , \cdots ,e_n \} $ be a collection of n (intersecting) line segments in the plane. Suppose that all segments have their right endpoints lying on the same vertical line, and that one wishes to bound the number of pairs of nonintersecting vertically visible segments that will intersect when extended to the right ($e_i$, $e_j$ are vertically visible if there exists a vertical line segment connecting a point on ei to a point on $e_i$ and not meeting any other segment). It is shown that there are at most $O(n\log ^2 n)$ such pairs, and only $O(n\log n)$ in the case of full rays, where the latter bound can be attained in the worst case. These results are applied to obtain similar upper and lower bounds on the maximum size of the queue in the original implementation of the Bentley–Ottmann algorithm for reporting all intersections between the segments in S, i.e., the implementation where future events are not deleted from the queue. It is also shown that, without the extra conditions on the segments in S and on the pairs of segments to be counted, the number of nonintersecting vertically visible pairs of segments is $O(n^{4 / 3} (\log n)^{2 / 3} )$, and can be $\Omega (n^{4 / 3} )$ in the worst case.

We show that the maximum combinatorial complexity of the space of hyperplane transversals to a family of n separated and strictly convex sets in Rd is Θ(n⌊d/2⌋), which generalizes results of Edelsbrunner and Sharir in the plane. As a key step in the argument, we show that the space of hyperplanes tangent to κ ≤ d separated and strictly convex sets in Rd is a topological (d - κ)-sphere.

Given any natural number d, 0 < ε < 1, let ƒd(ε) denote the smallest integer ƒ such that every range space of Vapnik-Chervonenkis dimension d has an ε-net of size at most ƒ We solve a problem of Haussler and Welzl by showing that if d ≥ 2, then ƒd(ε) > 1/48 d/ε log 1/ ε which is not far from being optimal, if d is fixed and ε → 0. Further, we prove that ƒ1(ε) = max(2,⌈1/ε⌉ - 1), and similar bounds are established for some special classes of range spaces of Vapnik-Chervonenkis dimension three.

Given a set S of n points, a subset X of size k is called a k-set if there is a hyperplane II that separates X from X/sup c/. It is proved that O(n square root k/log/sub */k) is an upper bound for the number of k-sets in the plane, thus improving the previous bound of P. Erdos et al. (A Survey of Combinatorial Theory, North-Holland, 1983, p.139-49) by a factor of log/sub */k. The method can be extended to give the bound O(n square root k/(log k)/sup epsilon /). The proof only establishes the weaker result; it uses the geometry and combinatorics together in a stronger way than in the earlier work.>

Motivated by a number of motion-planning questions, we investigate in this paper some general topological and combinatorial properties of the boundary of the union of n regions bounded by Jordan curves in the plane. We show that, under some fairly weak conditions, a simply connected Riemann surface can be constructed that exactly covers this union and whose boundary has combinatorial complexity that is nearly linear, even though the covered region can have quadratic complexity. In the case where our regions are delimited by Jordan arcs in the upper halfplane starting and ending on the x-axis such that any pair of arcs intersect in at most three points, we prove that the total number of subarcs that appear on the boundary of the union is only Θ(nα(n)), where α(n) is the extremely slowly growing functional inverse of Ackermann's function.

Answering a question of Rosenstiehl and Tarjan, we show that every plane graph with n vertices has a Fáry embedding (i.e., straight-line embedding) on the 2n - 4 by n - 2 grid and provide an Ο(n) space, Ο(n log n) time algorithm to effect this embedding. The grid size is asymptotically optimal and it had been previously unknown whether one can always find a polynomial sized grid to support such an embedding. On the other hand we show that any set F, which can support a Fáry embedding of every planar graph of size n, has cardinality at least n + (1 - ο(1)) √n which settles a problem of Mohar.

A series of explicit low-rate binary linear codes that have relatively low covering radius and can be rapidly decoded is exhibited. These codes can be derived from higher-dimensional analogs of the Gale-Berlekamp switching game. Conjectures of independent interest involving Hadamard matrices are given that could yield semiexplicit covering codes of very low density.>

We consider the problem of obtaining sharp (nearly quadratic) bounds for the combinatorial complexity of the lower envelope (i.e. pointwise minimum) of a collection of n bivariate (or generally multi-variate) continuous and "simple" functions, and of designing efficient algorithms for the calculation of this envelope. This problem generalizes the well-studied univariate case (whose analysis is based on the theory of Davenport-Schinzel sequences), but appears to be much more difficult and still largely unsolved. It is a central problem that arises in many areas in computational and combinatorial geometry, and has numerous applications including generalized planar Voronoi diagrams, hidden surface elimination for intersecting surfaces, purely translational motion planning, finding common transversals of polyhedra, and more. In this abstract we provide several partial solutions and generalizations of this problem, and apply them to the problems mentioned above. The most significant of our results is that the lower envelope of n triangles in three dimensions has combinatorial complexity at most O(n2α(n)) (where α(n) is the extremely slowly growing inverse of Ackermann's function), that this bound is tight in the worst case, and that this envelope can be calculated in time O(n2α(n)).