A Variant of the Hadwiger-Debrunner (p, q)-Problem in the Plane


Autoria(s): Govindarajan, Sathish; Nivasch, Gabriel
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