Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

A collection of simple closed Jordan curves in the plane is called a family of pseudo-circles if any two of its members intersect at most twice. A closed curve composed of two subarcs of distinct pseudo-circles is said to be an empty lens if the closed Jordan region that it bounds does not intersect any other member of the family. We establish a linear upper bound on the number of empty lenses in an arrangement of n pseudo-circles with the property that any two curves intersect precisely twice. We use this bound to show that any collection of n x-monotone pseudo-circles can be cut into O(n^8/5) arcs so that any two intersect at most once; this improves a previous bound of O(n^5/3) due to Tamaki and Tokuyama. If, in addition, the given collection admits an algebraic representation by three real parameters that satisfies some simple conditions, then the number of cuts can be further reduced to O(n^3/2(log n)^O(α(s(n))), where α(n) is the inverse Ackermann function, and s is a constant that depends on the the representation of the pseudo-circles. For arbitrary collections of pseudo-circles, any two of which intersect exactly twice, the number of necessary cuts reduces still further to O(n^4/3). As applications, we obtain improved bounds for the number of incidences, the complexity of a single level, and the complexity of many faces in arrangements of circles, of pairwise intersecting pseudo-circles, of arbitrary x-monotone pseudo-circles, of parabolas, and of homothetic copies of any fixed simply shaped convex curve. We also obtain a variant of the Gallai--Sylvester theorem for arrangements of pairwise intersecting pseudo-circles, and a new lower bound on the number of distinct distances under any well-behaved norm.

REFERENCES

• 1: Agarwal, P. K., Aronov, B., and Sharir, M. 2003. On the complexity of many faces in arrangements of pseudo-segments and of circles. In Discrete and Computational Geometry: The Goodman-Pollack Festschrift, B. Aronov, S. Basu, J. Pach, and M. Sharir, Eds. Springer Verlag, Berlin, Germany 1--23.
• 2: Pankaj K. Agarwal , Alon Efrat , Micha Sharir, Vertical Decomposition of Shallow Levels in 3-Dimensional Arrangements and Its Applications, SIAM Journal on Computing, v.29 n.3, p.912-953, Dec. 1999 to Jan. 2000 [doi>10.1137/S0097539795295936]
• 3: Agarwal, P. K., and Matoušek, J. 1994. On range searching with semialgebraic sets. Disc. Comput. Geom. 11, 393--418.
• 4: Agarwal, P. K., and Sharir, M. 2000. Arrangements and their applications. In Handbook of Computational Geometry, J.-R. Sack and J. Urrutia, Eds. Elsevier Science Publishers B.V. North-Holland, Amsterdam, 49--119.
• 5: 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]
• 6: Alon, N., and Kleitman, D. 1992. Piercing convex sets and the Hadwiger--Debrunner (p, q)-problem. Adv. Math. 96, 1, 103--112.
• 7: Alon, N., Last, H., Pinchasi, R., and Sharir, M. 2001. On the complexity of arrangements of circles in the plane. Disc. Comput. Geom. 26, 103--112.
• 8: Aronov, B., and Sharir, M. 2002. Cutting circles into pseudo-segments and improved bounds for incidences. Disc. Comput. Geom. 28, 475--490.
• 9: Basu, S., Pollack, R., and Roy, M.-F. 2003. Algorithms in Real Algebraic Geometry. Springer-Verlag, New York.
• 10: Bochnak, J., Coste, M., and Roy, M.-F. 1998. Real Algebraic Geometry. Springer-Verlag, Heidelberg, Germany.
• 11: Chan, T. M. 2003. On levels in arrangements of curves. Disc. Comput. Geom. 29, 275--293.
• 12: Bernard Chazelle , Herbert Edelsbrunner , Leonidas J. Guibas , Micha Sharir, A Singly-Expenential Stratification Scheme for Real Semi-Algebraic Varieties and Its Applications, Proceedings of the 16th International Colloquium on Automata, Languages and Programming, p.179-193, July 11-15, 1989
• 13: Kenneth L. Clarkson , Herbert Edelsbrunner , Leonidas J. Guibas , Micha Sharir , Emo Welzl, Combinatorial complexity bounds for arrangements of curves and spheres, Discrete & Computational Geometry, v.5 n.2, p.99-160, 1990 [doi>10.1007/BF02187783]
• 14: Herbert Edelsbrunner, Algorithms in combinatorial geometry, Springer-Verlag New York, Inc., New York, NY, 1987
• 15: Erdős, P. 1946. On a set of distances of n points. Amer. Math. Monthly 53, 248--250.
• 16: Goodman, J. E., and Pollack, R. 1993. Allowable sequences and order types in discrete and computational geometry. In New Trends in Discrete and Computational Geometry, J. Pach, Ed. Algorithms and Combinatorics, vol. 10. Springer-Verlag, New York, 103--134.
• 17: Hanani, C. C. A. 1934. Über wesentlich unplättbare Kurven im dreidimensionalen Raume. Fund. Math. 23, 135--142. (Hungarian with German and Russian Summaries).
• 18: Haussler, D., and Welzl, E. 1987. Epsilon-nets and simplex range queries. Disc. Comput. Geom. 2, 127--151.
• 19: Helly, E. 1930. Über Systeme von abgeschlossenen Mengen mit gemeinschaftlichen Punkten. Monaths. Math. und Physik 37, 281--302.
• 20: Klara Kedem , Ron Livne , János Pach , Micha Sharir, On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles, Discrete & Computational Geometry, v.1 n.1, p.59-71, 1986 [doi>10.1007/BF02187683]
• 21: Lovász, L., Pach, J., and Szegedy, M. 1997. On Conway&s thrackle conjecture. Disc. Comput. Geom. 18, 369--376.
• 22: Molnár, J. 1956. Über eine Verallgemeinerung auf die Kugelfläche eines topologischen Satzes von Helly. Acta Math. Acad. Sci. 7, 107--108. (Hungarian with German and Russian Summaries).
• 23: Pinchasi, R. 2001. Problems in combinatorial geometry in the plane. Ph.D. dissertation, Dept. Mathematics, Hebrew Univ.
• 24: Rom Pinchasi , Radoa Radoicic, Topological graphs with no self-intersecting cycle of length 4, Proceedings of the nineteenth annual symposium on Computational geometry, June 08-10, 2003, San Diego, California, USA [doi>10.1145/777792.777807]
• 25: Micha Sharir , Pankaj K. Agarwal, Davenport-Schinzel sequences and their geometric applications, Cambridge University Press, New York, NY, 1996
• 26: Snoeyink, J., and Hershberger, J. 1991. Sweeping arrangements of curves. In Discrete and Computational Geometry: Papers from the DIMACS Special Year. American Mathematical Society, Providence, R.I., 309--349.
• 27: Spencer, J., Szemerédi, E., and Trotter, W. T. 1984. Unit distances in the Euclidean plane. In Graph Theory and Combinatorics, B. Bollobás, Ed. Academic Press, New York, NY, 293--303.
• 28: László A. Székely, Crossing Numbers and Hard Erdös Problems in Discrete Geometry, Combinatorics, Probability and Computing, v.6 n.3, p.353-358, September 1997 [doi>10.1017/S0963548397002976]
• 29: Tamaki, H., and Tokuyama, T. 1998. How to cut pseudo-parabolas into segments. Disc. Comput. Geom. 19, 265--290.
• 30: Tardos, G. 2003. On distinct sums and distinct distances. Adv. Math., 180, 275--289.
• 31: Tutte, W. T. 1970. Toward a theory of crossing numbers. J. Combin. Theory 8, 45--53.

INDEX TERMS

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

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Geometric algorithms, languages, and systems

General Terms:
Algorithms, Theory

Keywords:
Arrangements, incidence problems, pseudo-circles