A Variant of the Hadwiger-Debrunner (p, q)-Problem in the Plane
Data(s) |
2015
|
---|---|
Resumo |
Let X be a convex curve in the plane (say, the unit circle), and let be a family of planar convex bodies such that every two of them meet at a point of X. Then has a transversal of size at most . Suppose instead that only satisfies the following ``(p, 2)-condition'': Among every p elements of , there are two that meet at a common point of X. Then has a transversal of size . For comparison, the best known bound for the Hadwiger-Debrunner (p, q)-problem in the plane, with , is . Our result generalizes appropriately for if is, for example, the moment curve. |
Formato |
application/pdf |
Identificador |
http://eprints.iisc.ernet.in/52469/1/Dis_Com_Geo_54-3_%20637_2015.pdf Govindarajan, Sathish and Nivasch, Gabriel (2015) A Variant of the Hadwiger-Debrunner (p, q)-Problem in the Plane. In: DISCRETE & COMPUTATIONAL GEOMETRY, 54 (3). pp. 637-646. |
Publicador |
SPRINGER |
Relação |
http://dx.doi.org/10.1007/s00454-015-9723-9 http://eprints.iisc.ernet.in/52469/ |
Palavras-Chave | #Computer Science & Automation (Formerly, School of Automation) |
Tipo |
Journal Article PeerReviewed |