Bounds on piercing and line-piercing numbers in families of convex sets in the plane

DOI10.1016/J.DISC.2023.113787MaRDI QIDQ6136671zbMATH OpenOpenAlexFDO

Authors Shira Zerbib

Publication date 17 January 2024

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2303.16240

zbMATH Keywords

convex sets in the planepiercing numbers\((p, q)\) property\((p, 2)\) propertyline-piercing numbers

Mathematics Subject Classification ID

Convex sets in (2) dimensions (including convex curves) (52A10)

Abstract: A family of sets has the $(p,q)$ property if among any $p$ members of it some $q$ intersect. It is shown that if a finite family of compact convex sets in $R^2$ has the $(p+1,2)$ property then it is pierced by $lfloorfracp2floor+1$ lines. A colorful version of this result is proved as well. As a corollary, the following is proved: Let $F$ be a finite family of compact convex sets in the plane with no isolated sets, and let $F^{\prime }$ be the family of its pairwise intersections. If $F$ has the $(p+1,2)$ property and $F^{\prime }$ has the $(r+1,2)$ property, then $F$ is pierced by $(lfloorfracr2floo{r}^2+lfloorfracr2floor)p$ points when $rge2$, and by $p$ points otherwise. The proofs use the topological KKM theorem.

Recommendations

• Bounding the piercing number
• scientific article; zbMATH DE number 1406328
• Piercing convex sets
• Piercing numbers for balanced and unbalanced families
• Piercing families of convex sets in the plane that avoid a certain subfamily with lines

Cites work

• scientific article; zbMATH DE number 4017764 (Why is no real title available?)
• scientific article; zbMATH DE number 3154393 (Why is no real title available?)
• scientific article; zbMATH DE number 2209723 (Why is no real title available?)
• A Gallai-type transversal problem in the plane
• A family of convex sets in the plane satisfying the (4, 3)-property can be pierced by nine points
• Bounding the piercing number
• Equilibrium in a discrete exchange economy with money
• Independent and hitting sets of rectangles intersecting a diagonal line: algorithms and complexity
• Line Transversals in Families of Connected Sets in the Plane
• On max-clique for intersection graphs of sets and the Hadwiger-Debrunner numbers
• Piercing axis-parallel boxes
• Piercing convex sets and the Hadwiger-Debrunner \((p,q)\)-problem
• Piercing families of convex sets with the \(d\)-intersection property in \(\mathbb R^{d}\)
• The \((2,2)\) and \((4,3)\) properties in families of Fat sets in the plane
• Transversals of 2-intervals, a topological approach
• Transversals of \(d\)-intervals
• Über eine Variante zum Hellyschen Satz
• Über eine kombinatorisch-geometrische Frage von Hadwiger und Debrunner

Cited in

(1)

• Piercing families of convex sets in the plane that avoid a certain subfamily with lines

This page was built for publication: Bounds on piercing and line-piercing numbers in families of convex sets in the plane

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6136671)