TY - JOUR
AB - 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.
AU - Herbert Edelsbrunner
AU - Sharir, Micha
ID - 4068
IS - 1
JF - Discrete & Computational Geometry
TI - The maximum number of ways to stabn convex nonintersecting sets in the plane is 2n−2
VL - 5
ER -
TY - JOUR
AB - 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.
AU - Herbert Edelsbrunner
ID - 4069
IS - 3
JF - Combinatorica
TI - An acyclicity theorem for cell complexes in d dimension
VL - 10
ER -
TY - JOUR
AB - 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.
AU - Herbert Edelsbrunner
AU - Overmars, Mark H
AU - Welzl, Emo
AU - Hartman, Irith Ben-Arroyo
AU - Feldman,Jack A
ID - 4070
IS - 3-4
JF - International Journal of Computer Mathematics
TI - Ranking intervals under visibility constraints
VL - 34
ER -
TY - CONF
AB - 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.
AU - Herbert Edelsbrunner
AU - Tan, Tiow Seng
AU - Waupotitsch, Roman
ID - 4071
TI - An O(n^2log n) time algorithm for the MinMax angle triangulation
ER -
TY - JOUR
AB - 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).
AU - Herbert Edelsbrunner
AU - Guibas, Leonidas J
AU - Sharir, Micha
ID - 4072
IS - 1
JF - Discrete & Computational Geometry
TI - The complexity and construction of many faces in arrangements of lines and of segments
VL - 5
ER -
TY - CONF
AB - A number of rendering algorithms in computer graphics sort three-dimensional objects by depth and assume that there is no cycle that makes the sorting impossible. One way to resolve the problem caused by cycles is to cut the objects into smaller pieces. The problem of estimating how many such cuts are always sufficient is addressed. A few related algorithmic and combinatorial geometry problems are considered
AU - Chazelle, Bernard
AU - Herbert Edelsbrunner
AU - Guibas, Leonidas J
AU - Pollack, Richard
AU - Seidel, Raimund
AU - Sharir, Micha
AU - Snoeyink, Jack
ID - 4073
TI - Counting and cutting cycles of lines and rods in space
ER -
TY - JOUR
AU - Clarkson, Kenneth L
AU - Herbert Edelsbrunner
AU - Guibas, Leonidas J
AU - Sharir, Micha
AU - Welzl, Emo
ID - 4074
IS - 1
JF - Discrete & Computational Geometry
TI - Combinatorial complexity bounds for arrangements of curves and spheres
VL - 5
ER -
TY - JOUR
AB - A key problem in computational geometry is the identification of subsets of a point set having particular properties. We study this problem for the properties of convexity and emptiness. We show that finding empty triangles is related to the problem of determining pairs of vertices that see each other in a star-shaped polygon. A linear-time algorithm for this problem which is of independent interest yields an optimal algorithm for finding all empty triangles. This result is then extended to an algorithm for finding empty convex r-gons (r> 3) and for determining a largest empty convex subset. Finally, extensions to higher dimensions are mentioned.
AU - Dobkin, David P
AU - Herbert Edelsbrunner
AU - Overmars, Mark H
ID - 4075
IS - 4
JF - Algorithmica
TI - Searching for empty convex polygons
VL - 5
ER -
TY - CONF
AB - We present an algorithm to compute a Euclidean minimum spanning tree of a given set S of n points in Ed in time O(Td(N, N) logd N), where Td(n, m) is the time required to compute a bichromatic closest pair among n red and m blue points in Ed. If Td(N, N) = Ω(N1+ε), for some fixed ε > 0, then the running time improves to O(Td(N, N)). Furthermore, we describe a randomized algorithm to compute a bichromatic closets pair in expected time O((nm log n log m)2/3+m log2 n + n log2 m) in E3, which yields an O(N4/3log4/3 N) expected time algorithm for computing a Euclidean minimum spanning tree of N points in E3.
AU - Agarwal, Pankaj K
AU - Herbert Edelsbrunner
AU - Schwarzkopf, Otfried
AU - Welzl, Emo
ID - 4076
TI - Euclidean minimum spanning trees and bichromatic closest pairs
ER -
TY - CONF
AB - We prove that for any set S of n points in the plane and n3-α triangles spanned by the points of S there exists a point (not necessarily of S) contained in at least n3-3α/(512 log25 n) of the triangles. This implies that any set of n points in three - dimensional space defines at most 6.4n8/3 log5/3 n halving planes.
AU - Aronov, Boris
AU - Chazelle, Bernard
AU - Herbert Edelsbrunner
AU - Guibas, Leonidas J
AU - Sharir, Micha
AU - Wenger, Rephael
ID - 4077
TI - Points and triangles in the plane and halving planes in space
ER -