56 citations · 204 across the 25 of their papers we have counts for
19 papers · 1 filter
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…
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…
Optimal Curve Straightening is -Complete
Jeff Erickson
We prove that the following problem has the same computational complexity as the existential theory of the reals: Given a generic self-intersecting closed curve in the plane an…
Topologically Trivial Closed Walks in Directed Surface Graphs
Jeff Erickson, Yipu Wang
Let be a directed graph with vertices and edges, embedded on a surface , possibly with boundary, with first Betti number . We consider the complexity of finding c…
Lower Bounds for Electrical Reduction on Surfaces
Hsien-Chih Chang, Marcos Cossarini, Jeff Erickson
We strengthen the connections between electrical transformations and homotopy from the planar setting---observed and studied since Steinitz---to arbitrary surfaces with punctures.…
Untangling Planar Curves
Hsien-Chih Chang, Jeff Erickson
Any generic closed curve in the plane can be transformed into a simple closed curve by a finite sequence of local transformations called homotopy moves. We prove that simplifying a…