2026-07-22T13:03:05Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8772 2024-03-06T10:42:37Z ddc:004 open_access

Further Consequences of the Colorful Helly Hypothesis Martínez-Sandoval, Leonardo Roldán-Pensado, Edgardo Rubin, Natan geometric transversals convex sets colorful Helly-type theorems line transversals weak epsilon-nets transversal numbers Let F be a family of convex sets in R^d, which are colored with d+1 colors. We say that F satisfies the Colorful Helly Property if every rainbow selection of d+1 sets, one set from each color class, has a non-empty common intersection. The Colorful Helly Theorem of Lovász states that for any such colorful family F there is a color class F_i subset F, for 1 <= i <= d+1, whose sets have a non-empty intersection. We establish further consequences of the Colorful Helly hypothesis. In particular, we show that for each dimension d >= 2 there exist numbers f(d) and g(d) with the following property: either one can find an additional color class whose sets can be pierced by f(d) points, or all the sets in F can be crossed by g(d) lines. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Leonardo Martínez-Sandoval and Edgardo Roldán-Pensado and Natan Rubin 2018 Is Part Of LIPIcs, Volume 99, 34th International Symposium on Computational Geometry (SoCG 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2018.59 urn:nbn:de:0030-drops-87726 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.59 eng https://creativecommons.org/licenses/by/3.0/legalcode