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

H. Edelsbrunner, M. Sharir, Discrete & Computational Geometry 5 (1990) 35–42.

Download
No fulltext has been uploaded. References only!

Journal Article | Published
Author
Abstract
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
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/BF02187778
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. https://doi.org/ 10.1007/BF02187778
Edelsbrunner, Herbert, and Micha Sharir. “The Maximum Number of Ways to Stabn Convex Nonintersecting Sets in the Plane Is 2n−2.” Discrete & Computational Geometry 5, no. 1 (1990): 35–42. 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, pp. 35–42, 1990.
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.
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.

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar