6 citations · 14 across the 6 of their papers we have counts for
13 papers
Geometric Embeddability of Complexes is -complete
Mikkel Abrahamsen, Linda Kleist, Tillmann Miltzow
We show that the decision problem of determining whether a given (abstract simplicial) -complex has a geometric embedding in is complete for the Existential Theory…
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…
Local Complexity of Polygons
Fabian Klute, Meghana M. Reddy, Tillmann Miltzow
Many problems in Discrete and Computational Geometry deal with simple polygons or polygonal regions. Many algorithms and data-structures perform considerably faster, if the underly…
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…
Maximum Clique in Disk-Like Intersection Graphs
Édouard Bonnet, Nicolas Grelier, Tillmann Miltzow
We study the complexity of Maximum Clique in intersection graphs of convex objects in the plane. On the algorithmic side, we extend the polynomial-time algorithm for unit disks [Cl…
Dynamic Toolbox for ETRINV
Mikkel Abrahamsen, Tillmann Miltzow
Recently, various natural algorithmic problems have been shown to be -complete. The reduction relied in many cases on the -completeness of t…