|
ROLE
AUTHOR PROFILE PAGES (BETA)
Project background
BOOKMARK & SHARE
|
|
|
|
| Export results as:
BibTeX
EndNotes
ACM Ref
|
| 2009
|
1
|
|
Minimum cuts and shortest homologous cycles
Erin W. Chambers, Jeff Erickson, Amir Nayyeri
|
|
June 2009
|
|
SCG '09: Proceedings of the 25th annual symposium on Computational geometry
|
|
Publisher: ACM
|
|
Full text available: |
 Pdf
(729.25 KB)
|
|
|
| Bibliometrics: Downloads (6 Weeks): 11, Downloads (12 Months): 48, Citation Count: 1 |
 |
|
We describe the first algorithms to compute minimum cuts in surface-embedded graphs in near-linear time. Given an undirected graph embedded on an orientable surface of genus g, with two specified vertices s and t, our algorithm computes a minimum (s,t)-cut ...
Keywords: computational topology, topological graph theory
|
| |
|
2
|
|
Homology flows, cohomology cuts
Erin W. Chambers, Jeff Erickson, Amir Nayyeri
|
|
May 2009
|
|
STOC '09: Proceedings of the 41st annual ACM symposium on Theory of computing
|
|
Publisher: ACM
|
|
Full text available: |
Pdf
(783.18 KB)
|
|
|
| Bibliometrics: Downloads (6 Weeks): 19, Downloads (12 Months): 81, Citation Count: 1 |
|
|
We describe the first algorithms to compute maximum flows in surface-embedded graphs in near-linear time. Specifically, given an undirected graph embedded on an orientable surface of genus g, with two specified vertices s and t, we can compute a maximum ...
Keywords: combinatorial optimization, computational topology
|
| |
|
3
|
|
Guest Editor’s Foreword
Jeff Erickson
|
|
May 2009
|
|
Discrete & Computational Geometry
, Volume 42 Issue 1
|
|
Publisher: Springer-Verlag New York, Inc.
|
|
| Bibliometrics: Downloads (6 Weeks): n/a, Downloads (12 Months): n/a, Citation Count: 0 |
|
|
|
|
| |
|
| 2008
|
4
|
|
Splitting (complicated) surfaces is hard
Erin W. Chambers, Éric Colin de Verdière, Jeff Erickson, Francis Lazarus, Kim Whittlesey
|
|
October 2008
|
|
Computational Geometry: Theory and Applications
, Volume 41 Issue 1-2
|
|
Publisher: Elsevier Science Publishers B. V.
|
|
| Bibliometrics: Downloads (6 Weeks): n/a, Downloads (12 Months): n/a, Citation Count: 3 |
|
|
Let M be an orientable combinatorial surface. A cycle on M is splitting if it has no self-intersections and it partitions M into two components, neither of which is homeomorphic to a disk. In other words, splitting cycles are simple, separating, and ...
Keywords: Combinatorial surfaces, Computational topology, Homotopy
|
| |
|
5
|
|
Testing contractibility in planar rips complexes
Erin W. Chambers, Jeff Erickson, Pratik Worah
|
|
June 2008
|
|
SCG '08: Proceedings of the twenty-fourth annual symposium on Computational geometry
|
|
Publisher: ACM
|
|
Full text available: |
Pdf
(1.03 MB)
|
|
|
| Bibliometrics: Downloads (6 Weeks): 2, Downloads (12 Months): 38, Citation Count: 1 |
|
|
The (Vietoris-)Rips complex of a discrete point-set P is an abstract simplicial complex in which a subset of P defines a simplex if and only if the diameter of that subset is at most 1. We describe an efficient algorithm to determine whether ...
Keywords: computational topology, homotopy, rips shadow, vietoris-rips complex
|
| |
|
6
|
|
Walking your dog in the woods in polynomial time
Erin Wolf Chambers, Éric Colin de Verdière, Jeff Erickson, Sylvain Lazard, Francis Lazarus, Shripad Thite
|
|
June 2008
|
|
SCG '08: Proceedings of the twenty-fourth annual symposium on Computational geometry
|
|
Publisher: ACM
|
|
Full text available: |
Pdf
(346.54 KB)
|
|
|
| Bibliometrics: Downloads (6 Weeks): 8, Downloads (12 Months): 63, Citation Count: 1 |
|
|
The Fréchet distance between two curves in the plane is the minimum length of a leash that allows a dog and its owner to walk along their respective curves, from one end to the other, without backtracking. We propose a natural extension of Fréchet ...
Keywords: geodesic leash map, homotopic fréchet distance
|
| |
|
7
|
|
Empty-ellipse graphs
Olivier Devillers, Jeff Erickson, Xavier Goaoc
|
|
January 2008
|
|
SODA '08: Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms
|
|
Publisher: Society for Industrial and Applied Mathematics
|
|
Full text available: |
Pdf
(695.05 KB)
|
|
|
| Bibliometrics: Downloads (6 Weeks): 11, Downloads (12 Months): 45, Citation Count: 1 |
|
|
We define and study a geometric graph over points in the plane that captures the local behavior of Delaunay triangulations of points on smooth surfaces in IR3. Two points in a planar point set P are neighbors in the empty-ellipse ...
|
| |
|
8
|
|
Finding one tight cycle
Sergio Cabello, Matt DeVos, Jeff Erickson, Bojan Mohar
|
|
January 2008
|
|
SODA '08: Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms
|
|
Publisher: Society for Industrial and Applied Mathematics
|
|
Full text available: |
Pdf
(370.83 KB)
|
|
|
| Bibliometrics: Downloads (6 Weeks): 3, Downloads (12 Months): 38, Citation Count: 2 |
|
|
A cycle on a combinatorial surface is tight if it as short as possible in its (free) homotopy class. We describe an algorithm to compute a single tight, non-contractible, simple cycle on a given orientable combinatorial surface in O(n log n) time. ...
|
| |
|
| 2006
|
9
|
|
On the Least Median Square Problem
Jeff Erickson, Sariel Har-Peled, David M. Mount
|
|
December 2006
|
|
Discrete & Computational Geometry
, Volume 36 Issue 4
|
|
Publisher: Springer-Verlag New York, Inc.
|
|
| Bibliometrics: Downloads (6 Weeks): n/a, Downloads (12 Months): n/a, Citation Count: 1 |
|
|
We consider the exact and approximate computational complexity of the multivariate least median-of-squares (LMS) linear regression estimator. The LMS estimator is among the most widely used robust linear statistical estimators. Given a set of n points ...
|
| |
|
10
|
|
Necklaces, convolutions, and X + Y
David Bremner, Timothy M. Chan, Erik D. Demaine, Jeff Erickson, Ferran Hurtado, John Iacono, Stefan Langerman, Perouz Taslakian
|
|
September 2006
|
|
ESA'06: Proceedings of the 14th conference on Annual European Symposium - Volume 14
, Volume 14
|
|
Publisher: Springer-Verlag
|
|
| Bibliometrics: Downloads (6 Weeks): n/a, Downloads (12 Months): n/a, Citation Count: 1 |
|
|
We give subquadratic algorithms that, given two necklaces each with n beads at arbitrary positions, compute the optimal rotation of the necklaces to best align the beads. Here alignment is measured according to the lp norm of ...
|
| |
|
|
|
|
|
Author only
