@article{4068,
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.},
author = {Herbert Edelsbrunner and Sharir, Micha},
journal = {Discrete & Computational Geometry},
number = {1},
pages = {35 -- 42},
publisher = {Springer},
title = {{The maximum number of ways to stabn convex nonintersecting sets in the plane is 2n−2}},
doi = { 10.1007/BF02187778},
volume = {5},
year = {1990},
}
@article{4069,
abstract = {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.},
author = {Herbert Edelsbrunner},
journal = {Combinatorica},
number = {3},
pages = {251 -- 260},
publisher = {Springer},
title = {{An acyclicity theorem for cell complexes in d dimension}},
doi = {10.1007/BF02122779},
volume = {10},
year = {1990},
}
@article{4070,
abstract = {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 = {Herbert Edelsbrunner and Overmars, Mark H and Welzl, Emo and Hartman, Irith Ben-Arroyo and Feldman,Jack A},
journal = {International Journal of Computer Mathematics},
number = {3-4},
pages = {129 -- 144},
publisher = {Taylor & Francis},
title = {{Ranking intervals under visibility constraints}},
doi = {10.1080/00207169008803871},
volume = {34},
year = {1990},
}
@inproceedings{4071,
abstract = {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 = {Herbert Edelsbrunner and Tan, Tiow Seng and Waupotitsch, Roman},
pages = {44 -- 52},
publisher = {ACM},
title = {{An O(n^2log n) time algorithm for the MinMax angle triangulation}},
doi = {10.1145/98524.98535},
year = {1990},
}
@article{4072,
abstract = {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).},
author = {Herbert Edelsbrunner and Guibas, Leonidas J and Sharir, Micha},
journal = {Discrete & Computational Geometry},
number = {1},
pages = {161 -- 196},
publisher = {Springer},
title = {{The complexity and construction of many faces in arrangements of lines and of segments}},
doi = { 10.1007/BF02187784},
volume = {5},
year = {1990},
}