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,...
Walking Your Dog in the Woods in Polynomial Time (2008)
Erin W. Chambers, Éric Colin, Verdière Jeff, Erickson Sylvain Lazard, Francis Lazarus, Shripad Thite
Given two input curves, the Fréchet distance, sometimes called the dog-leash distance, between them is defined as the minimum length of a leash required to connect a dog and its owner as they walk...
SHORTEST VERTEX-DISJOINT TWO-FACE PATHS IN PLANAR GRAPHS (2008)
Éric Colin, De Verdi, Alexander Schrijver
Abstract. Let G be a directed planar graph of complexity n, each arc having a nonnegative length. Let s and t be two distinct faces of G; let s1,..., sk be vertices incident with s; let t1,..., tk be...
Optimal Pants Decompositions and Shortest Homotopic Cycles (2008)
Éric Colin, De Verdi Ère, Francis Lazarus
We consider the problem of finding a shortest cycle (freely) homotopic to a given simple cycle on a compact, orientable surface. For this purpose, we use a pants decomposition of the surface: a set...
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,...
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,...
Splitting (complicated) surfaces is hard (2006)
Erin W. Chambers, Éric Colin, Verdière Jeff, Erickson Francis, Lazarus Kim Whittlesey
Let M be an orientable surface without boundary. A cycle on M is splitting if it has no self-intersections and it partitions M into two components, neither homeomorphic to a disk. In other words,...
Splitting (complicated) surfaces is hard (2006)
Erin W. Chambers, Éric Colin, Verdière Jeff Erickson, Francis Lazarus, Kim Whittlesey
Let M be an orientable surface without boundary. A cycle on M is splitting if it has no self-intersections and it partitions M into two components, neither homeomorphic to a disk. In other words,...
Optimal system of loops on an orientable surface (2005)
Éric Colin, Verdière Francis Lazarus
Every compact orientable boundaryless surface M can be cut along simple loops with a common point v0, pairwise disjoint except at v0, so that the resulting surface is a topological disk; such a set...