Arrow Research search

Author name cluster

Herbert Edelsbrunner

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

28 papers
2 author rows

Possible papers

28

SODA Conference 2014 Conference Paper

On the Computational Complexity of Betti Numbers: Reductions from Matrix Rank

  • Herbert Edelsbrunner
  • Salman Parsa

We give evidence for the difficulty of computing Betti numbers of simplicial complexes over a finite field. We do this by reducing the rank computation for sparse matrices with m non-zero entries to computing Betti numbers of simplicial complexes consisting of at most a constant times m simplices. Together with the known reduction in the other direction, this implies that the two problems have the same computational complexity.

Details

MFCS Conference 2010 Conference Paper

Persistent Homology under Non-uniform Error

  • Paul Bendich
  • Herbert Edelsbrunner
  • Michael Kerber
  • Amit K. Patel

Abstract Using ideas from persistent homology, the robustness of a level set of a real-valued function is defined in terms of the magnitude of the perturbation necessary to kill the classes. Prior work has shown that the homology and robustness information can be read off the extended persistence diagram of the function. This paper extends these results to a non-uniform error model in which perturbations vary in their magnitude across the domain.

Details

SODA Conference 2009 Conference Paper

Persistent homology for kernels, images, and cokernels

  • David Cohen-Steiner
  • Herbert Edelsbrunner
  • John Harer
  • Dmitriy Morozov

Motivated by the measurement of local homology and of functions on noisy domains, we extend the notion of persistent homology to sequences of kernels, images, and cokernels of maps induced by inclusions in a filtration of pairs of spaces. Specifically, we note that persistence in this context is well defined, we prove that the persistence diagrams are stable, and we explain how to compute them.

Details

FOCS Conference 2007 Conference Paper

Inferring Local Homology from Sampled Stratified Spaces

  • Paul Bendich
  • David Cohen-Steiner
  • Herbert Edelsbrunner
  • John Harer
  • Dmitriy Morozov

We study the reconstruction of a stratified space from a possibly noisy point sample. Specifically, we use the vineyard of the distance function restricted to a 1-parameter family of neighborhoods of a point to assess the local homology of the stratified space at that point. We prove the correctness of this assessment under the assumption of a sufficiently dense sample. We also give an algorithm that constructs the vineyard and makes the local assessment in time at most cubic in the size of the Delaunay triangulation of the point sample.

Details

FOCS Conference 2000 Conference Paper

Topological Persistence and Simplification

  • 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 either a feature or noise, depending on its life-time or persistence within the filtration. We give fast algorithms for completing persistence and experimental evidence for their speed and utility.

Details

FOCS Conference 1995 Conference Paper

Algebraic Decompositions of Non-Convex Polyhedra

  • Herbert Edelsbrunner

Any arbitrary polyhedron P/spl sube/R/sup d/ can be written as algebraic sum of simple terms, each an integer multiple of the intersection of d or fewer half-spaces defined by facets of P. P can be non-convex and can have holes of any kind. Among the consequences of this result are a short boolean formula for P, a fast parallel algorithm for point classification, and a new proof of the Gram-Sommerville angle relation.

Details

FOCS Conference 1991 Conference Paper

A Quadratic Time Algorithm for The MinMax Length Triangulation (Extended Abstract)

  • Herbert Edelsbrunner
  • Tiow Seng Tan

It is shown 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/sup 2/). The algorithm is reasonably easy to implement and is based on the theorem that there is a triangulation with minmax edge length that contains the relative neighborhood graph of the points as a subgraph. With minor modifications the algorithm works for arbitrary normed metrics. >

Details

FOCS Conference 1990 Conference Paper

Counting and Cutting Cycles of Lines and Rods in Space

  • Bernard Chazelle
  • Herbert Edelsbrunner
  • Leonidas J. Guibas
  • Richard Pollack
  • Raimund Seidel
  • Micha Sharir
  • Jack Snoeyink

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. >

Details

FOCS Conference 1988 Conference Paper

An Optimal Algorithm for Intersecting Line Segments in the Plane

  • Bernard Chazelle
  • Herbert Edelsbrunner

The authors present the first optimal algorithm for the following problem: given n line segments in the plane, compute all k pairwise intersections in O(n log n+k) time. Within the same asymptotic cost the algorithm will also compute the adjacencies of the planar subdivision induced by the segments, which is a useful data structure for contour-filling on raster devices. >

Details

FOCS Conference 1988 Conference Paper

Combinatorial Complexity Bounds for Arrangements of Curves and Surfaces

  • Kenneth L. Clarkson
  • Herbert Edelsbrunner
  • Leonidas J. Guibas
  • Micha Sharir
  • Emo Welzl

The authors study both the incidence counting and the many-faces problem for various kinds of curves, including lines, pseudolines, unit circles, general circles, and pseudocircles. They also extend the analysis to three dimensions, where they concentrate on the case of spheres, which is relevant for the three-dimensional unit-distance problem. They obtain upper bounds for certain quantities. The authors believe that the techniques they use are of independent interest. >

Details

FOCS Conference 1987 Conference Paper

On the Lower Envelope of Bivariate Functions and its Applications

  • Herbert Edelsbrunner
  • János Pach
  • Jacob T. Schwartz
  • Micha Sharir

We consider the problem of obtaining sharp (nearly quadratic) bounds for the combinatorial complexity of the lower envelope (i. e. pointwise minimum) of a collection of n bivariate (or generally multi-variate) continuous and "simple" functions, and of designing efficient algorithms for the calculation of this envelope. This problem generalizes the well-studied univariate case (whose analysis is based on the theory of Davenport-Schinzel sequences), but appears to be much more difficult and still largely unsolved. It is a central problem that arises in many areas in computational and combinatorial geometry, and has numerous applications including generalized planar Voronoi diagrams, hidden surface elimination for intersecting surfaces, purely translational motion planning, finding common transversals of polyhedra, and more. In this abstract we provide several partial solutions and generalizations of this problem, and apply them to the problems mentioned above. The most significant of our results is that the lower envelope of n triangles in three dimensions has combinatorial complexity at most O(n2α(n)) (where α(n) is the extremely slowly growing inverse of Ackermann's function), that this bound is tight in the worst case, and that this envelope can be calculated in time O(n2α(n)).

Details

FOCS Conference 1984 Conference Paper

Space Searching for Intersecting Objects

  • David P. Dobkin
  • Herbert Edelsbrunner

Determining or counting geometric objects that intersect another geometric query object is at the core of algorithmic problems in a number of applied areas of computer science. This article presents a family of space-efficient data structures that realize sublinear query time for points, line segments, lines and polygons in the plane, and points, line segments, plaraes, and polyhedra in three dimensions.

Details

FOCS Conference 1983 Conference Paper

Constructing Arrangements of Lines and Hyperplanes with Applications

  • Herbert Edelsbrunner
  • Joseph O'Rourke
  • Raimund Seidel

An optimal algorithm is presented for constructing an arrangement of hyperplanes in arbitrary dimensions. It relies on a combinatorial result that is of interest in its own right. The algorithm is shown to improve known worst-case time complexities for five problems: computing all order-k Voronoi diagrams, computing the λ-matrix, estimating halfspace queries, degeneracy testing, and finding the minimum volume simplex determined by a set of points.

Details