TY - JOUR
AU - Herbert Edelsbrunner
AU - van Leeuwen,Jan
AU - Ottmann,Thomas
AU - Wood, Derick
ID - 4117
IS - 2
JF - Rairo-Informatique Theorique Et Applications-Theoretical Informatics and Applications
TI - Computing the connected components of simple rectilinear geometrical objects in D-Space
VL - 18
ER -
TY - JOUR
AB - A rectilinear polygon can be viewed as an art gallery room whose walls meet at right angles. An algorithm is presented that stations guards in such a room so that every interior point is visible to some guard. The algorithm partitions the polygon into L-shaped pieces, a subclass of star-shaped pieces, and locates one guard within each kernel. The algorithm runs in O(n log n) time in the worst case for a polygon of n vertices.
AU - Herbert Edelsbrunner
AU - O'Rourke, Joseph
AU - Welzl, Emo
ID - 4118
IS - 2
JF - Computer Vision, Graphics, and Image Processing
TI - Stationing guards in rectilinear art galleries
VL - 27
ER -
TY - CONF
AU - Herbert Edelsbrunner
AU - Welzl, Emo
ID - 4119
TI - Monotone edge sequences in line arrangements and applications
VL - 176
ER -
TY - JOUR
AB - Whenevern objects are characterized by a matrix of pairwise dissimilarities, they may be clustered by any of a number of sequential, agglomerative, hierarchical, nonoverlapping (SAHN) clustering methods. These SAHN clustering methods are defined by a paradigmatic algorithm that usually requires 0(n 3) time, in the worst case, to cluster the objects. An improved algorithm (Anderberg 1973), while still requiring 0(n 3) worst-case time, can reasonably be expected to exhibit 0(n 2) expected behavior. By contrast, we describe a SAHN clustering algorithm that requires 0(n 2 logn) time in the worst case. When SAHN clustering methods exhibit reasonable space distortion properties, further improvements are possible. We adapt a SAHN clustering algorithm, based on the efficient construction of nearest neighbor chains, to obtain a reasonably general SAHN clustering algorithm that requires in the worst case 0(n 2) time and space.
Whenevern objects are characterized byk-tuples of real numbers, they may be clustered by any of a family of centroid SAHN clustering methods. These methods are based on a geometric model in which clusters are represented by points ink-dimensional real space and points being agglomerated are replaced by a single (centroid) point. For this model, we have solved a class of special packing problems involving point-symmetric convex objects and have exploited it to design an efficient centroid clustering algorithm. Specifically, we describe a centroid SAHN clustering algorithm that requires 0(n 2) time, in the worst case, for fixedk and for a family of dissimilarity measures including the Manhattan, Euclidean, Chebychev and all other Minkowski metrics.
AU - Day,William H
AU - Herbert Edelsbrunner
ID - 4121
IS - 1
JF - Journal of Classification
TI - Efficient algorithms for agglomerative hierarchical clustering methods
VL - 1
ER -
TY - CONF
AB - Computational geometry, considered a subfield of computer science, is concerned with the computational aspects of geometric problems. The increasing activity in this rather young field made it split into several reasonably independent subareas. This paper presents several key-problems of the classical part of computational geometry which exhibit strong interrelations. A unified view of the problems is stressed, and the general ideas behind the methods that solve them are worked out.
AU - Herbert Edelsbrunner
ID - 4122
TI - Key-problems and key-methods in computational geometry
VL - 166
ER -
TY - JOUR
AB - Windowing a two-dimensional picture means to determine those line segments of the picture that are visible through an axis-parallel window. A study of some algorithmic problems involved in windowing a picture is offered. Some methods from computational geometry are exploited to store the picture in a computer such that (1) those line segments inside or partially inside of a window can be determined efficiently, and (2) the set of those line segments can be maintained efficiently while the window is moved parallel to a coordinate axis and/or it is enlarged or reduced.
AU - Herbert Edelsbrunner
AU - Overmars, Mark H
AU - Seidel, Raimund
ID - 4123
IS - 1
JF - Computer Vision, Graphics, and Image Processing
TI - Some methods of computational geometry applied to computer graphics
VL - 28
ER -
TY - JOUR
AB - Let S denote a set of n points in the plane such that each point p has assigned a positive weight w(p) which expresses its capability to influence its neighbourhood. In this sense, the weighted distance of an arbitrary point x from p is given by de(x,p)/w(p) where de denotes the Euclidean distance function. The weighted Voronoi diagram for S is a subdivision of the plane such that each point p in S is associated with a region consisting of all points x in the plane for which p is a weighted nearest point of S.
An algorithm which constructs the weighted Voronoi diagram for S in O(n2) time is outlined in this paper. The method is optimal as the diagram can consist of Θ(n2) faces, edges and vertices.
AU - Aurenhammer,Franz
AU - Herbert Edelsbrunner
ID - 4125
IS - 2
JF - Pattern Recognition
TI - An optimal algorithm for constructing the weighted Voronoi diagram in the plane
VL - 17
ER -
TY - JOUR
AU - Nicholas Barton
AU - Charlesworth, Brian
ID - 4327
JF - Annual Review of Ecology and Systematics
TI - Genetic revolutions, founder effects, and speciation
VL - 15
ER -
TY - CONF
AU - Dobkin, David P
AU - Herbert Edelsbrunner
ID - 3513
TI - Ham-sandwich theorems applied to intersection problems
ER -