---
_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\n(i1i2in−1in)(inin−1i2i1)
\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.
author:
- first_name: Herbert
full_name: Herbert Edelsbrunner
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: 2021-01-12T07:54:16Z
day: '01'
doi: ' 10.1007/BF02187778'
extern: 1
intvolume: ' 5'
issue: '1'
month: '01'
page: 35 - 42
publication: Discrete & Computational Geometry
publication_status: published
publisher: Springer
publist_id: '2057'
quality_controlled: 0
status: public
title: The maximum number of ways to stabn convex nonintersecting sets in the plane
is 2n−2
type: journal_article
volume: 5
year: '1990'
...
---
_id: '4069'
abstract:
- lang: eng
text: Let C be a cell complex in d-dimensional Euclidean space whose faces are obtained
by orthogonal projection of the faces of a convex polytope in d + 1 dimensions.
For example, the Delaunay triangulation of a finite point set is such a cell complex.
This paper shows that the in front/behind relation defined for the faces of C
with respect to any fixed viewpoint x is acyclic. This result has applications
to hidden line/surface removal and other problems in computational geometry.
acknowledgement: Research reported in this paper was supported by the National Science
Foundation under grant CCR-8714565
author:
- first_name: Herbert
full_name: Herbert Edelsbrunner
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
citation:
ama: Edelsbrunner H. An acyclicity theorem for cell complexes in d dimension. *Combinatorica*.
1990;10(3):251-260. doi:10.1007/BF02122779
apa: Edelsbrunner, H. (1990). An acyclicity theorem for cell complexes in d dimension.
*Combinatorica*. Springer. https://doi.org/10.1007/BF02122779
chicago: Edelsbrunner, Herbert. “An Acyclicity Theorem for Cell Complexes in d Dimension.”
*Combinatorica*. Springer, 1990. https://doi.org/10.1007/BF02122779.
ieee: H. Edelsbrunner, “An acyclicity theorem for cell complexes in d dimension,”
*Combinatorica*, vol. 10, no. 3. Springer, pp. 251–260, 1990.
ista: Edelsbrunner H. 1990. An acyclicity theorem for cell complexes in d dimension.
Combinatorica. 10(3), 251–260.
mla: Edelsbrunner, Herbert. “An Acyclicity Theorem for Cell Complexes in d Dimension.”
*Combinatorica*, vol. 10, no. 3, Springer, 1990, pp. 251–60, doi:10.1007/BF02122779.
short: H. Edelsbrunner, Combinatorica 10 (1990) 251–260.
date_created: 2018-12-11T12:06:45Z
date_published: 1990-01-01T00:00:00Z
date_updated: 2021-01-12T07:54:16Z
day: '01'
doi: 10.1007/BF02122779
extern: 1
intvolume: ' 10'
issue: '3'
month: '01'
page: 251 - 260
publication: Combinatorica
publication_status: published
publisher: Springer
publist_id: '2050'
quality_controlled: 0
status: public
title: An acyclicity theorem for cell complexes in d dimension
type: journal_article
volume: 10
year: '1990'
...
---
_id: '4070'
abstract:
- lang: eng
text: Let S be a set of n closed intervals on the x-axis. A ranking assigns to each
interval, s, a distinct rank, p(s) [1, 2,…,n]. We say that s can see t if p(s)<p(t)
and there is a point ps∩t so that pu for all u with p(s)<p(u)<p(t). It is
shown that a ranking can be found in time O(n log n) such that each interval sees
at most three other intervals. It is also shown that a ranking that minimizes
the average number of endpoints visible from an interval can be computed in time
O(n 5/2). The results have applications to intersection problems for intervals,
as well as to channel routing problems which arise in layouts of VLSI circuits.
author:
- first_name: Herbert
full_name: Herbert Edelsbrunner
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
- first_name: Mark
full_name: Overmars, Mark H
last_name: Overmars
- first_name: Emo
full_name: Welzl, Emo
last_name: Welzl
- first_name: Irith
full_name: Hartman, Irith Ben-Arroyo
last_name: Hartman
- first_name: Jack
full_name: Feldman,Jack A
last_name: Feldman
citation:
ama: Edelsbrunner H, Overmars M, Welzl E, Hartman I, Feldman J. Ranking intervals
under visibility constraints. *International Journal of Computer Mathematics*.
1990;34(3-4):129-144. doi:10.1080/00207169008803871
apa: Edelsbrunner, H., Overmars, M., Welzl, E., Hartman, I., & Feldman, J. (1990).
Ranking intervals under visibility constraints. *International Journal of Computer
Mathematics*. Taylor & Francis. https://doi.org/10.1080/00207169008803871
chicago: Edelsbrunner, Herbert, Mark Overmars, Emo Welzl, Irith Hartman, and Jack
Feldman. “Ranking Intervals under Visibility Constraints.” *International Journal
of Computer Mathematics*. Taylor & Francis, 1990. https://doi.org/10.1080/00207169008803871.
ieee: H. Edelsbrunner, M. Overmars, E. Welzl, I. Hartman, and J. Feldman, “Ranking
intervals under visibility constraints,” *International Journal of Computer
Mathematics*, vol. 34, no. 3–4. Taylor & Francis, pp. 129–144, 1990.
ista: Edelsbrunner H, Overmars M, Welzl E, Hartman I, Feldman J. 1990. Ranking intervals
under visibility constraints. International Journal of Computer Mathematics. 34(3–4),
129–144.
mla: Edelsbrunner, Herbert, et al. “Ranking Intervals under Visibility Constraints.”
*International Journal of Computer Mathematics*, vol. 34, no. 3–4, Taylor
& Francis, 1990, pp. 129–44, doi:10.1080/00207169008803871.
short: H. Edelsbrunner, M. Overmars, E. Welzl, I. Hartman, J. Feldman, International
Journal of Computer Mathematics 34 (1990) 129–144.
date_created: 2018-12-11T12:06:46Z
date_published: 1990-01-01T00:00:00Z
date_updated: 2021-01-12T07:54:17Z
day: '01'
doi: 10.1080/00207169008803871
extern: 1
intvolume: ' 34'
issue: 3-4
month: '01'
page: 129 - 144
publication: International Journal of Computer Mathematics
publication_status: published
publisher: Taylor & Francis
publist_id: '2051'
quality_controlled: 0
status: public
title: Ranking intervals under visibility constraints
type: journal_article
volume: 34
year: '1990'
...
---
_id: '4071'
abstract:
- lang: eng
text: We show that a triangulation of a set of n points in the plane that minimizes
the maximum angle can be computed in time O(n2 log n) and space O(n). In the same
amount of time and space we can also handle the constrained case where edges are
prescribed. The algorithm iteratively improves an arbitrary initial triangulation
and is fairly easy to implement.
author:
- first_name: Herbert
full_name: Herbert Edelsbrunner
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
- first_name: Tiow
full_name: Tan, Tiow Seng
last_name: Tan
- first_name: Roman
full_name: Waupotitsch, Roman
last_name: Waupotitsch
citation:
ama: 'Edelsbrunner H, Tan T, Waupotitsch R. An O(n^2log n) time algorithm for the
MinMax angle triangulation. In: ACM; 1990:44-52. doi:10.1145/98524.98535'
apa: 'Edelsbrunner, H., Tan, T., & Waupotitsch, R. (1990). An O(n^2log n) time
algorithm for the MinMax angle triangulation (pp. 44–52). Presented at the SCG:
Symposium on Computational Geometry, ACM. https://doi.org/10.1145/98524.98535'
chicago: Edelsbrunner, Herbert, Tiow Tan, and Roman Waupotitsch. “An O(N^2log n)
Time Algorithm for the MinMax Angle Triangulation,” 44–52. ACM, 1990. https://doi.org/10.1145/98524.98535.
ieee: 'H. Edelsbrunner, T. Tan, and R. Waupotitsch, “An O(n^2log n) time algorithm
for the MinMax angle triangulation,” presented at the SCG: Symposium on Computational
Geometry, 1990, pp. 44–52.'
ista: 'Edelsbrunner H, Tan T, Waupotitsch R. 1990. An O(n^2log n) time algorithm
for the MinMax angle triangulation. SCG: Symposium on Computational Geometry,
44–52.'
mla: Edelsbrunner, Herbert, et al. *An O(N^2log n) Time Algorithm for the MinMax
Angle Triangulation*. ACM, 1990, pp. 44–52, doi:10.1145/98524.98535.
short: H. Edelsbrunner, T. Tan, R. Waupotitsch, in:, ACM, 1990, pp. 44–52.
conference:
name: 'SCG: Symposium on Computational Geometry'
date_created: 2018-12-11T12:06:46Z
date_published: 1990-01-01T00:00:00Z
date_updated: 2021-01-12T07:54:18Z
day: '01'
doi: 10.1145/98524.98535
extern: 1
month: '01'
page: 44 - 52
publication_status: published
publisher: ACM
publist_id: '2052'
quality_controlled: 0
status: public
title: An O(n^2log n) time algorithm for the MinMax angle triangulation
type: conference
year: '1990'
...
---
_id: '4072'
abstract:
- lang: eng
text: We show that the total number of edges ofm faces of an arrangement ofn lines
in the plane isO(m 2/3– n 2/3+2 +n) for any>0. The proof takes an algorithmic
approach, that is, we describe an algorithm for the calculation of thesem faces
and derive the upper bound from the analysis of the algorithm. The algorithm uses
randomization and its expected time complexity isO(m 2/3– n 2/3+2 logn+n logn
logm). If instead of lines we have an arrangement ofn line segments, then the
maximum number of edges ofm faces isO(m 2/3– n 2/3+2 +n (n) logm) for any>0,
where(n) is the functional inverse of Ackermann's function. We give a (randomized)
algorithm that produces these faces and takes expected timeO(m 2/3– n 2/3+2 log+n(n)
log2 n logm).
acknowledgement: The first author is pleased to acknowledge partial support by the
Amoco Fnd. Fac. Dev. Comput. Sci. 1-6-44862 and the National Science Foundation
under Grant CCR-8714565. Work on this paper by the third author has been supported
by Office of Naval Research Grant N00014-82-K-0381, by National Science Foundation
Grant DCR-83-20085, by grants from the Digital Equipment Corporation, and the IBM
Corporation, and by a research grant from the NCRD-the Israeli National Council
for Research and Development. A preliminary version of this paper has appeared in
theProceedings of the 4th ACM Symposium on Computational Geometry, 1988, pp. 44–55.
author:
- first_name: Herbert
full_name: Herbert Edelsbrunner
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
- first_name: Leonidas
full_name: Guibas, Leonidas J
last_name: Guibas
- first_name: Micha
full_name: Sharir, Micha
last_name: Sharir
citation:
ama: Edelsbrunner H, Guibas L, Sharir M. The complexity and construction of many
faces in arrangements of lines and of segments. *Discrete & Computational
Geometry*. 1990;5(1):161-196. doi:
10.1007/BF02187784
apa: Edelsbrunner, H., Guibas, L., & Sharir, M. (1990). The complexity and construction
of many faces in arrangements of lines and of segments. *Discrete & Computational
Geometry*. Springer. https://doi.org/
10.1007/BF02187784
chicago: Edelsbrunner, Herbert, Leonidas Guibas, and Micha Sharir. “The Complexity
and Construction of Many Faces in Arrangements of Lines and of Segments.” *Discrete
& Computational Geometry*. Springer, 1990. https://doi.org/
10.1007/BF02187784.
ieee: H. Edelsbrunner, L. Guibas, and M. Sharir, “The complexity and construction
of many faces in arrangements of lines and of segments,” *Discrete & Computational
Geometry*, vol. 5, no. 1. Springer, pp. 161–196, 1990.
ista: Edelsbrunner H, Guibas L, Sharir M. 1990. The complexity and construction
of many faces in arrangements of lines and of segments. Discrete & Computational
Geometry. 5(1), 161–196.
mla: Edelsbrunner, Herbert, et al. “The Complexity and Construction of Many Faces
in Arrangements of Lines and of Segments.” *Discrete & Computational Geometry*,
vol. 5, no. 1, Springer, 1990, pp. 161–96, doi:
10.1007/BF02187784.
short: H. Edelsbrunner, L. Guibas, M. Sharir, Discrete & Computational Geometry
5 (1990) 161–196.
date_created: 2018-12-11T12:06:46Z
date_published: 1990-01-01T00:00:00Z
date_updated: 2021-01-12T07:54:18Z
day: '01'
doi: ' 10.1007/BF02187784'
extern: 1
intvolume: ' 5'
issue: '1'
month: '01'
page: 161 - 196
publication: Discrete & Computational Geometry
publication_status: published
publisher: Springer
publist_id: '2053'
quality_controlled: 0
status: public
title: The complexity and construction of many faces in arrangements of lines and
of segments
type: journal_article
volume: 5
year: '1990'
...