2026-07-20T05:59:30Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25005 2026-02-09T07:52:46Z ddc:004 open_access

Crossing and Non-Crossing Families Antić, Todor Balko, Martin Vogtenhuber, Birgit crossing family non-crossing family geometric graph For a finite set P of points in the plane in general position, a 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 non-crossing family of size m, which is a collection of 4 disjoint subsets P₁, P₂, P₃, and P₄ of P, each containing m points of P, such that for every choice of 4 points p_i ∈ P_i, the set {p₁,p₂,p₃,p₄} is such that p₄ is in the interior of the triangle formed by p₁,p₂,p₃. We prove that, for every m ∈ ℕ, each set P of n points in the plane in general position contains either a crossing family of size n/2^{O(√{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). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Todor Antić and Martin Balko and Birgit Vogtenhuber 2025 Is Part Of LIPIcs, Volume 357, 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.GD.2025.19 urn:nbn:de:0030-drops-250058 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2025.19 eng https://creativecommons.org/licenses/by/4.0/legalcode