Crossing and Non-Crossing Families

Let $P$ be a finite set of points in the plane. We say that $P$ is in general position if there is no line containing three points of $P$. Two line segments in the plane are crossing if their intersection is a single point in the relative interior of both of them. If $ℱ$ is a set of $k$ line segments in the plane, each having both endpoints in $P$, then we say that $ℱ$ is a crossing family of size $k$ in $P$ if any two line segments in $ℱ$ cross; see Figure 1(a) for an example.

A classic topic in discrete geometry is to find the largest size $T(n)$ of a crossing family in any set of $n$ points in the plane in general position. The study of this problem was initiated in 1991 by Aronov, Erdős, Goddard, Kleitman, Klugerman, Pach, and Schulman [9], who proved that $T(n)\in \mathrm{\Omega }(\sqrt{n})$. On the other hand, it is trivial to see that $T(n)\le \lfloor n/2\rfloor$. The currently best known upper bound is $T(n)\le \lceil 8n/41\rceil$, obtained by Aichholzer, Kynčl, Scheucher, Vogtenhuber, and Valtr [3]. There is a prevailing conjecture that $T(n)\in \mathrm{\Theta }(n)$ [9, 14].

Despite many attempts and several studied variants of the problem – see for example [3, 5, 19, 24, 29, 33] – to date no one has been able to resolve this problem. In fact, for a long time, not even an improvement of the lower bound of $\mathrm{\Omega }(\sqrt{n})$ was obtained. In 2021, Pach, Rubin, and Tardos [29] achieved a breakthrough result by proving that $T(n)\in n^{1-o(1)}$. More precisely, they showed the following result.

Despite this remarkable progress, the problem of deciding whether $T(n)\in \mathrm{\Theta }(n)$ remains open. Note that the problem becomes trivial if restricted to point sets in convex position, that is, point sets whose points are vertices of a convex polygon. It is easy to see that any set of $n$ points in convex position determines a crossing family of size $\lfloor n/2\rfloor$.

In this work, we study a variant of the crossing family problem where we relate the size of a largest crossing family in a point set to how convex/non-convex the point set is. A non-crossing family in a set $P$ of points in the plane is a collection of four disjoint non-empty subsets $P_1$, $P_2$, $P_3$, and $P_4$ of $P$, such that for every choice of four points $p_i\in P_i$ the set $\{p_1,p_2,p_3,p_4\}$ is not in convex position, with $p_4$ in the interior of the convex hull of $\{p_1,p_2,p_3\}$. The size of a non-crossing family is the minimum over the cardinalities of the four subsets $P_1$, $P_2$, $P_3$, and $P_4$. see Figure 1(b) for an example.

It is easy to see and follows from Carathédory’s theorem that a point set is in convex position if and only if it does not contain a non-crossing family of size one. Then, as we have mentioned, it is easy to find a linear-size crossing family. Towards answering the question of whether $T(n)\in \mathrm{\Theta }(n)$, we parameterize point sets according to the largest non-crossing family they contain, and try to find their largest crossing family in dependence of this parameter. We thus study the following Ramsey-type problem.

In particular, for which values of $m$ can we always find a crossing family that is larger than the bound $n/2^{O(\sqrt{\log n})}$ from Theorem 1 for any set of $n$ points in general position?

We first show that forbidding non-crossing families of some small size can indeed help in finding larger crossing families than the ones obtained from Theorem 1. We actually find something stronger, a so-called convex bundle.

For a positive integer $k$ and a point set $P$ in the plane, a convex bundle of size $k$ in $P$ is a $k$-tuple of disjoint non-empty subsets $C_1,\mathrm{\dots },C_k$ of $P$, such that for every choice of points $c_i\in C_i$ for every $i\in [k]$, the points $c_1,\mathrm{\dots },c_k$ are in convex position. The width of a convex bundle of size $k$ is the minimum over the cardinalities of its subsets $C_1,\mathrm{\dots },C_k$.

Our first result guarantees the existence of a convex bundle of size $\mathrm{\Theta }(n/m)$ in any $n$-point set without a non-crossing family of size $m$. To show it, we make use of the so-called Same-Type-Lemma [10], a classic result on orientations of point tuples in point sets.

Since every convex bundle of size $2k$ and width at least $1$ determines a crossing family of size $k$, we obtain the following immediate corollary of Theorem 2.

In particular, it follows from Corollary 3 that if our point set does not contain a constant size non-crossing family, then it contains a crossing family of linear size. Working with crossing families directly, we use Theorem 2 in combination with Theorem 5 below to improve the bound from Corollary 3 as follows, by this obtaining our main theorem.

Since no set of $n$ points in the plane contains a non-crossing family of size $n$, Theorem 1 can be obtained as a corollary of Theorem 4 by setting $m=n$. The lower bound on the size of the crossing families that we obtain by Theorem 4 is asymptotically larger than the bounds from Theorem 1 and Corollary 3, as long as the point set does not contain a non-crossing family of size $n^{\mathrm{\Omega }(1)}$. For example, if we forbid non-crossing families of size $\log n$, then we find a crossing family of size $\mathrm{\Omega }(n/2^{\sqrt{\log \log n}})$ instead of $n/2^{O(\sqrt{\log n})}$ and $\mathrm{\Omega }(n/\log n)$ that we would get from Theorem 1 and Corollary 3, respectively. Further, Theorem 4 implies that for any constant $m$, if $P$ is a set of $n$ points in the plane in general position with no non-crossing family of size $m$, then the complete geometric graph on $P$ can be decomposed into $cn$ plane subgraphs for some constant , by this resolving the problem of Bose, Hurtado, Rivera-Campo and Wood [12] for such point sets.

To prove Theorem 4, we use the following slight strengthening of Theorem 1, which we obtain by modifying the proof of the result by Pach, Rubin, and Tardos [29].

We also consider the algorithmic aspects of our results. The proofs of Theorems 2 and 4 are both constructive. By analyzing their time complexity, we obtain an expected linear time algorithm for Theorem 2 and an expected polynomial time algorithm for Theorem 4.

We remark that the non-determinism in the time complexities stems from an analysis of the runtime requirements of the Same-Type-Lemma. A deterministic variant of this building block would yield a deterministic analogue of Theorem 6. Further, we note that the proof of Theorem 1 is also constructive and results in an $n^{2+O({(\log n)}^{-1/3})}$ time algorithm for finding an according crossing family in a set of $n$ points; see [29].

Finally, we show that the size of the largest spoke set and the largest crossing family in a point set can differ by a constant multiplicative factor, showcasing the different behavior of these two closely related notions.

Note that if Problem 1 admits an affirmative solution, then the sizes of the maximal spoke set and the maximal crossing family differ by at most a constant multiplicative factor.

This section is devoted to proving our main result, the existence of a large crossing family or a large non-crossing family (Theorem 4), for which we will use and first prove the existence of a large convex bundle or a large non-crossing family (Theorem 2).

One crucial ingredient for the proof of Theorem 2 is a well-known result by Bárány and Valtr [10], called the Same-Type lemma, on the combinatorics of point sets in ${ℝ}^d$.

For an integer $d\ge 2$ and non-coplanar points $p_1,\mathrm{\dots },p_{d+1}\in {ℝ}^d$, where $p_{i,j}$ is the $j$th coordinate of $p_i$, the orientation of the $(d+1)$-tuple $(p_1,\mathrm{\dots },p_{d+1})$ is the sign of the determinant of the matrix

For point sets $Y_1,\mathrm{\dots },Y_{d+1}$ in ${ℝ}^d$, we say that the sets $Y_1,\mathrm{\dots },Y_{d+1}$ have the same-type property if, for every choice of points $y_1\in Y_1,\mathrm{\dots },y_{d+1}\in Y_{d+1}$, the orientation of the $(d+1)$-tuple $(y_1,\mathrm{\dots },y_{d+1})$ is the same. More generally, for every integer $r\ge d+1$, we say that sets $Y_1,\mathrm{\dots },Y_r$ in ${ℝ}^d$ have the same-type property if any $d+1$ of them do.

With these definitions, we can now state the Same-Type lemma.

Bárány and Valtr [10] showed that $c(d,r)\ge {(d+1)}^{(-2^d-1)\left(\genfrac{}{}{0pt}{}{r-1}{d}\right)}$. This was later improved by Fox, Pach, and Suk [18] to $c(d,r)\in 2^{-O(d^{3}r\log r)}$. Very recently, Bukh [15] proved the bounds $d^{-50d^3}{r}^{-d^2}\le c(d,r)\le d^d{r}^{-d}$, which are polynomial in $r$.

For disjoint sets $P$ and $Q$ of points in the plane, we write if the $x$-coordinate $x(p)$ of every point $p\in P$ is smaller than $x(q)$ for every point $q\in Q$. For a positive integer $a$, we say that $a$ points in the plane form an $a$-cap if they lie on the graph of some concave function. Similarly, for $u\in \mathbb{N}$, a set of $u$ points in the plane forms a $u$-cup if its points lie on the graph of some convex function. Note that any $a$-cap or $u$-cup is a point set in convex position.

In this section, we show that every set of $n$ points in the plane in general position partitioned into two separated nonempty subsets $P_1$ and $P_2$ of equal size contains a crossing family $ℱ$ of size at least $n/2^{O(\sqrt{\log n})}$, where each segment from $ℱ$ has one endpoint in $P_1$ and one endpoint in $P_2$. We do so by slightly modifying the proof of Theorem 1 by Pach, Rubin, and Tardos [29].

Let $ℒ$ be a finite set of lines in the plane. Following the terminology in [29], we call the partition $𝒜=𝒜(ℒ)$ of ${ℝ}^2\setminus \left(\bigcup ℒ\right)$ into 2-dimensional sets, called cells, the arrangement¹¹1We remark that in other literature, the line arrangement formed by a set $ℒ$ of lines also contains $ℒ$, partitioned into vertices, which are the crossings of $ℒ$, and edges, which are the (possibly unbounded) segments of lines of $ℒ$ between consecutive crossings. of lines from $ℒ$. Each cell of $𝒜$ is a maximal connected region of ${ℝ}^2\setminus \left(\bigcup ℒ\right)$ and a (possibly unbounded) convex polygon. The boundary of each cell consists of edges, which are portions of the lines from $ℒ$. The edges connect crossings between lines from $ℒ$, which are called vertices. The zone of a line $\mathrm{\ell }\notin ℒ$ in the arrangement $𝒜$ is the union of all the open cells whose closure is intersected by $\mathrm{\ell }$.

We will need the following result on point sets and line arrangements, which was implicitly established by Matoušek [26, 25]; see [29] for a proof.

The following definitions were introduced by Pach, Rubin, and Tardos [29]. For non-empty separated point sets $A$ and $B$, we define a binary relation on $A$ such that, for distinct points $x,y\in A$, we let if $B$ is contained in the open half-plane to the left of the line determined by $x$ and $y$ and oriented from $x$ towards $y$. Pach, Rubin, and Tardos [29] proved that is a partial order on $A$, in which two distinct points $x$ and $y$ are incomparable if and only if the line through $x$ and $y$ intersects $\mathrm{conv}(B)$.

For a partially ordered set , we use to denote the number of pairs of elements from $S$ that are incomparable in . For $\epsilon >0$, two separated point sets $A$ and $B$, each with $m$ points, are said to form an $\epsilon$-avoiding pair if

The following lemma is a variant of Lemma 3.3 by Pach, Rubin, and Tardos [29]. Its proof is a modification of their argument.

This section is devoted to the algorithmic aspects of Theorems 2 and 4. Specifically, we prove that there is a constant $C>0$ such that for all positive integers $k$ and $m$ if $P$ is a set of $n=Ckm$ points in the plane in general position, we can find a convex bundle of size $k$ and width $m$ or a non-crossing family of size $m$ in time $O(n)$. Similarly, we show that we can find a crossing family of size $n/2^{O(\sqrt{\log m})}$ or a non-crossing family of size $m$ in time $O(n{m}^{1+O({(\log m)}^{-1/3})})$.

To do so, we use a variant of the semi-algebraic regularity lemma recently proved by Rubin [31]. To state it, we first need to introduce some more definitions.

A Boolean function $\psi :{ℝ}^{d\times r}\to \{0,1\}$ is an $r$-wise semi-algebraic relation in ${ℝ}^d$ if it can be described by a finite combination $(f_1,\mathrm{\dots },f_s,\varphi )$, where $f_1,\mathrm{\dots },f_s\in ℝ[z_1,\mathrm{\dots },z_{rd}]$ are polynomials, and $\varphi$ is a Boolean function in ${\{0,1\}}^s\to \{0,1\}$, so that

holds for all the ordered $r$-tuples $(y_1,\mathrm{\dots },y_r)$ of points $y_i\in {ℝ}^d$. We call the $(s+1)$-tuple $(f_1,\mathrm{\dots },f_s,\varphi )$ a semi-algebraic description of $\psi$ (which need not be unique). Such a relation $\psi$ has description complexity at most $(\mathrm{\Delta },s)$ if it admits a description using at most $s$ polynomials $f_i\in ℝ[z_1,\mathrm{\dots },z_{rd}]$ of maximum degree at most $\mathrm{\Delta }$. We let ${\mathrm{\Psi }}_{d,r,\mathrm{\Delta },s}$ be the family of all such $r$-wise semi-algebraic relations $\psi :{ℝ}^{d\times r}\to \{0,1\}$ with description complexity bounded by $(\mathrm{\Delta },s)$.

The proof of the Same-Type Lemma by Fox, Pach, and Suk [18] is constructive. We go through it step by step in order to estimate the running time of the algorithm it yields. If $(p_1,\mathrm{\dots },p_n)$ is a sequence of $n\ge d+1$ points in ${ℝ}^d$ in general position, then the order-type of $(p_1,\mathrm{\dots },p_n)$ is the mapping $\chi :\left(\genfrac{}{}{0pt}{}{P}{d+1}\right)\to \{+1,-1\}$, which assigns to each $(d+1)$-tuple of these points its orientation (positive or negative). For integers $d\ge 2$ and $r\ge d+1$, let $X_1,\mathrm{\dots },X_r$ be pairwise disjoint sets in ${ℝ}^d$, each containing $n$ points, whose union is in general position. It is known that the number of different order-types of $r$-element point sets in ${ℝ}^d$ is at most $r^{O(d^{2}r)}$ [20, 21]. Thus, by the pigeonhole principle, at least $r^{-O(d^{2}r)}|X_1|\mathrm{\cdots }|X_r|$ $r$-tuples $(x_1,\mathrm{\dots },x_r)\in (X_1,\mathrm{\dots },X_r)$ have the same order-type $\chi$. We define the relation $E\subset X_1\times \mathrm{\cdots }\times X_r$, where $(x_1,\mathrm{\dots },x_r)\in E$ if and only if $(x_1,\mathrm{\dots },x_r)$ has the order-type $\chi$. Then it can be shown [18] that the description complexity of $E$ is $(\left(\genfrac{}{}{0pt}{}{r}{d+1}\right),1)$. Therefore, we can apply Theorem 12 to the $r$-partite semi-algebraic hypergraph $(P,E)$ with $d$, $r$, $\mathrm{\Delta }=\left(\genfrac{}{}{0pt}{}{r}{d+1}\right)$, $s=1$, $\delta =1$, and $\epsilon =r^{-O(d^{2}r)}$ to obtain subsets $Y_i\subseteq X_i$, each of cardinality $c(d,r)\cdot |X_i|$, with the same-type property, where $c(d,r)\in r^{-O(d^{3}r)}$, in time

Thus, we obtain the following estimate on the time complexity of the Same-Type Lemma.