On the Shape of a Set of Points in the Plane (2009)
L I. Gurantz, S. Blake, E. Hoversten, J. Petranovich, A High, Herbert Edelsbrunner, ...
The authors express their appreciation for numerous constructive suggestions, which led to improvements on various phases of the manuscript, to Dr. Marvin Simon of JPL and to Professor George L....
Quantifying Transversality by Measuring the Robustness of Intersections (2009)
Edelsbrunner, Herbert, Morozov, Dmitriy, Patel, Amit
By definition, transverse intersections are stable under infinitesimal perturbations. Using persistent homology, we extend this notion to sizeable perturbations. Specifically, we assign to each...
Abstract Extreme Elevation on a 2-Manifold (2009)
Pankaj K. Agarwal, Herbert Edelsbrunner, John Harer
Given a smoothly embedded 2-manifold in ¤¦ ¥ , we define the elevation of a point as the height difference to a canonically defined second point on the same manifold. Our definition is invariant...
Abstract Morse Complexes for Piecewise Linear 3-Manifolds (2009)
Herbert Edelsbrunner, John Harer, Vijay Natarajan, Valerio Pascucci
We define the Morse complex of a Morse function over a 3manifold as the overlay of the stable and unstable manifolds of all critical points. In the generic case, its 3-dimensional cells are shaped...
Robert Bryant, Herbert Edelsbrunner, Patrice Koehl, Michael Levitt
Abstract. The motion of a biomolecule greatly depends on the engulfing solution, which is mostly water. Instead of representing individual water molecules, it is desirable to develop implicit solvent...
Running title Accurate Protein Docking by Shape Complementarity Alone (2009)
Sergei Bespamyatnikh, Vicky Choi, Herbert Edelsbrunner, Johannes Rudolph, North Carolina
Number of pages: 25 Number of tables: 2 Number of figures: 5 Submitted as pdf-file. No supplementary material.
Abstract Surface Reconstruction by Wrapping Finite Sets in Space (2008)
Given a finite point set in ¡£¢, the surface reconstruction problem asks for a surface that passes through many but not necessarily all points. We describe an unambiguous definition of such a...
Abstract Dynamic Skin Triangulation ∗ (2008)
Ho-lun Cheng, Tamal K. Dey, Herbert Edelsbrunner, John Sullivan
This paper describes an algorithm for maintaining an approximating triangulation of a deforming surface in R 3. The surface is the envelope of an infinite family of spheres defined and controlled by...
ABSTRACT Persistence-Sensitive Simplification of Functions on 2-Manifolds ∗ (2008)
We continue the study of topological persistence [5] by investigating the problem of simplifying a function f in a way that removes topological noise as determined by its persistence diagram [2]. To...
Abstract An Incremental Algorithm for Betti Numbers of Simplicial Complexes* (2008)
Cecil Jose, A. Delfinado, Herbert Edelsbrunner
A general and direct method for computing the betti numbers of the homology groups of a finite simplicial complez is given. For subcomplexes of a triangulation of S3 this method has implementations...
Stability and computation of medial axes – a state-of-the-art report (2008)
Dominique Attali, Jean-daniel Boissonnat, Herbert Edelsbrunner
Summary. The medial axis of a geometric shape captures its connectivity. In spite of its inherent instability, it has found applications in a number of areas that deal with shapes. In this survey...
Abstract Design and Analysis of Planar Shape Deformation (2008)
Siu-wing Cheng, Herbert Edelsbrunner, Ping Fu, Ka-po Lam
Shape deformation refers to the continuous change of one geometric object to another. We develop a software tool for planning, analyzing, and visualizing deformations between two shapes in ¤¦ ¥....
Abstract Relaxed Scheduling in Dynamic Skin Triangulation (2008)
We introduce relaxed scheduling as a paradigm for mesh maintenance and demonstrate its applicability to triangulating a skin surface in £¥ ¤.
Bernard Chazelle, Herbert Edelsbrunner, Leonidas J. Guibas, Micha Sharir
A singly exponential stratification scheme for real semi-algebraic varieties and its applications*
Stability and computation of medial axes – a state-of-the-art report (2008)
Dominique Attali, Jean-daniel Boissonnat, Herbert Edelsbrunner
Summary. The medial axis of a geometric shape captures its connectivity. In spite of its inherent instability, it has found applications in a number of areas that deal with shapes. In this survey...
University of Pennsylvania (2008)
Leonidas J. Guibas, Herbert Edelsbrunner, Jeff Erickson, Michael Isard, John Hershberger, Christian Jensen, ...
DIMITRIS METAXAS
Afra Zomorodian, Herbert Edelsbrunner
Received received date Revised revised date Communicated by Editor’s name We present fast implementations of a hybrid algorithm for reporting box and cube intersections. Our algorithm initially...
Abstract Dynamic Skin Triangulation ∗ (extended abstract) (2008)
Ho-lun Cheng, Tamal K. Dey, Herbert Edelsbrunner, John Sullivan
This paper describes an algorithm for maintaining an approximating triangulation of a deforming surface in R 3. The triangulation adapts dynamically to changing shape, curvature, and topology of the...
Abstract Time-varying Reeb Graphs for Continuous Space-Time Data (2008)
Herbert Edelsbrunner, John Harer, Ajith Mascarenhas, Valerio Pascucci
We study the evolution of the Reeb graph of a time-varying continuous function defined in three-dimensional space. While maintaining the Reeb graph, we compress the evolving sequence into a single,...
Abstract Extreme Elevation on a 2-Manifold (2008)
Pankaj K. Agarwal, Herbert Edelsbrunner, John Harer
Given a smoothly embedded 2-manifold in ¤¦ ¥ , we define the elevation of a point as the height difference to a canonically defined second point on the same manifold. Our definition is invariant...
Frequently, data in scientific computing is in its abstract form a finite point set in space, and it is sometimes useful or required to compute what one might call the “shape ” of the set. For...
Abstract The Union of Balls and its Dual Shape* (2008)
algorithms are described for compuiing topo-logical, combinatorial, and metric properties of ihe union of finitely many balls in R ‘. These algorithms are based on a simplicial complex dual to a...
Contemporary Mathematics Persistent Homology — a Survey (2008)
Herbert Edelsbrunner, John Harer
ABSTRACT. Persistent homology is an algebraic tool for measuring topological features of shapes and functions. It casts the multi-scale organization we frequently observe in nature into a...
Abstract Dynamic Skin Triangulation (2008)
Ho-lun Cheng, Tamal K. Dey, Herbert Edelsbrunner, John Sullivan
This paper describes an algorithm for maintaining an approximating triangulation of a deforming surface in ¥§ ¦. The surface is the envelope of an infinite family of spheres defined and controlled...
Contemporary Mathematics Persistent Homology — a Survey (2008)
Herbert Edelsbrunner, John Harer
ABSTRACT. Persistent homology is an algebraic tool for measuring topological features of shapes and functions. It casts the multi-scale organization we frequently observe in nature into a...
Abstract Computing the Writhing Number of a Polygonal Knot (2008)
Pankaj K. Agarwal, Herbert Edelsbrunner, Yusu Wang
The writhing number measures the global geometry of a closed space curve or knot. We show that this measure is related to the average winding number of its Gauss map. Using this relationship, we give...
Abstract Morse-Smale Complexes for Piecewise Linear 3-Manifolds (2008)
Herbert Edelsbrunner, John Harer, Vijay Natarajan, Valerio Pascucci
We define the Morse-Smale complex of a Morse function over a 3-manifold as the overlay of the descending and ascending manifolds of all critical points. In the generic case, its 3-dimensional cells...
Herbert Edelsbrunner, Nimish R. Shah
Given a subspace X G Rd and a jinite set S G Rd, we in-troduce the Delaunay simplicial complex, DX, restricted by X. Its simplices are spanned by subsets T ~ S for which the common intersection of...
Algorithms for Weak "-Nets (2008)
Bernard Chazelle, Herbert Edelsbrunner, Michelangelo Grigni, Leonidas Guibas, Micha Sharir, Emo Welzl
In the plane, we can nd a weak "-net for convex sets consisting of O( ",2) points, in time O(n ",2). We can determine the smallest " for which a given planar set...
Bernard Chazelle, Herbert Edelsbrunner, Leonidas Guibas, Micha Sharir, Emo Welzl
In the plane, we can find a weak "-net for convex sets consisting of O(" \Gamma2 points, in time O(n" \Gamma2). We can determine the smallest " for which a given...
Bernard Chazelle, Herbert Edelsbrunner, Leonidas Guibas, Micha Sharir, Emo Welzl
Let S be a set of n points in IR d. A set W is a weak "-net for (convex ranges of) S if for any T ` S containing "n points, the convex hull of T intersects W. We show the existence...
Herbert Edelsbrunner, Damrong Guoy
We present results on a two-step improvement of mesh quality in three-dimensional Delaunay triangulations. The rst step renes the triangulation by inserting sinks and eliminates tetrahedra with large...
Herbert Edelsbrunner, David Letscher, Afra Zomorodian
We formalize a notion of topological simplification within the framework of a filtration, which is the history of a growing complex. We classify a topological change that happens during growth as...
Raindrop Geomagic, RTP North Carolina (2007)
Herbert Edelsbrunner, John Harer, Afra Zomorodian
We present algorithms for constructing a hierarchy of increasingly coarse Morse complexes that decompose a piecewise linear 2-manifold. While Morse complexes are defined
Jie Liang, Herbert Edelsbrunner, Ping Fu, Pamidighantam V. Sudhakar, Shankar Subramaniam
ABSTRACT The size and shape of macromolecules such as proteins and nucleic acids play an important role in their functions. Prior efforts to quantify these properties have been based on various...
Weak Witnesses for Delaunay triangulations of Submanifold (2007)
Attali, Dominique, Edelsbrunner, Herbert, Mileyko, Yuriy
The main result of this paper is an extension of de Silva’s Weak Delaunay Theorem to smoothly embedded curves and surfaces in Euclidean space. Assuming a sufficiently fine sampling, we...
Alpha-Beta Witness Complexes (2007)
Attali, Dominique, Edelsbrunner, Herbert, Harer, John, Mileyko, Yuriy
Building on the work of Martinetz, Schulten and de Silva, Carlsson, we introduce a 2-parameter family of witness complexes and algorithms for constructing them. This family can be used to determine...
Inclusion-exclusion formulas for independent complexes (2007)
Attali, Dominique, Edelsbrunner, Herbert
Using inclusion-exclusion, we can write the indicator function of a union of finitely many balls as an alternating sum of indicator functions of common intersections of balls. We exhibit abstract...
Weak Witnesses for Delaunay triangulations of Submanifold (2007)
Attali, Dominique, Edelsbrunner, Herbert, Mileyko, Yuriy
The main result of this paper is an extension of de Silvas Weak Delaunay Theorem to smoothly embedded curves and surfaces in Euclidean space. Assuming a sufficiently fine sampling, we...
Alpha-Beta Witness Complexes (2007)
Attali, Dominique, Edelsbrunner, Herbert, Harer, John, Mileyko, Yuriy
Building on the work of Martinetz, Schulten and de Silva, Carlsson, we introduce a 2-parameter family of witness complexes and algorithms for constructing them. This family can be used to determine...
Inclusion-exclusion formulas for independent complexes (2007)
Attali, Dominique, Edelsbrunner, Herbert
Using inclusion-exclusion, we can write the indicator function of a union of finitely many balls as an alternating sum of indicator functions of common intersections of balls. We exhibit abstract...
Alpha-beta witness complexes (2007)
Dominique Attali, Herbert Edelsbrunner, John Harer, Yuriy Mileyko
Carlsson, we introduce a 2-parameter family of witness complexes and algorithms for constructing them. This family can be used to determine the gross topology of point cloud data in R d or other...
Andrew Danner, Lars Arge Supervisor, Pankaj K. Agarwal, Herbert Edelsbrunner, Helena Mitasova, Andrew Danner, ...
Modern remote sensing methods such a laser altimetry (lidar) and Interferometric Synthetic Aperture Radar (IfSAR) produce georeferenced elevation data at unprecedented rates. Many Geographic...
Andrew Danner, Lars Arge Supervisor, Pankaj K. Agarwal, Herbert Edelsbrunner, Helena Mitasova, Andrew Danner, ...
Modern remote sensing methods such a laser altimetry (lidar) and Interferometric Synthetic Aperture Radar (IfSAR) produce georeferenced elevation data at unprece-dented rates. Many Geographic...
The geometry of biomolecular solvation (2005)
Herbert Edelsbrunner, Patrice Koehl
Abstract. Years of research in biology have established that all cellular functions are deeply connected to the shape and dynamics of their molecular actors. As a response, structural molecular...
Jungsan Sohn, Jerry M. Parks, Gregory Buhrman, Paul Brown, Kolbrun Kristjánsdóttir, Alexias Safi, ...
ABSTRACT: Cdc25 phosphatases are key activators of the eukaryotic cell cycle and compelling anticancer targets because their overexpression has been associated with numerous cancers. However, drug...
Peer-timo Bremer, Herbert Edelsbrunner, Hamann Valerio Pascucci
Approved for public release; further dissemination unlimited
Interface surfaces for protein-protein complexes (2004)
Herbert Edelsbrunner, Johannes Rudolph
Protein-protein interactions, which form the basis for most cellular processes, result in the formation of protein interfaces. Believing that the local shape of proteins is crucial, we take a...
Time-varying reeb graphs for continuous space-time data (2004)
Herbert Edelsbrunner, John Harer, Ajith Mascarenhas, Valerio Pascucci, Jack Snoeyink
The Reeb graph is a useful tool in visualizing real-valued data obtained from computational simulations of physical processes. We characterize the evolution of the Reeb graph of a time-varying...
Time-varying reeb graphs for continuous space-time data (2004)
Herbert Edelsbrunner, John Harer, Ajith Mascarenhas, Valerio Pascucci
Time-varying reeb graphs for continuous space-time data (2004)
Herbert Edelsbrunner, John Harer, Ajith Mascarenhas, Valerio Pascucci
Simplification of Three-dimensional Density Maps (2004)
Vijay Natarajan, Herbert Edelsbrunner
We consider scientific datasets that describe density functions over three-dimensional geometric domains. Such datasets are often large and coarsened representations are needed for visualization and...
A Topological Hierarchy for Functions on Triangulated Surfaces (2004)
Peer-timo Bremer, Herbert Edelsbrunner, Bernd Hamann, Valerio Pascucci
We combine topological and geometric methods to construct a multi-resolution representation for functions over two-dimensional domains. In a preprocessing stage, we create the Morse-Smale complex of...
Local and Global Comparison of Continuous Functions (2004)
Herbert Edelsbrunner, John Harer, Vijay Natarajan, Valerio Pascucci
We introduce local and global comparison measures for a collection of k d real-valued smooth functions on a common d-dimensional Riemannian manifold. For k = d = 2 we relate the measures to the set...
Local and global comparison of continuous functions (2004)
Herbert Edelsbrunner, John Harer, Vijay Natarajan, Valerio Pascucci
Figure 1: We consider the simulation of a combustion process, measure two physical quantities, and compare them. The comparison measure, κ, is mapped to the height of a terrain and the first...
A topological hierarchy for functions on triangulated surfaces (2004)
Peer-timo Bremer, Herbert Edelsbrunner, Bernd Hamann, Valerio Pascucci
Abstract — We combine topological and geometric methods to construct a multi-resolution representation for a function over a two-dimensional domain. In a preprocessing stage, we create the...
Interface surfaces for protein-protein complexes (2004)
Herbert Edelsbrunner, Johannes Rudolph
Protein-protein interactions, which form the basis for most cellular processes, result in the formation of protein interfaces. Believing that the local shape of proteins is crucial, we take a...
ABSTRACT SIMPLIFICATION, ESTIMATION AND CLASSIFICATION OF GEOMETRIC OBJECTS (2004)
Nabil H. Mustafa, Pankaj K. Agarwal, Herbert Edelsbrunner, Shankar Krishnan, Carlo Tomasi, Nabil H. Mustafa, ...
The main focus of this thesis is on the analysis, via simplification, estimation and clas-sification, of discrete geometric objects using methods from discrete and combinatorial geometry. Geometric...
Relaxed Scheduling in Dynamic Skin Triangulation (2003)
Edelsbrunner, Herbert, Ungor, Alper
We introduce relaxed scheduling as a paradigm for mesh maintenance and demonstrate its applicability to triangulating a skin surface in $\Rspace^3$.
Computing linking numbers of a filtration (2003)
Edelsbrunner, Herbert, Zomorodian, Afra
We develop fast algorithms for computing the linking number of a simplicial complex within a filtration. We give experimental results in applying our work toward the detection of non-trivial tangling...
Loops in Reeb graphs of 2-manifolds (2003)
Kree Cole-mclaughlin, Herbert Edelsbrunner, John Harer, Vijay Natarajan, Valerio Pascucci
Given a Morse function ¥ over a 2-manifold with or without boundary, the Reeb graph is obtained by contracting the connected components of the level sets to points. We prove tight upper and lower...
A Multi-resolution Data Structure for Two-dimensional Morse Functions (2003)
Peer-Timo Bremer, Herbert Edelsbrunner, Bernd Hamann, Valerio Pascucci, Bremer¡£ Edelsbrunner Pascucci, Peer-timo Herbert, ...
The efficient construction of simplified models is a central problem in the field of visualization. We combine topological and geometric methods to construct a multi-resolution data structure for...
Relaxed scheduling in dynamic skin triangulation (2002)
Herbert Edelsbrunner, Alper Üngör
Abstract. We introduce relaxed scheduling as a paradigm for mesh maintenance and demonstrate its applicability to triangulating a skin surface in R 3.
Computing linking numbers in a filtration (2001)
Herbert Edelsbrunner, Afra Zomorodian
We develop fast algorithms for computing the linking number of a simplicial complex within a filtration. We give experimental results in applying our work toward the detection of non-trivial tangling...
Hierarchical Morse Complexes for Piecewise Linear 2-Manifolds (2001)
Herbert Edelsbrunner, John Harer, Afra Zomorodian
We present algorithms for constructing a hierarchy of increasingly coarse Morse complexes that decompose a piecewise linear 2-manifold. While Morse complexes are defined
Computing linking numbers in a filtration (2001)
Herbert Edelsbrunner, Afra Zomorodian
Abstract. We develop fast algorithms for computing the linking number of a simplicial complex within a filtration. We give experimental results in applying our work toward the detection of...
Dynamic Skin Triangulation (2001)
Ho-lun Cheng, Tamal K. Dey, Herbert Edelsbrunner, John M. Sullivan
This paper describes an algorithm for maintaining an approximating triangulation of a deforming surface in R 3 . The surface is modeled as the skin defined by a finite set of spheres, as defined in...
Hierarchical Morse Complexes for Piecewise Linear 2-Manifolds (2001)
Herbert Edelsbrunner, John Harer, Afra Zomorodian
We present algorithms for constructing a hierarchy of increasingly coarse Morse complexes that decompose a piecewise linear 2-manifold. While Morse complexes are defined
Area and perimeter derivatives of a union of disks (2001)
Ho-lun Cheng, Herbert Edelsbrunner
Abstract. We give analytic inclusion-exclusion formulas for the area and perimeter derivatives of a union of finitely many disks in the plane.
Cheng, Siu-Wing, Dey, Tamal K., Edelsbrunner, Herbert, Facello, Michael A., Teng, Shang-Hua
A silver is a tetrahedron whose four vertices lie close to a plane and whose orthogonal projection to that plane is a convex quadrilateral with no short edge. Silvers are notoriously common in...
Abstract: The 180 models collected in this paper are produced by sampling and wrapping point sets on tubes. The surfaces are represented as triangulated 2-manifolds and available as stlfiles from the...
Topological persistence and simplification (2000)
Herbert Edelsbrunner, David Letscher, Afra Zomorodian
We formalize a notion of topological simplification within the framework of a filtration, which is the history of a growing complex. We classify a topological change that happens during growth as...
Smoothing and Cleaning up Slivers (2000)
Herbert Edelsbrunner, Xiang-yang Li, Gary Miller, Andreas Stathopoulos, Dafna Talmor, Shang-Hua Teng, ...
A sliver is a tetrahedron whose four vertices lie close to a plane and whose perpendicular projection to that plane is a convex quadrilateral with no short edge. Slivers are both undesirable and...
Abstract: The 180 models collected in this paper are produced by sampling and wrapping point sets on tubes. The surfaces are represented as triangulated 2-manifolds and available as stlfiles from the...
Emerging Challenges in Computational Topology (1999)
Bern, Marshall, Eppstein, David, Agarwal, Pankaj K., Amenta, Nina, Chew, Paul, Dey, Tamal, ...
Here we present the results of the NSF-funded Workshop on Computational Topology, which met on June 11 and 12 in Miami Beach, Florida. This report identifies important problems involving both...
Emerging challenges in computational topology (1999)
Marshall Bern, Pankaj K. Agarwal, Nina Amenta, Paul Chew, Tamal Dey, David P. Dobkin, ...
Here we present the results of the NSF-funded Workshop on Computational Topology, which met on June 11 and 12 in Miami Beach, Florida. This report identifies
Mesh Association: Formulation and Algorithms (1999)
Xiangmin Jiao, Herbert Edelsbrunner, Michael T. Heath
In computational simulation of coupled, multicomponent systems, it is frequently necessary to transfer data between meshes that may differ in resolution, structure, and discretization methodology....
Emerging Challenges in Computational Topology (1999)
Marshall Bern, David Eppstein, Pankaj K. Agarwal, Nina Amenta, Paul Chew, Tamal Dey, ...
Here we present the results of the NSF-funded Workshop on Computational Topology, which met on June 11 and 12 in Miami Beach, Florida. This report identifies important problems involving both...
Siu-Wing Cheng, Tamal K. Dey, Herbert Edelsbrunner, Michael A. Facello, Shang-Hua Teng
A sliver is a tetrahedron whose four vertices lie close to a plane and whose orthogonal projection to that plane is a convex quadrilateral with no short edge. Slivers are notoriously common in...
Siu-wing Cheng, Tamal K. Dey, Herbert Edelsbrunner, Michael A. Facello, Shang-hua Teng
A sliver is a tetrahedron whose four vertices lie close to a plane and whose projection to that plane is a convex quadrilateral with no short edge. Slivers are notoriously common in 3-dimensional...
Siu-Wing Cheng, Tamal K. Dey, Herbert Edelsbrunner, Michael A. Facello, Shang-Hua Teng
A sliver is a tetrahedron whose four vertices lie close to a plane and whose projection to that plane is a convex quadrilateral with no short edge. Slivers are notoriously common in 3-dimensional...
Tamal K. Dey, Herbert Edelsbrunner, Sumanta Guha
The authors of this article believe there is or should be a research area appropriately referred to as computational topology. Its agenda includes the identification and formalization of topological...
Shape and Surface Reconstruction, Quantification and Deformation (1998)
Edelsbrunner, Herbert, Fu, Ping
Research under this grant focused on the reconstruction and the representation of continuous shapes and objects. The primary data structure are meshes, and we study triangle meshes for surface and...
Design and analysis of planar shape deformation (1998)
Cheng, Siu-Wing, Edelsbrunner, Herbert, Fu, Ping, Lam, Ka-Po
Shape deformation refers to the continuous change of one geometric object to another. We develop a software tool for planning, analyzing, and visualizing deformations between two shapes in R2. The...
Jie Liang, Herbert Edelsbrunner, Ping Fu, Pamidighantam V. Sudhakar, Shankar Subramaniam
ABSTRACT The structures of proteins are well-packed, yet they contain numerous cavities which play key roles in accommodating small molecules, or enabling conformational changes. From high-resolution...
Auditory morse analysis of triangulated manifolds (1998)
Ulrike Axen, Herbert Edelsbrunner
Abstract. Visualization of high-dimensional or large geometric data sets is inherently difficult, so we experiment with the use of audio to display the shape and connectivity of these data sets....
Analytical shape computing of macromolecules I: Molecular area and volume through alpha-shape (1998)
Jie Liang, Herbert Edelsbrunner, Ping Fu, Pamidighantam V. Sudhakar, Shankar Subramaniam
ABSTRACT The structures of proteins are well-packed, yet they contain numerous cavities which play key roles in accommodating small molecules, or enabling conformational changes. From high-resolution...
Topology Preserving Edge Contraction (1998)
Tamal K. Dey, Herbert Edelsbrunner, Sumanta Guha, Dmitry V. Nekhayev
We study edge contractions in simplicial complexes and local conditions under which they preserve the topological type. The conditions are based on a generalized notion of boundary, which lends...
Design and Analysis of Planar Shape Deformation (1998)
Siu-Wing Cheng, Herbert Edelsbrunner, Ping Fu, Ka-po Lam
Shape deformation refers to the continuous change of one geometric object to another. We develop a software tool for planning, analyzing, and visualizing deformations between two shapes in R 2 . The...
Design and Analysis of Planar Shape Deformation (1998)
Siu-Wing Cheng, Herbert Edelsbrunner, Ping Fu, Ka-po Lam
Shape deformation refers to the continuous change of one geometric object to another. We develop a software tool for planning, analyzing, and visualizing deformations between two shapes in R 2 . The...
Measuring proteins and voids in proteins (1995)
Herbert Edelsbrunner, Michael Face, Ping Fu, Jie Liang
Common geometric models for proteins and other molecules are the space filling diagram, the solvent ac-cessible surface, and the molecular surface. We descnbe software that compules metric properties...
On the Definition and the Construction of Pockets in Macromolecules (1995)
Herbert Edelsbrunner, Michael Facello, Jie Liang
The shape of a protein is important for its functions. This includes the location and size of identifiable regions in its complement space. We formally define pockets as regions in the complement...
Algorithms for Weak Epsilon-Nets (1995)
Bernard Chazelle, Herbert Edelsbrunner, David Eppstein, Michelangelo Grigni, Leonidas Guibas, Micha Sharir, ...
In the plane, we can find a weak "-net for convex sets consisting of O(" \Gamma2 ) points, in time O(n" \Gamma2 log 2 (1=")). We can determine the smallest " for which a...
Algorithms for Weak Epsilon-Nets (1995)
Bernard Chazelle, Herbert Edelsbrunner, David Eppstein, Michelangelo Grigni, Leonidas Guibas, Micha Sharir, ...
In the plane, we can find a weak "-net for convex sets consisting of O(" \Gamma2 ) points, in time O(n" \Gamma2 ). We can determine the smallest " for which a given planar set is...
Three-dimensional alpha shapes (1994)
Edelsbrunner, Herbert, Mücke, Ernst
Frequently, data in scientific computing is in its abstract form a finite point set in space, and it is sometimes useful or required to compute what one might call the ``shape'' of the set. For that...
Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms (1994)
Edelsbrunner, Herbert, Mücke, Ernst
This paper describes a general-purpose programming technique, called the Simulation of Simplicity, which can be used to cope with degenerate input data for geometric algorithms. It relieves the...
Adaptive Simplicial Grids from Cross-sections of Monotone Complexes (1994)
Herbert Edelsbrunner, Roman Waupotitsch
. We study the maintenance of a simplicial grid or complex under changing density requirements. The proposed method works in any fixed dimension and generates grids by projecting cross-sections of a...
Three-dimensional Alpha Shapes (1994)
Herbert Edelsbrunner, Ernst P. Mücke
. Frequently, data in scientific computing is in its abstract form a finite point set in space, and it is sometimes useful or required to compute what one might call the "shape" of the set....
An Upper Bound for Conforming Delaunay Triangulations (1993)
Herbert Edelsbrunner, Tiow Seng Tan
A plane geometric graph C in ! 2 conforms to another such graph G if each edge of G is the union of some edges of C. It is proved that for every G with n vertices and m edges, there is a completion...
An upper bound for conforming Delaunay triangulations (1993)
Herbert Edelsbrunner, Tiow Seng Tan
A plane geometric graph C in < 2 conforms to another such graph G if each edge of G is the union of some edges of C. It is proved that for every G with n vertices and m edges, there is a...
Edge Insertion for Optimal Triangulations (1992)
Marshall Bern, Herbert Edelsbrunner, David Eppstein, Scott Mitchell, Tiow-Seng Tan, M. Bern, ...
The edge-insertion paradigm improves a triangulation of a finite point set in ! 2 iteratively by adding a new edge, deleting intersecting old edges, and retriangulating the resulting two polygonal...
An optimal algorithm for intersecting line segments in the plane (1992)
Bernard Chazelle, Herbert Edelsbrunner
Abstract. Themain contribution ofthiswork is an O(nlogr ~ +k)-timeal gorithmfo rcomputingall k intersections among n line segments in the plane, This time complexity IS easdy shown to be optimal....
Arrangements of curves in the plane --- topology, combinatorics, and algorithms. (1992)
Edelsbrunner, Herbert, Guibas, Leonidas, Pach, János, Pollack, Richard, Seidel, Raimund, Sharir, Micha
A Quadratic Time Algorithm for the MinMax Length Triangulation (1991)
Herbert Edelsbrunner, Seng Tan
Abstract. We show that a triangulation of a set of n points in the plane that minimizes the maximum edge length can be computed in time O(n 2). The algorithm is reasonably easy to implement and is...
Elsevier Counting and cutting cycles of lines and rods in space* (1991)
Bernard Chazelle, Herbert Edelsbrunner, Leonidas J. Guibas, Richard Pollack, Raimund Seidel, Micha Sharir, ...
306 B. Chazelle et al.
Simulation of Simplicity: A Technique to Cope with Degenerate Cases in Geometric Algorithms (1990)
Herbert Edelsbrunner, Ernst Peter Mücke
This paper describes a general-purpose programming technique, called the Simulation of Simplicity, which can be used to cope with degenerate input data for geometric algorithms. It relieves the...
On the lower envelope of bivariate functions and its applications (1987)
Pach, János, Edelsbrunner, Herbert, Schwartz, J.T., Sharir, Micha
Voronoi Diagrams and Arrangements (1985)
Edelsbrunner, Herbert, Seidel, Raimund
We propose a uniform and general framework for defining and dealing with Voronoi Diagrams. In this framework a Voronoi Diagram is a partition of a domain $D$ induced by a finite number of real valued...
Voronoi Diagrams and Arrangements (1985)
Edelsbrunner, Herbert, Seidel, Raimund
We propose a uniform and general framework for defining and dealing with Voronoi Diagrams. In this framework a Voronoi Diagram is a partition of a domain $D$ induced by a finite number of real valued...
Intersection problems in computational geometry /--by Herbert Edelsbrunner. (1982)
Thesis (doctoral)--Technische Universität Graz, 1982.
The weighted-volume derivative of a space-filling diagram
Edelsbrunner, Herbert, Koehl, Patrice
Computing the volume occupied by individual atoms in macromolecular structures has been the subject of research for several decades. This interest has grown in the recent years, because weighted...
The weighted-volume derivative of a space-filling diagram
Edelsbrunner, Herbert, Koehl, Patrice
Computing the volume occupied by individual atoms in macromolecular structures has been the subject of research for several decades. This interest has grown in the recent years, because weighted...
Comparison of Pattern Detection Methods in Microarray Time Series of the Segmentation Clock
Dequéant, Mary-Lee, Ahnert, Sebastian, Edelsbrunner, Herbert, Fink, Thomas M. A., Glynn, Earl F., Hattem, Gaye, ...
While genome-wide gene expression data are generated at an increasing rate, the repertoire of approaches for pattern discovery in these data is still limited. Identifying subtle patterns of interest...
Efficient algorithms for agglomerative hierarchical clustering methods
William Day, Herbert Edelsbrunner
Algorithm complexity, Algorithm design, Centroid clustering method, Geometric model, SAHN clustering method,
Investigation of proportional link linkage clustering methods
William Day, Herbert Edelsbrunner
Algorithm complexity, Algorithm design, Integer link linkage clustering method, Monotone invariance, SAHN clustering method, Space distortion,