On s -intersecting curves and related problems
Sarit Buzaglo, Rom Holzman, Rom Pinchasi · 2008
Let P be a set of n points in the plane and let C be a family of simple closed curves in the plane each of which avoids the points of P. For every curve C ∈ C we denote by disc(C) the region in the plane bounded by C. Fix an integer s > 0 and assume that every two curves in C intersect at most s times and that for every two curves C,C' ∈ C the intersection disc(C) ∩ disc(C') is a connected set. We consider the family F = {P ∩ disc(C) | C ∈ C}. When s is even, we provide sharp bounds, in terms of n, s, and k, for the number of sets in F of cardinality k, assuming that ∩C ∈Cdisc(C) is nonempty. In particular, we provide sharp bounds for the number of halving pseudo-parabolas for a set of n points in the plane. Finally, we consider the VC-dimension of F and show that F has VC-dimension at most s+1.