Erin Wolf Chambers, Éric Colin, De Verdière, Jeff Erickson, Sylvain Lazard, Francis Lazarus
ABSTRACT. 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,...
WALKING YOUR DOG IN THE WOODS IN POLYNOMIAL TIME (2009)
Erin Wolf Chambers, Éric Colin, De Verdière, Jeff Erickson, Sylvain Lazard, Francis Lazarus, ...
Abstract. 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,...
Flipturning Polygons (Extended abstract) (2009)
Oswin Aichholzer, Carmen Cortés, Erik D. Demaine, Vida Dujmović, Jeff Erickson, Mark Overmars, ...
Figure 1. A flipturn. The pocket is bold (red), and its lid is dashed. A central problem in polymer physics and molecular biology is the reconfiguration of large molecules (modeled as polygons) such...
Homology Flows, Cohomology Cuts ∗ (2009)
Erin W. Chambers, Jeff Erickson, Amir Nayyeri, John Dryden, All For Love, Erin Chambers, ...
We describe the first algorithms to compute maximum flows in surface-embedded graphs in nearlinear time. Specifically, given an undirected graph embedded on an orientable surface of genus g, with two...
Erin Chambers, Jeff Erickson, Amir Nayyeri, Erin Chambers, Jeff Erickson, Amir Nayyeri
We describe the first algorithms to compute minimum cuts in surface-embedded graphs in nearlinear time. Given an undirected graph embedded on an orientable surface of genus g, with two specified...
Computing the Shortest Essential Cycle ∗ (2009)
An essential cycle on a surface is a simple cycle that cannot be continuously deformed to a point or a single boundary. We describe algorithms to compute the shortest essential cycle in an orientable...
Abstract On the Complexity of Halfspace Volume Queries (2008)
Erik D. Demaine, Jeff Erickson, Stefan Langerman
Given a polyhedron P in R d with n vertices, a halfspace volume query asks for the volume of P ∩ H for a given halfspace H. We show that, for d ≥ 3, such queries can require Ω(n) operations...
REALIZING PARTITIONS RESPECTING FULL AND PARTIAL ORDER INFORMATION (2008)
Erik Demaine, Jeff Erickson, Danny Krizanć, Henk Meijer, Pat Morin, Mark Overmars, ...
Abstract. For n ∈ , we consider the problem of partitioning the interval [0, n) into k subintervals of positive integer lengths ℓ1,..., ℓk such that the lengths satisfy a set of simple...
Realizing Partitions Respecting Full and Partial Order Information Abstract (2008)
Erik D. Demaine, Jeff Erickson, Henk Meijer, Pat Morin, Mark Overmars, Sue Whitesides
For n ∈ N, we consider the problem of partitioning the interval [0, n) into k subintervals of positive integer lengths ℓ1,..., ℓk such that the lengths satisfy a set of simple constraints of...
Realizing Partitions Respecting Full and Partial Order Information (2008)
Erik Demaine, Jeff Erickson, Danny Krizanć, Henk Meijer, Pat Morin, Mark Overmars, ...
For n ∈ N, we consider the problem of partitioning the interval [0, n) into k subintervals of positive integer lengths ℓ1,..., ℓk such that the lengths satisfy a set of simple constraints of...
Distance-2 edge coloring is NPcomplete (2008)
Jeff Erickson, Shripad Thite, David Bunde
Let G be a simple, undirected graph. We say that two edges of G are within distance 2 of each other if either they are adjacent or there is some other edge that is adjacent to both of them. A...
Lower Bounds for External Algebraic Decision Trees * (2008)
Abstract We propose a natural extension of algebraic decision trees to the external-memory setting, where the cost of disk operations overwhelms CPU time, and prove a tight lower bound of \Omega (n...
ABSTRACT Splitting (Complicated) Surfaces Is Hard ∗ (2008)
Erin W. Chambers, Francis Lazarus, Jeff Erickson, Kim Whittlesey
Let M be an orientable combinatorial surface without boundary. 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...
Universitat Polit`ecnica de Catalunya Polytechnic University (2008)
Erik D. Demaine, Jeff Erickson
ABSTRACT We consider the separability of two point sets inside a polygon by means of chords or geodesic lines. Specifically, given a set of red points and a set of blue points in the interior of a...
Necklaces, Convolutions, and X + Y (2008)
David Bremner, Timothy M. Chan, Erik D. Demaine, Jeff Erickson, Ferran Hurtado, John Iacono, ...
Abstract. 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...
IEEE TRANSACTIONS ON ROBOTICS 1 Capturing a Convex Object with Three Discs (2008)
Jeff Erickson, Shripad Thite, Fred Rothganger, Jean Ponce Fellow
Abstract — This paper addresses the problem of capturing an arbitrary convex object P in the plane with three congruent disc-shaped robots. Given two stationary robots in contact with P, we...
University of Pennsylvania (2008)
Leonidas J. Guibas, Herbert Edelsbrunner, Jeff Erickson, Michael Isard, John Hershberger, Christian Jensen, ...
DIMITRIS METAXAS
Swarup Acharya, Rafael Alonso, Michael J. Franklin, Stanley B. Zdonik, Pankaj Agarwal, Lars Arge, ...
145
G.2.2 [Mathematics of Computing]: Discrete Mathematics—Graph Theory General Terms Algorithms (2008)
Erik D. Demaine, Jeff Erickson
We present an algorithm to unfold any triangulated 2-manifold (in particular, any simplicial polyhedron) into a non-overlapping, connected planar layout in linear time. The manifold is cut only along...
Meshing Roundtable [9]. (2008)
Jeff Erickson, Æ Damrong, Guoy Æ John, M. Sullivan, Alper U Ngo¨r, J. Erickson, ...
Abstract We present an algorithm to construct meshes suitable for spacetime discontinuous Galerkin finiteelement methods. Our method generalizes and improves the ‘Tent Pitcher ’ algorithm of U ¨...
March 25, 2005 8:15 WSPC/Guidelines chordsep SEPARATING POINT SETS IN POLYGONAL ENVIRONMENTS (2008)
Erik D. Demaine, Jeff Erickson, Ferran Hurtado, John Iacono, Stefan Langerman, Henk Meijer, ...
∗Partially supported by DURSI 2001SGR00224, Acció Integrada UPC-McGill (DURSI2004) and
ABSTRACT Minimum-Cost Coverage of Point Sets by Disks ∗ (2008)
Helmut Alt, Jeff Erickson, Jonathan Lenchner, Esther M. Arkin, Sándor P. Fekete
We consider a class of geometric facility location problems in which the goal is to determine a set X of disks given by their centers (t j) and radii (r j) that cover a given set of demand points Y...
On the Complexity of Halfspace Volume Queries (2008)
Erik D. Demaine, Jeff Erickson, Stefan Langerman
Given a polyhedron P in R d with n vertices, a halfspace volume query asks for the volume of P ∩ H for a given halfspace H. We show that, for d ≥ 3, such queries can require Ω(n) operations...
Distance-2 edge coloring is NPcomplete (2008)
Jeff Erickson, Shripad Thite, David P. Bunde
We prove that it is NP-complete to determine whether there exists a distance-2 edge coloring (strong edge coloring) with 5 colors of a bipartite 2-inductive graph with girth 6 and maximum degree 3....
Output-Sensitive Algorithms for Computing Nearest-Neighbour Decision Boundaries ⋆ (2008)
David Bremner, Erik Demaine, Jeff Erickson, John Iacono, Stefan Langerman, Pat Morin, ...
Abstract. Given a set R of red points and a set B of blue points, the nearest-neighbour decision rule classifies a new point q as red (respectively, blue) if the closest point to q in R ∪ B comes...
March 25, 2005 14:14 WSPC/Guidelines chordsep SEPARATING POINT SETS IN POLYGONAL ENVIRONMENTS (2008)
Erik D. Demaine, Jeff Erickson, Ferran Hurtado, John Iacono, Stefan Langerman, Henk Meijer, ...
∗Partially supported by DURSI 2001SGR00224, Acció Integrada UPC-McGill (DURSI2004) and
AUTOMATIC BLOCKING SCHEME FOR STRUCTURED MESHING IN 2D MULTIPHASE FLOW SIMULATION (2008)
We present an automatic algorithm to construct blocking scheme for multiblock structured meshes in 2D multiphase flow problems. Our solution is based on the concepts of medial axis and Delaunay...
REALIZING PARTITIONS RESPECTING FULL AND PARTIAL ORDER INFORMATION (2008)
Erik Demaine, Jeff Erickson, Danny Krizanć, Henk Meijer, Pat Morin, Mark Overmars, ...
Abstract. For n ∈ �, we consider the problem of partitioning the interval [0, n) into k subintervals of positive integer lengths ℓ1,..., ℓk such that the lengths satisfy a set of simple...
Finding one tight cycle (2008)
Sergio Cabello, Matt Devos, Jeff Erickson, Bojan Mohar
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...
Abstract Greedy Optimal Homotopy and Homology Generators ∗ (2008)
We describe simple greedy algorithms to construct the shortest set of loops that generates either the fundamental group (with a given basepoint) or the first homology group (over any fixed...
ABSTRACT On the Least Median Square Problem ∗ (2008)
Jeff Erickson, Sariel Har-peled
We consider the exact and approximate computational complexity of the multivariate LMS linear regression estimator. The LMS estimator is among the most widely used robust linear statistical...
Necklaces, Convolutions, and X + Y (2008)
David Bremner, Timothy M. Chan, Erik D. Demaine, Jeff Erickson, Ferran Hurtado, John Iacono, ...
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...
Realizing Partitions Respecting Full and Partial Order Information Abstract (2008)
Erik D. Demaine, Jeff Erickson, Henk Meijer, Pat Morin, Mark Overmars, Sue Whitesides
For n ∈ N, we consider the problem of partitioning the interval [0,n) into k subintervals of positive integer lengths ℓ1,...,ℓk such that the lengths satisfy a set of simple constraints of the...
Necklaces, Convolutions, and X + Y (2008)
David Bremner, Timothy M. Chan, Erik D. Demaine, Jeff Erickson, Ferran Hurtado, John Iacono, ...
Abstract. 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...
Output-Sensitive Algorithms for Computing Nearest-Neighbour Decision Boundaries ⋆ (2008)
David Bremner, Erik Demaine, Jeff Erickson, John Iacono, Stefan Langerman, Pat Morin, ...
Abstract. Given a set R of red points and a set B of blue points, the nearest-neighbour decision rule classifies a new point q as red (respectively, blue) if the closest point to q in R ∪ B comes...
OUTPUT-SENSITIVE ALGORITHMS FOR COMPUTING NEAREST-NEIGHBOUR DECISION BOUNDARIES ∗ (2008)
David Bremner, Erik Demaine, Jeff Erickson, John Iacono, Stefan Langerman, Pat Morin, ...
ABSTRACT. Given a set R of red points and a set B of blue points, the nearest-neighbour decision rule classifies a new point q as red (respectively, blue) if the closest point to q in R ∪ B comes...
Output-Sensitive Algorithms for Computing Nearest-Neighbour Decision Boundaries (2008)
David Bremner, Erik Demaine, Jeff Erickson, John Iacono, Stefan Langerman, Pat Morin, ...
Given a set R of red points and a set B of blue points, the nearest-neighbour decision rule classifies a new point q as red (respectively, blue) if the closest point to q in R B comes from R...
Output-Sensitive Algorithms for Computing Nearest-Neighbour Decision Boundaries (2008)
David Bremner, Erik Demaine, Jeff Erickson, John Iacono, Stefan Langerman, Pat Morin, ...
Given a set R of red points and a set B of blue points, the nearest-neighbour decision rule classifies a new point q as red (respectively, blue) if the closest point to q in R [ B comes from R...
Output-Sensitive Algorithms for Computing Nearest-Neighbour Decision Boundaries (2008)
David Bremner, Erik Demaine, Jeff Erickson, John Iacono, Stefan Langerman, Pat Morin, ...
Given a set R of red points and a set B of blue points, the nearest-neighbour decision rule classifies a new point q as red (respectively, blue) if the closest point to q in R ∪ B comes from...
Devillers, Olivier, Erickson, Jeff, Goaoc, Xavier
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 3-space. Two points in a planar point set P...
Devillers, Olivier, Erickson, Jeff, Goaoc, Xavier
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 3-space. Two points in a planar point set P...
Walking Your Dog in the Woods in Polynomial Time (2008)
Wolf Chambers, Erin, Colin De Verdire, Eric, Erickson, Jeff, Lazard, Sylvain, Lazarus, Francis, Thite, Shripad
The Frechet 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...
Walking Your Dog in the Woods in Polynomial Time (2008)
Wolf Chambers, Erin, Colin De Verdire, Eric, Erickson, Jeff, Lazard, Sylvain, Lazarus, Francis, Thite, Shripad
The Frechet 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...
Olivier Devillers, Jeff Erickson, Xavier Goaoc
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 IR 3. Two points in a planar point set P are...
Testing Contractibility in Planar Rips Complexes ∗ (2008)
Erin W. Chambers, Jeff Erickson, Pratik Worah
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...
WALKING YOUR DOG IN THE WOODS IN POLYNOMIAL TIME 1 (2008)
Erin Wolf Chambers, Éric Colin, De Verdière, Jeff Erickson, Sylvain Lazard, Francis Lazarus, ...
Abstract. 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,...
Computing the shortest essential cycle (2008)
An essential cycle on a surface is a simple cycle that cannot be continuously deformed to a point or a single boundary. We describe algorithms to compute the shortest essential cycle in an orientable...
Computing the shortest essential cycle (2008)
A non-contractible cycle is a simple cycle that cannot be deformed to a point. An essential cycle is a non-contractible cycle that cannot be deformed to a boundary on the surface. One of the first...
Rips Complexes of Planar Point Sets (2007)
Chambers, Erin W., De Silva, Vin, Erickson, Jeff, Ghrist, Robert
Fix a finite set of points in Euclidean $n$-space $\euc^n$, thought of as a point-cloud sampling of a certain domain $D\subset\euc^n$. The Rips complex is a combinatorial simplicial complex based on...
Pankaj K. Agarwal, Lars Arge, Jeff Erickson, Paolo G. Franciosa, Jeffrey Scott Vitter
We show how to preprocess a set S of points in R d to get an external memory data structure that efficiently supports linear-constraint queries. Each query is in the form of a linear constraint a...
Open Problems on Polytope Reconstruction (2007)
Erik D. Demaine, Jeff Erickson
. We describe some open algorithmic problems related to constructing 3-dimensional polytopes from limited information. Introduction. There are several dierent ways to specify convex polytopes in...
New Lower Bounds for Hopcroft's Problem (Extended Abstract) (2007)
Jeff Erickson, New Lower, Bounds Hopcroft's Problem
) Jeff Erickson Computer Science Division University of California Berkeley, CA 94720 USA jeffe@cs.berkeley.edu Fachbereich Informatik Universitat des Saarlandes D-66123 Saarbrucken, Germany Abstract...
New Lower Bounds for Hopcroft's Problem (Extended Abstract) (2007)
) Jeff Erickson Computer Science Division University of California Berkeley, CA 94720 USA jeffe@cs.berkeley.edu Fachbereich Informatik Universitat des Saarlandes D-66123 Saarbrucken, Germany Abstract...
On the Relative Complexities of Some Geometric Problems (Extended Abstract) (2007)
) Jeff Erickson y 1 Introduction We consider a number of problems whose best known algorithms run in roughly O(n 4=3 ) time. While it is generally believed that these algorithms are optimal, at least...
Pankaj K. Agarwal, Jeff Erickson
. 1. Introduction HW Cl, Cl2 CS Pankaj K. Agarwal and Jeff Erickson Geometric Range Searching and Its Relatives Contemporary Mathematics c 0000 (copyright holder) Mathematics Subject Classification....
Finding Longest Arithmetic Progressions (2007)
We describe efficient output-sensitive algorithms to find the longest arithmetic progression in a given set of numbers.
David Bremner, Erik Demaine, Jeff Erickson, John Iacono, Stefan Langerman, Pat Morin, ...
Computer Science Department, University of Illinois,
G.2.2 [Mathematics of Computing]: Discrete Mathematics—Graph Theory General Terms Algorithms (2007)
Erik D. Demaine, Jeff Erickson
We present an algorithm to unfold any triangulated 2-manifold (in particular, any simplicial polyhedron) into a non-overlapping, connected planar layout in linear time. The manifold is cut only along...
Oswin Aichholzerf, Vida Dujmovid, Mark Overmars, Carmen Cortes, Jeff Erickson, ...
jeffecs.uiuc.edu
guidance, and numerous contributions to this work. (2007)
Sariel Har-peled, Prof Micha Sharir, Bernard Chazelle, Ken Clarkson, Alon Efrat, Jeff Erickson
by
Preprocessing Chains for Dihedral Rotations is Difficult (2007)
Michael Soss, Jeff Erickson, Mark Overmars
This draft was last touched on September 14, 2001. We examine a computational geometric problem concerning the structure of polymers. We model a polymer as a polygonal chain in three dimensions. Each...
x Submitted to Journal of Computer and System Sciences (2007)
Pankaj K. Agarwal, Lars Arge, Jeff Erickson
We propose three indexing schemes for storing a set S of N points in the plane, each moving along a linear trajectory, so that a query of the following form can be answered quickly: Given a rectangle...
Pankaj K. Agarwal, Lars Arge, Jeff Erickson
We propose three indexing schemes for storing a set S of N points in the plane, each moving along a linear trajectory, so that a query of the following form can be answered quickly: Given a rectangle...
Output-Sensitive Algorithms for Computing Nearest-Neighbour Decision Boundaries (2007)
David Bremner, Erik Demaine, Jeff Erickson, John Iacono, Stefan Langerman, Pat Morin, ...
Given a set R of red points and a set B of blue points, the nearest-neighbour decision rule classifies a new point q as red (respectively, blue) if the closest point to q in R B comes from R...
Flat-State Connectivity of Linkages under Dihedral Motions (2007)
Greg Aloupis, Erik D. Demaine, Vida Dujmovic, Jeff Erickson, Stefan Langerman, Henk Meijer, ...
We explore which classes of linkages have the property that each pair of their at states|that is, their embeddings in R without self-intersection|can be connected by a continuous dihedral motion that...
On the Complexity of Halfspace Volume Queries (2007)
Erik D. Demaine, Jeff Erickson, Stefan Langerman
Given a polyhedron P in R with n vertices, a halfspace volume query asks for the volume of P H for a given halfspace H. We show that, for d 3, such queries can require# n) operations even if the...
Reza Abedi, Shuo-heng Chung, Jeff Erickson, Yong Fan, Michael Garl, Damrong Guoy, ...
We propose a new algorithm for constructing finite-element meshes suitable for spacetime discontinuous Galerkin solutions of linear hyperbolic PDEs. Given a triangular mesh of some planar domain Ω...
David Bremner, Erik Demaine, Jeff Erickson, John Iacono, Stefan Langerman, Pat Morin, ...
Computer Science Department, University of Illinois,
Rips complexes of planar point sets (2007)
Erin W. Chambers, Vin De Silva, Jeff Erickson, Robert Ghrist
ABSTRACT. Fix a finite set of points in Euclidean n-space E n, thought of as a point-cloud sampling of a certain domain D ⊂ E n. The Rips complex is a combinatorial simplicial complex based on...
Rips complexes of planar point sets (2007)
Erin W. Chambers, Vin De Silva, Jeff Erickson, Robert Ghrist
ABSTRACT. Fix a finite set of points in Euclidean n-space E n, thought of as a point-cloud sampling of a certain domain D ⊂ E n. The Rips complex is a combinatorial simplicial complex based on...
WALKING YOUR DOG IN THE WOODS IN POLYNOMIAL TIME 1 (2007)
Erin Wolf Chambers, Éric Colin, De Verdière, Jeff Erickson, Sylvain Lazard, Francis Lazarus, ...
Abstract. 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,...
Minimum-Cost Coverage of Point Sets by Disks (2006)
Arkin, Esther M., Broennimann, Herve, Erickson, Jeff, Fekete, Sandor P., Knauer, Christian, Lenchner, Jonathan, ...
We consider a class of geometric facility location problems in which the goal is to determine a set X of disks given by their centers (t_j) and radii (r_j) that cover a given set of demand points Y...
Splitting (Complicated) Surfaces is Hard (2006)
Chambers, Erin, Colin De Verdière, Éric, Erickson, Jeff, Lazarus, Francis, Whittlesey, Kim
Let $\MM$ be an orientable combinatorial surface without boundary. A cycle on $\MM$ is \emph{splitting} if it has no self-intersections and it partitions $\MM$ into two components, neither of which...
Splitting (Complicated) Surfaces is Hard (2006)
Chambers, Erin, Colin De Verdière, Éric, Erickson, Jeff, Lazarus, Francis, Whittlesey, Kim
Let $\MM$ be an orientable combinatorial surface without boundary. A cycle on $\MM$ is \emph{splitting} if it has no self-intersections and it partitions $\MM$ into two components, neither of which...
Splitting (Complicated) Surfaces is Hard (2006)
Chambers, Erin, Colin De Verdière, Éric, Erickson, Jeff, Lazarus, Francis, Whittlesey, Kim
Let $\MM$ be an orientable combinatorial surface without boundary. A cycle on $\MM$ is \emph{splitting} if it has no self-intersections and it partitions $\MM$ into two components, neither of which...
Splitting (Complicated) Surfaces is Hard (2006)
Chambers, Erin, Colin De Verdière, Éric, Erickson, Jeff, Lazarus, Francis, Whittlesey, Kim
Let $\MM$ be an orientable combinatorial surface without boundary. A cycle on $\MM$ is \emph{splitting} if it has no self-intersections and it partitions $\MM$ into two components, neither of which...
Minimum-cost coverage of point sets by disks (2006)
Helmut Alt, Esther M. Arkin, Hervé Brönnimann, Jeff Erickson, Sándor P. Fekete, Christian Knauer, ...
We consider a class of geometric facility location problems in which the goal is to determine a set X of disks given by their centers (t j) and radii (r j) that cover a given set of demand points Y...
Distance-2 Edge Coloring is NP-Complete (2005)
Erickson, Jeff, Thite, Shripad, Bunde, David P.
We prove that it is NP-complete to determine whether there exists a distance-2 edge coloring (strong edge coloring) with 5 colors of a bipartite 2-inductive graph with girth 6 and maximum degree 3.
Realizing partitions respecting full and partial order information (2005)
Demaine, E., Erickson, Jeff, Krizanc, D., Meijer, H., Morin, P., Overmars, M.H., ...
Meshing in 2D×time for front-tracking DG methods (2005)
Shripad Thite, Jeff Erickson, Shuo-heng Chung, Reza Abedi Jay
Spacetime discontinuous Galerkin (SDG) finite element methods are used to solve hyperbolic PDEs describing wavelike phenomena, such as fluid flow. In front-tracking SDG methods, the inclined facets...
Greedy optimal homotopy and homology generators (2005)
Abstract We describe simple greedy algorithms to construct the shortest set of loops that generates either the fundamental group (with a given basepoint) or the first homology group (over any fixed...
Adaptive spacetime meshing in 2D×time for nonlinear and anisotropic media (2005)
Shripad Thite, Shuo-heng Chung, Jeff Erickson, Robert Haber
Scientists and engineers use hyperbolic partial differential equations (PDEs) to model wave propagation phenomena. Anisotropy of the transmitting medium can cause waves to propagate asymmetrically,...
Separating point sets in polygonal environments (2004)
Erik D. Demaine, Jeff Erickson, Ferran Hurtado, John Iacono, Stefan Langerman, Henk Meijer, ...
We consider the separability of two point sets inside a polygon by means of chords or geodesic lines. Specifically, given a set of red points and a set of blue points in the interior of a polygon, we...
Adaptive discontinuous galerkin method for elastodynamics on unstructured spacetime grids (2004)
Reza Abedi, Shuo-heng Chung, Yong Fan, Shripad Thite, Jeff Erickson, Robert B. Haber
Summary We present an adaptive spacetime discontinuous Galerkin (SDG) method for linearized elastodynamics. The SDG method uses a simple Bubnov-Galerkin projection that delivers stable and...
On the least median square problem (2004)
Jeff Erickson, Sariel Har-peled, David M. Mount
We consider the exact and approximate computational complexity of the multivariate LMS linear regression estimator. The LMS estimator is among the most widely used robust linear statistical...
Separating point sets in polygonal environments (2004)
Erik D. Demaine, Jeff Erickson, Ferran Hurtado, John Iacono, Stefan Langerman, Henk Meijer, ...
We consider the separability of two point sets inside a polygon by means of chords or geodesic lines. Specifically, given a set of red points and a set of blue points in the interior of a polygon, we...
On the least median square problem (2004)
Jeff Erickson, Sariel Har-peled, David M. Mount
We consider the exact and approximate computational complexity of the multivariate LMS linear regression estimator. The LMS estimator is among the most widely used robust linear statistical...
Efficient tradeoff schemes in data structures for querying moving objects (2004)
Pankaj K. Agarwal, Lars Arge, Jeff Erickson, Hai Yu
The ability to represent and query continuously moving objects is important in many applications of spatio-temporal database systems. In this paper we develop data structures for answering various...
Separating point sets in polygonal environments (2004)
Erik D. Demaine, Jeff Erickson, Ferran Hurtado, John Iacono, Stefan Langerman, Henk Meijer, ...
We consider the separability of two point sets inside a polygon by means of chords or geodesic lines. Specifically, given a set of red points and a set of blue points in the interior of a polygon, we...
Capturing a convex object with three discs (2003)
Jeff Erickson, Shripad Thite, Fred Rothganger, Jean Ponce
Abstract — This paper addresses the problem of capturing an arbitrary convex object P in the plane with three congruent discshaped robots. Given two stationary robots in contact with P, we...
Local polyhedra and geometric graphs (2003)
We introduce a new realistic input model for geometric graphs and nonconvex polyhedra. A geometric graph G is local if (1) the longest edge at every vertex v is only a constant factor longer than the...
Local Polyhedra and Geometric Graphs (2003)
We introduce a new realistic input model for geometric graphs and nonconvex polyhedra.
Uniform Samples of Generic Surfaces Have Nice Delaunay Triangulations (2003)
Have Nice, Delaunay Triangulations, Jeff Erickson
Let Σ be a fixed smooth surface in R³, such that no medial ball touches Σ more than four times, counting with multiplicity, or more than three times at any single point....
Optimally cutting a surface into a disk (2002)
Erickson, Jeff, Har-Peled, Sariel
We consider the problem of cutting a set of edges on a polyhedral manifold surface, possibly with boundary, to obtain a single topological disk, minimizing either the total number of cut edges or...
Building Space-Time Meshes over Arbitrary Spatial Domains (2002)
Erickson, Jeff, Guoy, Damrong, Sullivan, John M., Üngör, Alper
We present an algorithm to construct meshes suitable for space-time discontinuous Galerkin finite-element methods. Our method generalizes and improves the `Tent Pitcher' algorithm of \"Ung\"or and...
Preprocessing Chains for Fast Dihedral Rotations Is Hard or Even Impossible (2002)
Soss, Michael, Erickson, Jeff, Overmars, Mark
We examine a computational geometric problem concerning the structure of polymers. We model a polymer as a polygonal chain in three dimensions. Each edge splits the polymer into two subchains, and a...
Flat-state connectivity of linkages under dihedral motions (2002)
Greg Aloupis, Erik D. Demaine, Vida Dujmović, Jeff Erickson, Stefan Langerman, Henk Meijer, ...
Abstract. We explore which classes of linkages have the property that each pair of their flat states—that is, their embeddings in R 2 without self-intersection—can be connected by a continuous...
Building space-time meshes over arbitrary spatial domains (2002)
Jeff Erickson, Damrong Guoy, John M. Sullivan, Alper Ongsr
We present an algorithm to construct meshes suitable for space-time discontinuous Galerkin finite-element methods. Our method generalizes and improves the 'Tent Pitcher ' algorithm of...
Optimally cutting a surface into a disk (2002)
Jeff Erickson, Sariel Har-peled
We consider the problem of cutting a set of edges on a polyhedral manifold surface, possibly with boundary, to obtain a single topological disk, minimizing either the total number of cut edges or...
Optimally Cutting a Surface into a Disk (2002)
Jeff Erickson, Sariel Har-peled
We consider the problem of cutting a set of edges on a polyhedral manifold surface, possibly with boundary, to obtain a single topological disk, minimizing either the total number of cut edges or...
Uniform Samples of Generic Surfaces Have Nice Delaunay Triangulations (2002)
Have Nice, Delaunay Triangulations, Jeff Erickson
Let # be a fixed smooth surface in IR , such that no medial ball touches # more than four times, counting with multiplicity, or more than three times at any single point.
Preprocessing chains for fast dihedral rotations is hard or even impossible (2002)
Michael Soss, Jeff Erickson, Mark Overmars
We examine a computational geometric problem concerning the structure of polymers. We model a polymer as a polygonal chain in three dimensions. Each edge splits the polymer into two subchains, and a...
Flat-state connectivity of linkages under dihedral motions (2002)
Greg Aloupis, Erik D. Demaine, Jeff Erickson, Stefan Langerman, Henk Meijer, Mark Overmars, ...
Abstract. We explore which classes of linkages have the property that each pair of their flat states--that is, their embeddings in R2 without self-intersection--can be connected by a continuous...
Dense point sets have sparse Delaunay triangulations (2002)
The spread of a finite set of points is the ratio between the longest and shortest pairwise distances. We prove that the Delaunay triangulation of any set of n points in R 3 with spread ∆ has...
Building space-time meshes over arbitrary spatial domains (2002)
Jeff Erickson, Damrong Guoy, John M. Sullivan, Alper Üngör
We present an algorithm to construct meshes suitable for spacetime discontinuous Galerkin finite-element methods. Our method generalizes and improves the ‘Tent Pitcher ’ algorithm of Üngör and...
Preprocessing chains for fast dihedral rotations is hard or even impossible (2002)
Michael Soss, Jeff Erickson, Mark Overmars
We examine a computational geometric problem concerning the structure of polymers. We model a polymer as a polygonal chain in three dimensions. Each edge splits the polymer into two subchains, and a...
Optimally cutting a surface into a disk (2002)
Jeff Erickson, Sariel Har-peled
We consider the problem of cutting a subset of the edges of a polyhedral manifold surface, possibly with boundary, to obtain a single topological disk, minimizing either the total number of cut edges...
Optimally cutting a surface into a disk (2002)
Jeff Erickson, Sariel Har-peled
We consider the problem of cutting a set of edges on a polyhedral manifold surface, possibly with boundary, to obtain a single topological disk, minimizing either the total number of cut edges or...
Flat-State Connectivity of Linkages under Dihedral Motions (2002)
Greg Aloupis, Erik D. Demaine, Vida Dujmovic, Jeff Erickson, Stefan Langerman, Henk Meijer, ...
We explore which classes of linkages have the property that each pair of their at states|that is, their embeddings in R without self-intersection|can be connected by a continuous dihedral motion that...
Building Spacetime Meshes over Arbitrary Spatial Domains (2002)
Je Erickson Damrong, Jeff Erickson, Damrong Guoy, John M. Sullivan, Alper Üngör
We present an algorithm to construct meshes suitable for spacetime discontinuous Galerkin finite-element methods. Our method generalizes and improves the `Tent Pitcher' algorithm of Ungor and...
Vertex-Unfoldings of Simplicial Manifolds (2001)
Demaine, Erik D., Eppstein, David, Erickson, Jeff, Hart, George W., O'Rourke, Joseph
We present an algorithm to unfold any triangulated 2-manifold (in particular, any simplicial polyhedron) into a non-overlapping, connected planar layout in linear time. The manifold is cut only along...
Dense point sets have sparse Delaunay triangulations (2001)
The spread of a finite set of points is the ratio between the longest and shortest pairwise distances. We prove that the Delaunay triangulation of any set of n points in R^3 with spread D has...
Flipping Cubical Meshes (2001)
Bern, Marshall, Eppstein, David, Erickson, Jeff
We define and examine flip operations for quadrilateral and hexahedral meshes, similar to the flipping transformations previously used in triangular and tetrahedral mesh generation.
Vertex-Unfoldings of Simplicial Polyhedra (2001)
Demaine, Erik D., Eppstein, David, Erickson, Jeff, Hart, George W., O'Rourke, Joseph
We present two algorithms for unfolding the surface of any polyhedron, all of whose faces are triangles, to a nonoverlapping, connected planar layout. The surface is cut only along polyhedron edges....
Arbitrarily Large Neighborly Families of Congruent Symmetric Convex 3-Polytopes (2001)
We construct, for any positive integer n, a family of n congruent convex polyhedra in R^3, such that every pair intersects in a common facet. Previously, the largest such family contained only eight...
Nice point sets can have nasty Delaunay triangulations (2001)
We consider the complexity of Delaunay triangulations of sets of points in R^3 under certain practical geometric constraints. The spread of a set of points is the ratio between the longest and...
Nice point sets can have nasty Delaunay triangulations (2001)
ht tp://www.cs.uiuc.edu/~j effe
Arbitrarily large neighborly families of congruent symmetric convex 3-polytopes (2001)
We construct, for any positive integer n, a family of n congruent convex polyhedra in IR 3 such that every pair intersects in a common facet. Previously, the largest such family contained only eight...
Vertex-unfoldings of simplicial polyhedra (2001)
Erik D. Demaine, Jeff Erickson
We present two algorithms for unfolding the surface of any polyhedron, all of whose faces are triangles, to a nonoverlapping, connected planar layout. The surface is cut only along polyhedron edges....
Flipping Cubical Meshes (2001)
Marshall Bern David, Jeff Erickson
We define and examine flip operations for quadrilateral and hexahedral meshes, similar to the flipping transformations previously used in triangular and tetrahedral mesh generation.
Aichholzer, Oswin, Cortes, Carmen, Demaine, Erik D., Dujmovic, Vida, Erickson, Jeff, Meijer, Henk, ...
A flipturn is an operation that transforms a nonconvex simple polygon into another simple polygon, by rotating a concavity 180 degrees around the midpoint of its bounding convex hull edge. Joss and...
Aichholzer, O., Cortes, C., Demaine, E.D., Dujmovic, V., Erickson, Jeff, Meijer, H., ...
A flipturn is an operation that transforms a nonconvex simple polygon into another simple polygon, by rotating a concavity 180 degrees around the midpoint of its bounding convex hull edge Joss and...
Reconfiguring convex polygons (2000)
Aichholzer, O., Demaine, E.D., Erickson, Jeff, Hurtado, F., Overmars, M.H., Soss, M., ...
We prove that there is a motion from any convex polygon to any convex polygon with the same counterclockwise sequence of edge lengths, that preserves the lengths of the edges, and keeps the polygon...
Space-Time Tradeoffs for Emptiness Queries (Extended Abstract) (2000)
We present the first nontrivial space-time tradeoff lower bounds for hyperplane and halfspace emptiness queries. Our lower bounds apply to a general class of geometric range query data structures...
Reconfiguring Convex Polygons (2000)
Oswin Aichholzer Erik, Erik D. Demaine, Jeff Erickson, Ferran Hurtado, Mark Overmars, Michael A. Soss, ...
. We prove that there is a motion from any convex polygon to any convex polygon with the same counterclockwise sequence of edge lengths, that preserves the lengths of the edges, and keeps the polygon...
Pankaj K. Agarwal, Lars Arge, Jeff Erickson
) Pankaj K. Agarwal Lars Arge y Jeff Erickson z Submitted to 19th ACM Symposium on Principles of Database Systems. November 8, 1999 Abstract We propose three indexing schemes for storing a set S of N...
Reconfiguring Convex Polygons (2000)
Oswin Aichholzer, Erik D. Demaine, Jeff Erickson, Ferran Hurtado, Mark Overmars, Michael A. Soss, ...
. We prove that there is a motion from any convex polygon to any convex polygon with the same counterclockwise sequence of edge lengths, that preserves the lengths of the edges, and keeps the polygon...
Finite-resolution hidden surface removal (1999)
We propose a hybrid image-space/object-space solution to the classical hidden surface removal problem: Given n disjoint triangles in Real^3 and p sample points (``pixels'') in the xy-plane, determine...
Geometric Approximation Algorithms and Randomized Algorithms for Planar Arrangements (1999)
Prof Micha Sharir, Hervé Brönnimann, Bernard Chazelle, Ken Clarkson, Alon Efrat, Jeff Erickson, ...
by
Kinetic collision detection between two simple polygons (1999)
Julien Basch, Jeff Erickson, Leonidas J. Guibas, John Hershberger, Li Zhang
We design a kinetic data structure for detecting collisions between two simple polygons in motion. In order to do so, we create a planar subdivision of the free space between the two polygons, called...
The straight skeleton of a polygon is a variant of the medial axis, introduced by Aichholzer et al., defined by a shrinking process in which each edge of the polygon moves inward at a fixed rate. We...
New lower bounds for convex hull problems in odd dimensions (1999)
Abstract. We show that in the worst case,\Omega\Gamma n dd=2e\Gamma1 +n log n) sidedness queries are required to determine whether the convex hull of n points in IR d is simplicial, or to determine...
The straight skeleton of a polygon is a variant of the medial axis introduced by Aichholzer et al., defined by a shrinking process in which each edge of the polygon moves inward at a fixed rate. We...
Separation-Sensitive Collision Detection for Convex Objects (1999)
Jeff Erickson, Leonidas J. Guibas, Jorge Stolfi, Li Zhang
We develop a class of new kinetic data structures for collision detection between moving convex polytopes; the performance of these structures is sensitive to the separation of the polytopes during...
Geometric Range Searching and Its Relatives (1999)
Pankaj K. Agarwal, Jeff Erickson
From a theoretical point of view, range searching is now almost completely solved. The impact of general techniques developed for geometric range searching -- e-nets, 1/r cuttings, partition trees,...
New Lower Bounds for Convex Hull Problems in Odd Dimensions (1999)
We show that in the worst case,## n #d/2#-1 +n log n) sidedness queries are required to determine whether the convex hull of n points in R^d is simplicial or to determine the number of convex hull...
Geometric Range Searching and Its Relatives (1999)
Pankaj K. Agarwal, Jeff Erickson
. 1. Introduction HW Cl, Cl2 CS Pankaj K. Agarwal and Jeff Erickson Geometric Range Searching and Its Relatives Contemporary Mathematics c 0000 (copyright holder) Mathematics Subject Classification....
Kinetic Collision Detection Between Two Simple Polygons (1999)
Julien Basch, Jeff Erickson, Leonidas J. Guibas, John Hershberger, Li Zhang
MS-9627683 and by U.S. Army Research Office MURI grant DAAH04-96-1-0013. z Computer Science Department, Stanford University, Stanford, CA 94305; guibas@cs.stanford.edu. Research partially supported...
Kinetic collision detection between two simple polygons (1999)
Julien Basch, Jeff Erickson, Leonidas J. Guibas, John Hershberger, Li Zhang
We design a kinetic data structure for detecting collisions between two simple polygons in motion. In order to do so, we create a planar subdivision of the free space between the two polygons, called...
Kinetic collision detection between two simple polygons (1999)
Julien Basch, Jeff Erickson, Leonidas J. Guibas, John Hershberger, Li Zhang
We design a kinetic data structure for detecting collisions between two simple polygons in motion. In order to do so, we create a planar subdivision of the free space between the two polygons, called...
Separation-Sensitive Collision Detection for Convex Objects (1998)
Erickson, Jeff, Guibas, Leonidas J., Stolfi, Jorge, Zhang, Li
We develop a class of new kinetic data structures for collision detection between moving convex polytopes; the performance of these structures is sensitive to the separation of the polytopes during...
Kinetic Binary Space Partitions for Intersecting Segments and Disjoint Triangles (1998)
Pankaj K. Agarwal, Jeff Erickson, Leonidas J. Guibas
) Pankaj K. Agarwal Jeff Erickson y Leonidas J. Guibas z Abstract We describe randomized algorithms for efficiently maintaining a binary space partition of continuously moving, possibly intersecting,...
Efficient Searching with Linear Constraints (Extended Abstract) (1998)
Pankaj K. Agarwal, Lars Arge, Jeff Erickson, Paolo G. Franciosa, Jeffrey Scott Vitter
We show how to preprocess a set S of points in R d into an external memory data structure that efficiently supports linear-constraint queries. Each query is in the form of a linear constraint a...
Efficient Searching with Linear Constraints (1998)
Pankaj K. Agarwal, Lars Arge, Jeff Erickson, Paolo G. Franciosa, Jeffrey Scott Vitter
We show how to preprocess a set S of points in R d into an external memory data structure that efficiently supports linear-constraint queries. Each query is in the form of a linear constraint x d a 0...
Space-Time Tradeoffs for Emptiness Queries (1998)
We develop the first nontrivial lower bounds on the complexity of online hyperplane and halfspace emptiness queries. Our lower bounds apply to a general class of geometric range query data structures...
The straight skeleton of a polygon is a variant of the medial axis, introduced by Aichholzer et al., defined by a shrinking process in which each edge of the polygon moves inward at a fixed rate. We...
Geometric Range Searching and Its Relatives (1997)
Pankaj K. Agarwal, Pankaj K. Agarwal, Jeff Erickson, Jeff Erickson
this paper was supported by National Science Foundation Grant CCR93 -01259, by Army Research Office MURI grant DAAH04-96-1-0013, by a Sloan fellowship, by an NYI award and matching funds from Xerox...
Efficient Searching with Linear Constraints (1997)
Pankaj Agarwal Lars, Lars Arge, Jeff Erickson, Paolo G. Franciosa, Jeffrey Scott Vitter
We show how to preprocess a set S of points in R d into an external memory data structure that efficiently supports linear-constraint queries. Each query is in the form of a linear constraint x d a 0...
Space-Time Tradeoffs for Emptiness Queries (1997)
We develop the first nontrivial lower bounds on the complexity of online hyperplane and halfspace emptiness queries. Our lower bounds apply to a general class...
Efficient Searching with Linear Constraints (1997)
Pankaj K. Agarwal, Lars Arge, Jeff Erickson, Paolo G. Franciosa, Jeffrey Scott Vitter
We show how to preprocess a set S of points in R^d into an external memory....
Efficient Searching with Linear Constraints (1997)
Pankaj K. Agarwal, Lars Arge, Jeff Erickson, Paolo G. Franciosa, Jeffrey Scott Vitter
We show how to preprocess a set S of points in R d into an external memory data structure that efficiently supports linear-constraint queries. Each query is in the form of a linear constraint x d a 0...
Space-Time Tradeoffs for Emptiness Queries (1997)
We develop the first nontrivial lower bounds on the complexity of online hyperplane and halfspace emptiness queries. Our lower bounds apply to a general class of geometric range query data structures...
Lower Bounds for Linear Satisfiability Problems (1997)
We prove an \Omega\Gamma n dr=2e ) lower bound for the following problem: For some fixed linear equation in r variables, given n real numbers, do any r of them satisfy the equation? Our lower bound...
New Toads and Frogs results (1996)
Abstract. We present a number of new results for the combinatorial game Toads and Frogs. We begin by presenting a set of simplification rules, which allow us to split positions into independent...
New Lower Bounds for Convex Hull Problems in Odd Dimensions (1996)
We show that in the worst case,\Omega n dd=2e;1 +n log n) sidedness queries are required to determine whether the convex hull of n points in IR d is simplicial, or to determine the numberofconvex...
New Lower Bounds for Convex Hull Problems in Odd Dimensions (1996)
We show that in the worst case,\Omega\Gamma n dd=2e\Gamma1 +n log n) sidedness queries are required to determine whether the convex hull of n points in IR d is simplicial, or to determine the number...
New Lower Bounds for Halfspace Emptiness (1996)
We derive a lower bound of\Omega\Gamma n 4=3 ) for the halfspace emptiness problem: Given a set of n points and n hyperplanes in IR 5 , is every point above every hyperplane? This matches the best...
At the Workshop, John Conway and Richard Guy proposed the class of "sowing games", loosely based on the ancient African games Mancala and Wari, as an object of study in combinatorial game...
Lower Bounds for Fundamental Geometric Problems (Bibliography) (1996)
Jeff Erickson, Tarjan Robert, Tarski Alfred
Pach, J'anos, 7, 106 Pal'asti, Ilona, 22 partition graph, 81 as a range searching data structure, 107 level of node in, 82 polyhedral, 102 primal and dual edges, 84 primal and dual nodes,...
Errata: Better Lower Bounds on Detecting Affine and Spherical Degeneracies (1996)
Jeff Erickson, Raimund Seidel, Fachbereich Informaik
disjoint from every other surface induced by \Phi. The correctness of the perturbation technique is based on the following incorrect claim [1, p.48]: Let C be an arbitrary cell, and let C 0 be one of...
. At the Workshop, John Conway and Richard Guy proposed the class of "sowing games", loosely based on the ancient African games Mancala and Wari, as an object of study in combinatorial game...
New Lower Bounds for Hopcroft's Problem (1996)
We establish new lower bounds on the complexity of the following basic geometric problem, attributed to John Hopcroft: Given a set of n points and m hyperplanes in IR d ,isany pointcontained in...
New Lower Bounds for Halfspace Emptiness (1996)
We derive a lower bound of\Omega n 4=3 ) for the halfspace emptiness problem: Given a set of n points and n hyperplanes in IR 5 , is every point above every hyperplane ? This matches the best known...
New Toads and Frogs Results (1996)
. We present a number of new results for the combinatorial game Toads and Frogs. We begin by presenting a set of simplification rules, which allow us to split positions into independent components or...
New Lower Bounds for Hopcroft's Problem (1996)
We establish new lower bounds on the complexity of the following basic geometric problem, attributed to John Hopcroft: Given a set of n points and m hyperplanes in IR d , is any point contained in...
New Lower Bounds for Halfspace Emptiness (1996)
this paper will appear in the proceedings of the 37th FOCS. The paper is also available via the Web at "http://www.cs.duke.edu/
On the Relative Complexities of Some Geometric Problems (1995)
We consider the relative complexities of a large number of computational geometry problems whose complexities are believed to be roughly \Theta(n 4=3 ). For certain pairs of problems, we show that...
Better Lower Bounds on Detecting Affine and Spherical Degeneracies (1995)
We show that in the worst case,\Omega (n d ) sidedness queries are required to determine whether a set of n points in IR d is affinely degenerate, i.e., whether it contains d +1points on a common...
Better Lower Bounds on Detecting Affine and Spherical Degeneracies (1995)
We show that in the worst case,\Omega\Gamma n d ) sidedness queries are required to determine whether a set of n points in IR d is affinely degenerate, i.e., whether it contains d + 1 points on a...
New Lower Bounds for Convex Hull Problems in Odd Dimensions (Extended Abstract) (1995)
) Jeff Erickson Computer Science Division University of California Berkeley, CA 94720-1776 jeffe@cs.berkeley.edu Preliminary draft --- 10/14/95 --- Not for distribution Abstract We show that in the...
Iterated Nearest Neighbors and Finding Minimal Polytopes (1994)
We introduce a new method for finding several types of optimal k-point sets, minimizing perimeter, diameter, circumradius, and related measures, by testing sets of the O(k) nearest neighbors to each...
Separation-Sensitive Collision Detection for Convex Objects
Jeff Erickson, Leonidas J. Guibas, Jorge Stolfi, Li Zhang
this paper, see http://www:uiuc:edu/ph/www/jee/pubs/kollide:html.