On s-intersecting curves and related problems

ABSTRACT

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 ∈C}disc(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.

REFERENCES

• 1: Pankaj K. Agarwal , Eran Nevo , János Pach , Rom Pinchasi , Micha Sharir , Shakhar Smorodinsky, Lenses in arrangements of pseudo-circles and their applications, Journal of the ACM (JACM), v.51 n.2, p.139-186, March 2004 [doi>10.1145/972639.972641]
• 2: Pankaj K. Agarwal , Micha Sharir, Pseudo-line arrangements: duality, algorithms, and applications, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.800-809, January 06-08, 2002, San Francisco, California
• 3: Noga Alon , Gil Kalai , Jirí Matousek , Roy Meshulam, Transversal numbers for hypergraphs arising in geometry, Advances in Applied Mathematics, v.29 n.1, p.79-101, July 2002 [doi>10.1016/S0196-8858(02)00003-9]
• 4: N. Alon and D. J. Kleitman, Piercing convex sets and the Hadwiger-Debrunner (p,q)-problem, Adv. Math. 96 (1992), 103--112.
• 5: T. K. Dey, Improved bounds for planar k-sets and related problems. Discrete Comput. Geom. 19 (1998), no. 3, 373--382.
• 6: E. Helly, Über Systeme abgeschlossener Mengen mit gemeinschaftlichen Punkten, Monatshefte d. Mathematik 37 (1930), 281--302.
• 7: J. Molnár, Über eine Verallgemeinerung auf die Kugelfläche eines topologischen Satzes von Helly, Acta Math. Acad. Sci. 7 (1956), 107--108.
• 8: N. Sauer, On the density of families of sets, Journal of Combinatorial Theory, Series A 25 (1972), 80--83.
• 9: S. Shelah, A combinatorial problem, stability and order for models and theories in infinite languages, Pacific J. Math. 41 (1972), 247--261.
• 10: J. Snoeyink and J. Hershberger, Sweeping arrangements of curves, DIMACS Series in Discrete Mathematics, Discrete and Computational Geometry, the DIMACS Special Year 6 (1991), 309--349.
• 11: G. Tóth, Point sets with many k-sets, Discrete Comput. Geom. 26 (2001) no. 2, 187--194.
• 12: Hisao Tamaki , Takeshi Tokuyama, A Characterization of Planar Graphs by Pseudo-Line Arrangements, Proceedings of the 8th International Symposium on Algorithms and Computation, p.133-142, December 17-19, 1997
• 13: V.N. Vapnik and A. Ya. Chervonenkis, On the uniform convergence of relative frequences of events to their probabilities, Theory Probab. Appl. 16 (1971), 264--280.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Counting problems

General Terms:
Theory

Keywords:
$k$-sets, curves, plane, points, vc-dimension