On levels in arrangements of surfaces in three dimensions

ABSTRACT

A favorite open problem in combinatorial geometry is to determine the worst-case complexity of a level in an arrangement. Up to now, nontrivial upper bounds in three dimensions are known only for the linear cases of planes and triangles. We propose the first technique that can deal with more general surfaces in three dimensions. For example, in an arrangement of n "pseudo-planes" or "pseudo-spheres" (where each triple of surfaces has at most two common intersections), we prove that there are at most O(n^2.9986) vertices of any given level.

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 , 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]
• 3: Boris Aronov , Bernard Chazelle , Herbert Edelsbrunner , Leonidas J. Guibas , Micha Sharir , Rephael Wenger, Points and triangles in the plane and halving planes in space, Discrete & Computational Geometry, v.6 n.5, p.435-442, 1991 [doi>10.1007/BF02574700]
• 4: I. Bárány, Z. Füredi, and L. Lovász. On the number of halving planes. Combinatorica, 10:175--183, 1990.
• 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, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.544, October 11-14, 2003
• 7: T. K. Dey. Improved bounds on planar k-sets and related problems. Discrete Comput. Geom., 19:373--382, 1998.
• 8: T. K. Dey and H. Edelsbrunner. Counting triangle crossings and halving planes. Discrete Comput. Geom., 12:281--289, 1994.
• 9: Herbert Edelsbrunner, Algorithms in combinatorial geometry, Springer-Verlag New York, Inc., New York, NY, 1987
• 10: David Eppstein, Improved bounds for intersecting triangles and halving planes, Journal of Combinatorial Theory Series A, v.62 n.1, p.176-182, Jan. 1993 [doi>10.1016/0097-3165(93)90082-J]
• 11: 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.
• 12: N. Katoh and T. Tokuyama. Lovász's lemma for the three-dimensional k-level of concave surfaces and its applications. Discrete Comput. Geom., 27:567--584, 2002.
• 13: L. Lovász. On the number of halving lines. Ann. Univ. Sci. Budapest, Eötvös, Sec. Math., 14:107--108, 1971.
• 14: A. Marcus and G. Tardos. Intersection reverse sequences and geometric applications. To appear in Proc. 12th Int. Sympos. Graph Drawing, 2004.
• 15: Jiri Matousek, Lectures on Discrete Geometry, Springer-Verlag New York, Inc., Secaucus, NJ, 2002
• 16: J. Matoušek, M. Sharir, S. Smorodinsky, and U. Wagner. On k-sets in four dimensions. Manuscript, 2004.
• 17: J. Pach and P. K. Agarwal. Combinatorial Geometry. Wiley-Interscience, New York, 1995.
• 18: Micha Sharir , Pankaj K. Agarwal, Davenport-Schinzel sequences and their geometric applications, Cambridge University Press, New York, NY, 1996
• 19: M. Sharir, S. Smorodinsky, and G. Tardos. An improved bound for k-sets in three dimensions. Discrete Comput. Geom., 26:195--204, 2001.
• 20: 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
• 21: H. Tamaki and T. Tokuyama. How to cut pseudoparabolas into segments. Discrete Comput. Geom., 19:265--290, 1998.
• 22: G. Tóth. Point sets with many k-sets. Discrete Comput. Geom., 26:187--194, 2001.
• 23: Rade T. Živaljevic , Sinša T. Vrecica, The colored Tverberg's problem and complexes of injective functions, Journal of Combinatorial Theory Series A, v.61 n.2, p.309-318, Nov. 1992 [doi>10.1016/0097-3165(92)90028-S]