---
_id: '4068'
abstract:
- lang: eng
text: "LetS be a collection ofn convex, closed, and pairwise nonintersecting sets
in the Euclidean plane labeled from 1 ton. A pair of permutations\r\n(i1i2in−1in)(inin−1i2i1)
\r\nis 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."
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.
article_processing_charge: No
article_type: original
author:
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
- first_name: Micha
full_name: Sharir, Micha
last_name: Sharir
citation:
ama: 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
apa: Edelsbrunner, 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/BF02187778
chicago: Edelsbrunner, 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.
ieee: 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.
ista: 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.
mla: 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.
short: H. Edelsbrunner, M. Sharir, Discrete & Computational Geometry 5 (1990)
35–42.
date_created: 2018-12-11T12:06:45Z
date_published: 1990-01-01T00:00:00Z
date_updated: 2022-02-22T14:50:34Z
day: '01'
doi: 10.1007/BF02187778
extern: '1'
intvolume: ' 5'
issue: '1'
language:
- iso: eng
main_file_link:
- url: https://link.springer.com/article/10.1007/BF02187778
month: '01'
oa_version: None
page: 35 - 42
publication: Discrete & Computational Geometry
publication_identifier:
eissn:
- 1432-0444
issn:
- 0179-5376
publication_status: published
publisher: Springer
publist_id: '2057'
quality_controlled: '1'
status: public
title: The maximum number of ways to stabn convex nonintersecting sets in the plane
is 2n−2
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 5
year: '1990'
...