Publications (37)
Planar and Toroidal Morphs Made Easier
Jeff Erickson, Patrick Lin
We present simpler algorithms for two closely related morphing problems, both based on the barycentric interpolation paradigm introduced by Floater and Gotsman, which is in turn ba…
Shelling and Sinking Graphs on the Sphere
Jeff Erickson, Christian Howard
We describe a promising approach to efficiently morph spherical graphs, extending earlier approaches of Awartani and Henderson [Trans. AMS 1987] and Kobourov and Landis [JGAA 2006]…
Chasing Puppies: Mobile Beacon Routing on Closed Curves
Mikkel Abrahamsen, Jeff Erickson, Irina Kostitsyna +5
We solve an open problem posed by Michael Biro at CCCG 2013 that was inspired by his and others' work on beacon-based routing. Consider a human and a puppy on a simple closed curve…
Recognizing Weakly Simple Polygons
Hugo Akitaya, Greg Aloupis, Jeff Erickson +1
We present an -time algorithm that determines whether a given planar -gon is weakly simple. This improves upon an -time algorithm by Chang, Erickson, a…
Holiest Minimum-Cost Paths and Flows in Surface Graphs
Jeff Erickson, Kyle Fox, Luvsandondov Lkhamsuren
Let be an edge-weighted directed graph with vertices embedded on an orientable surface of genus . We describe a simple deterministic lexicographic perturbation scheme th…
Vertex-Unfoldings of Simplicial Manifolds
Erik D. Demaine, David Eppstein, Jeff Erickson +2
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 manifol…