Abstract
LetS be a collection ofn convex, closed, and pairwise nonintersecting sets in the Euclidean plane labeled from 1 ton. A pair of permutations
is called ageometric permutation of S if there is a line that intersects all sets ofS in this order. We prove thatS can realize at most 2n−2 geometric permutations. This upper bound is tight.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Atallah, M. Some dynamic computational geometry problems.Comput. Math. Appl. 11 (1985), 1171–1181.
Atallah, M. and Bajaj, Ch. Efficient algorithms for common transversals.Inform. Process. Lett. 25 (1987), 87–91.
Edelsbrunner, H., Maurer, H. A., Preparata, F. P., Rosenberg, A. L., Welzl, E., and Wood, D. Stabbing line segments.BIT 22 (1982), 274–281.
Hart, S. and Sharir, M. Nonlinearity of Davenport-Schinzel sequences and of a generalized path compression scheme.Combinatorica 6 (1986), 151–177.
Katchalski, M., Lewis, T., and Liu, A. Geometric permutations and common transversals.Discrete Comput. Geom. 1 (1986), 371–377.
Katchalski, M., Lewis, T., and Zaks, J. Geometric permutations for convex sets.Discrete Math. 54 (1985), 271–284.
Sharir, M. Almost linear upper bounds on the length of general Davenport-Schinzel sequences.Combinatorica 7 (1987), 131–143.
Sharir, M. Improved lower bounds on the length of Davenport-Schinzel sequences. To appear inCombinatorica and also available as Report 204, Courant Institute of Mathematical Sciences, New York University, New York, 1986.
Wenger, R. Upper bounds on linear orderings. Report TR-SOCS-89.19, School of Computer Science, McGill University, Montreal, Quebec, 1986.
Author information
Authors and Affiliations
Additional information
Research of the first author was supported by Amoco Foundation for Faculty Development in Computer Science Grant No. 1-6-44862. Work on this paper by the second author was supported by Office of Naval Research Grant No. N00014-82-K-0381, National Science Foundation Grant No. NSF-DCR-83-20085, and by grants from the Digital Equipment Corporation and the IBM Corporation.
Rights and permissions
About this article
Cite this article
Edelsbrunner, H., Sharir, M. The maximum number of ways to stabn convex nonintersecting sets in the plane is 2n−2. Discrete Comput Geom 5, 35–42 (1990). https://doi.org/10.1007/BF02187778
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/BF02187778