Crossing and non-crossing families
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912551765278720 |
|---|---|
| author | Antić, Todor Balko, Martin Vogtenhuber, Birgit |
| author_facet | Antić, Todor Balko, Martin Vogtenhuber, Birgit |
| contents | For a finite set $P$ of points in the plane in general position, a \emph{crossing family} of size $k$ in $P$ is a collection of $k$ line segments with endpoints in $P$ that are pairwise crossing. It is a long-standing open problem to determine the largest size of a crossing family in any set of $n$ points in the plane in general position. It is widely believed that this size should be linear in $n$.
Motivated by results from the theory of partitioning complete geometric graphs, we study a variant of this problem for point sets $P$ that do not contain a \emph{non-crossing family} of size $m$, which is a collection of 4 disjoint subsets $P_1$, $P_2$, $P_3$, and $P_4$ of $P$, each containing $m$ points of $P$, such that for every choice of 4 points $p_i \in P_i$, the set $\{p_1,p_2,p_3,p_4\}$ is such that $p_4$ is in the interior of the triangle formed by $p_1,p_2,p_3$. We prove that, for every $m \in \mathbb{N}$, each set $P$ of $n$ points in the plane in general position contains either a crossing family of size $n/2^{O(\sqrt{\log{m}})}$ or a non-crossing family of size $m$, by this strengthening a recent breakthrough result by Pach, Rubin, and Tardos (2021). Our proof is constructive and we show that these families can be obtained in expected time $O(nm^{1+o(1)})$. We also prove that a crossing family of size $Ω(n/m)$ or a non-crossing family of size $m$ in $P$ can be found in expected time $O(n)$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_17277 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Crossing and non-crossing families Antić, Todor Balko, Martin Vogtenhuber, Birgit Combinatorics Computational Geometry G.2 For a finite set $P$ of points in the plane in general position, a \emph{crossing family} of size $k$ in $P$ is a collection of $k$ line segments with endpoints in $P$ that are pairwise crossing. It is a long-standing open problem to determine the largest size of a crossing family in any set of $n$ points in the plane in general position. It is widely believed that this size should be linear in $n$. Motivated by results from the theory of partitioning complete geometric graphs, we study a variant of this problem for point sets $P$ that do not contain a \emph{non-crossing family} of size $m$, which is a collection of 4 disjoint subsets $P_1$, $P_2$, $P_3$, and $P_4$ of $P$, each containing $m$ points of $P$, such that for every choice of 4 points $p_i \in P_i$, the set $\{p_1,p_2,p_3,p_4\}$ is such that $p_4$ is in the interior of the triangle formed by $p_1,p_2,p_3$. We prove that, for every $m \in \mathbb{N}$, each set $P$ of $n$ points in the plane in general position contains either a crossing family of size $n/2^{O(\sqrt{\log{m}})}$ or a non-crossing family of size $m$, by this strengthening a recent breakthrough result by Pach, Rubin, and Tardos (2021). Our proof is constructive and we show that these families can be obtained in expected time $O(nm^{1+o(1)})$. We also prove that a crossing family of size $Ω(n/m)$ or a non-crossing family of size $m$ in $P$ can be found in expected time $O(n)$. |
| title | Crossing and non-crossing families |
| topic | Combinatorics Computational Geometry G.2 |
| url | https://arxiv.org/abs/2508.17277 |