TY - JOUR
AB - It is shown 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). The algorithm is fairly easy to implement and is based on the edge-insertion scheme that iteratively improves an arbitrary initial triangulation. It can be extended to the case where edges are prescribed, and, within the same time- and space-bounds, it can lexicographically minimize the sorted angle vector if the point set is in general position. Experimental results on the efficiency of the algorithm and the quality of the triangulations obtained are included.
AU - Herbert Edelsbrunner
AU - Tan, Tiow Seng
AU - Waupotitsch, Roman
ID - 4043
IS - 4
JF - SIAM Journal on Scientific Computing
TI - An O(n^2 log n) time algorithm for the MinMax angle triangulation
VL - 13
ER -
TY - JOUR
AB - The main contribution of this work is an O(n log n + k)-time algorithm for computing all k intersections among n line segments in the plane. This time complexity is easily shown to be optimal. Within the same asymptotic cost, our algorithm can also construct the subdivision of the plane defined by the segments and compute which segment (if any) lies right above (or below) each intersection and each endpoint. The algorithm has been implemented and performs very well. The storage requirement is on the order of n + k in the worst case, but it is considerably lower in practice. To analyze the complexity of the algorithm, an amortization argument based on a new combinatorial theorem on line arrangements is used.
AU - Chazelle, Bernard
AU - Herbert Edelsbrunner
ID - 4046
IS - 1
JF - Journal of the ACM
TI - An optimal algorithm for intersecting line segments in the plane
VL - 39
ER -
TY - JOUR
AB - Arrangements of curves in the plane are fundamental to many problems in computational and combinatorial geometry (e.g. motion planning, algebraic cell decomposition, etc.). In this paper we study various topological and combinatorial properties of such arrangements under some mild assumptions on the shape of the curves, and develop basic tools for the construction, manipulation, and analysis of these arrangements. Our main results include a generalization of the zone theorem of Edelsbrunner (1986) and Chazelle (1985) to arrangements of curves (in which we show that the combinatorial complexity of the zone of a curve is nearly linear in the number of curves) and an application of that theorem to obtain a nearly quadratic incremental algorithm for the construction of such arrangements.
AU - Herbert Edelsbrunner
AU - Guibas, Leonidas
AU - Pach, János
AU - Pollack, Richard
AU - Seidel, Raimund
AU - Sharir, Micha
ID - 4047
IS - 2
JF - Theoretical Computer Science
TI - Arrangements of curves in the plane - topology, combinatorics, and algorithms
VL - 92
ER -
TY - JOUR
AB - Given a sequence of n points that form the vertices of a simple polygon, we show that determining a closest pair requires OMEGA(n log n) time in the algebraic decision tree model. Together with the well-known O(n log n) upper bound for finding a closest pair, this settles an open problem of Lee and Preparata. We also extend this O(n log n) upper bound to the following problem: Given a collection of sets with a total of n points in the plane, find for each point a closest neighbor that does not belong to the same set.
AU - Aggarwal, Alok
AU - Herbert Edelsbrunner
AU - Raghavan, Prabhakar
AU - Tiwari, Prasoon
ID - 4048
IS - 1
JF - Information Processing Letters
TI - Optimal time bounds for some proximity problems in the plane
VL - 42
ER -
TY - CONF
AB - The edge-insertion paradigm improves a triangulation of a finite point set in R2
iteratively by adding a new edge, deleting intersecting old edges, and retriangulating
the resulting two polygonal regions. After presenting an abstract view of the paradigm,
this paper shows that it can be used to obtain polynomial time algorithms for several
types of optimal triangulations.
AU - Bern, Marshall
AU - Herbert Edelsbrunner
AU - Eppstein, David
AU - Mitchell, Stephen
AU - Tan, Tiow Seng
ID - 4049
TI - Edge insertion for optimal triangulations
VL - 583
ER -