8 papers
Segment Watchman Routes
Anna Brötzner, Omrit Filtser, Bengt J. Nilsson +2
Motivated by applications for robust guarding, we consider a variant of the multiple-watchmen problem that ensures that every point within a polygon is seen from more than one…
Minimum Exposure Motion Planning
Sarita de Berg, Joachim Gudmundsson, Peter Kramer +2
We investigate multiple fundamental variants of the classic coordinated motion planning (CMP) problem for unit square robots in the plane under the metric. In coordinated mot…
Sliding Cubes in Parallel
Hugo A. Akitaya, Joseph Dorfer, Peter Kramer +3
We study the classic sliding cube model for programmable matter under parallel reconfiguration in three dimensions, providing novel algorithmic and surprising complexity results in…
Structural Properties of Shortest Flip Sequences Between Plane Spanning Trees
Oswin Aichholzer, Joseph Dorfer, Peter Kramer +2
We study the reconfiguration of plane spanning trees on point sets in the plane in convex position, where a reconfiguration step (flip) replaces one edge with another, yielding aga…
Tilt Automata: Gathering Particles With Uniform External Control
Sándor P. Fekete, Jonas Friemel, Peter Kramer +3
Motivated by targeted drug delivery, we investigate the gathering of particles in the full tilt model of externally controlled motion planning: A set of particles is located at the…
Disproving two conjectures on the Hamiltonicity of Venn diagrams
Sofia Brenner, Linda Kleist, Torsten Mütze +2
In 1984, Winkler conjectured that every simple Venn diagram with curves can be extended to a simple Venn diagram with curves. His conjecture is equivalent to the statemen…