# The maximum number of ways to stabn convex nonintersecting sets in the plane is 2n−2

Edelsbrunner H, Sharir M. 1990. The maximum number of ways to stabn convex nonintersecting sets in the plane is 2n−2. Discrete & Computational Geometry. 5(1), 35–42.

Download

**No fulltext has been uploaded. References only!**

*Journal Article*|

*Published*|

*English*

Author

Edelsbrunner, Herbert

^{ISTA}^{}; Sharir, MichaAbstract

LetS be a collection ofn convex, closed, and pairwise nonintersecting sets in the Euclidean plane labeled from 1 ton. A pair of permutations
(i1i2in−1in)(inin−1i2i1)
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.

Publishing Year

Date Published

1990-01-01

Journal Title

Discrete & Computational Geometry

Acknowledgement

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.

Volume

5

Issue

1

Page

35 - 42

ISSN

eISSN

IST-REx-ID

### Cite this

Edelsbrunner H, Sharir M. The maximum number of ways to stabn convex nonintersecting sets in the plane is 2n−2.

*Discrete & Computational Geometry*. 1990;5(1):35-42. doi:10.1007/BF02187778Edelsbrunner, H., & Sharir, M. (1990). The maximum number of ways to stabn convex nonintersecting sets in the plane is 2n−2.

*Discrete & Computational Geometry*. Springer. https://doi.org/10.1007/BF02187778Edelsbrunner, Herbert, and Micha Sharir. “The Maximum Number of Ways to Stabn Convex Nonintersecting Sets in the Plane Is 2n−2.”

*Discrete & Computational Geometry*. Springer, 1990. https://doi.org/10.1007/BF02187778.H. Edelsbrunner and M. Sharir, “The maximum number of ways to stabn convex nonintersecting sets in the plane is 2n−2,”

*Discrete & Computational Geometry*, vol. 5, no. 1. Springer, pp. 35–42, 1990.Edelsbrunner, Herbert, and Micha Sharir. “The Maximum Number of Ways to Stabn Convex Nonintersecting Sets in the Plane Is 2n−2.”

*Discrete & Computational Geometry*, vol. 5, no. 1, Springer, 1990, pp. 35–42, doi:10.1007/BF02187778.**Link(s) to Main File(s)**

Access Level

Closed Access