6 papers
Reconstructing Graphs from Connected Triples
Paul Bastide, Linda Cook, Jeff Erickson +4
We introduce a new model of indeterminacy in graphs: instead of specifying all the edges of the graph, the input contains all triples of vertices that form a connected subgraph. In…
Abstract morphing using the Hausdorff distance and Voronoi diagrams
Lex de Kogel, Marc van Kreveld, Jordi L. Vermeulen
This paper introduces two new abstract morphs for two -dimensional shapes. The intermediate shapes gradually reduce the Hausdorff distance to the goal shape and increase the Hau…
Approximating the Earth Mover's Distance between sets of geometric objects
Marc van Kreveld, Frank Staals, Amir Vaxman +1
Given two distributions and of equal total mass, the Earth Mover's Distance measures the cost of transforming one distribution into the other, where the cost of moving a un…
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…
Between Shapes, Using the Hausdorff Distance
Marc van Kreveld, Tillmann Miltzow, Tim Ophelders +2
Given two shapes and in the plane with Hausdorff distance , is there a shape with Hausdorff distance to and from and ? The answer is always yes, and dep…
Convex partial transversals of planar regions
Vahideh Keikha, Mees van de Kerkhof, Marc van Kreveld +6
We consider the problem of testing, for a given set of planar regions and an integer , whether there exists a convex shape whose boundary intersects at least region…