On levels in arrangements of curves, iii: further improvements

ABSTRACT

We revisit the problem of bounding the combinatorial complexity of the k-level in a two-dimensional arrangement of n curves. We give a number of small improvements over the results from the author's previous paper (FOCS'03). For example:

1. For pseudo-parabolas, we obtain an upper bound of O(n^3/2 log n), which improves the previous bound of O(n^3/2 log² n).
2. For 3-intersecting curves, we obtain an upper bound of O(n^2-1/(3+√7))=O(n^1.823), the first improvement over the previous bound of O(n^11/6)=O(n^1.834).
3. For s-intersecting curves or curve segments with s ≥ 3, we obtain an upper bound of O(n^{2--1/2s--δ_s}) if s is odd, and O(n^{2--1/2(s--1)--δ_s}) if s is even, for some constant δ_s > 0.
4. For pseudo-segments, we obtain an upper bound of O(n^4/3 log^1/3--δ n) for some constant δ > 0. the previous bound was O(n^4/3 log ^2/3 n).
5. For s-intersecting curve segments such that all but B pairs intersect at most once, we obtain an upper bound of O((n^4/3 + n^1+δB^1/3--δ) log^1/3--δ n + B) for some constant δ > 0.

We also observe that better concrete bounds for k-levels for constant values of n could in principle lead to better asymptotic bounds for arbitrary n.

REFERENCES

• 1: P.K. Agarwal, B. Aronov, T.M. Chan, and M. Sharir. On levels in arrangements of lines, segments, planes, and triangles. Discrete Comput. Geom. 19:315--331, 1998.
• 2: Pankaj K. Agarwal , Boris Aronov , Micha Sharir, On levels in arrangements of lines, segments, planes, and triangles, Proceedings of the thirteenth annual symposium on Computational geometry, p.30-38, June 04-06, 1997, Nice, France [doi>10.1145/262839.262856]
• 3: 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]
• 4: B. Aronov and M. Sharir. Cutting circles into pseudo-segments and improved bounds for incidences and complexity of many faces. Discrete Comput. Geom. 28:475--490, 2002.
• 5: T.M. Chan. On levels in arrangements of curves. Discrete Comput. Geom. 29:375--393, 2003.
• 6: Timothy M. Chan, On Levels in Arrangements of Curves, II: A Simple Inequality and Its Consequences, Discrete & Computational Geometry, v.34 n.1, p.11-24, July 2005 [doi>10.1007/s00454-005-1165-3]
• 7: Timothy M. Chan, On levels in arrangements of surfaces in three dimensions, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 8: Timothy M. Chan, On the bichromatic k-set problem, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.561-570, January 20-22, 2008, San Francisco, California
• 9: K. L. Clarkson , P. W. Shor, Applications of random sampling in computational geometry, II, Discrete & Computational Geometry, v.4 n.5, p.387-421, 1989 [doi>10.1007/BF02187740]
• 10: T.K. Dey. Improved bounds on planar k-sets and related problems. Discrete Comput. Geom. 19:373--382, 1998.
• 11: H. Edelsbrunner and E. Welzl. On the number of line separations of a finite set in the plane. J. Combin. Theory Ser. A 38:15--29, 1985.
• 12: P. Erdös, L. Lovász, A. Simmons, and E. Straus. Dissection graphs of planar point sets. In A Survey of Combinatorial Theory (J.N. Srivastava, ed.), North-Holland, Amsterdam, Netherlands, pages 139--154, 1973.
• 13: D. Gusfield. Bounds for the parametric minimum spanning tree problem. In Proc. Humboldt Conf. on Graph Theory, Combinatorics, and Computing Utilitas Mathematica, pages 173--183, 1979.
• 14: L. Lovász. On the number of halving lines. Ann. Univ. Sci. Budapest, Eötvös, Sec. Math. 14:107--108, 1971.
• 15: Adam Marcus , Gábor Tardos, Intersection reverse sequences and geometric applications, Journal of Combinatorial Theory Series A, v.113 n.4, p.675-691, May 2006 [doi>10.1016/j.jcta.2005.07.002]
• 16: János Pach , William Steiger , Endre Szemerédi, An upper bound on the number of planar K-sets, Discrete & Computational Geometry, v.7 n.2, p.109-123, 1992 [doi>10.1007/BF02187829]
• 17: 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]
• 18: M. Sharir, S. Smorodinsky, and G. Tardos. An improved bound for k-sets in three dimensions. Discrete Comput. Geom.26: 195--204, 2001.
• 19: 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
• 20: H. Tamaki and T. Tokuyama. How to cut pseudoparabolas into segments. Discrete Comput. Geom. 19:265--290, 1998.
• 21: G. Tóth. Point sets with many k-sets. Discrete Comput. Geom. 26:187--194, 2001.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics

General Terms:
Theory

Keywords:
arrangements, combinatorial geometry, k-levels, k-sets