Computing Sciences Universiteit Utrecht (2009)
Noga Alon, Maike Buchin, Bettina Speckmann, Tu Eindhoven, Robert Berke, Péter Csorba, ...
We show that the vertices of any plane graph in which every face is of size at least g can be colored by ⌊(3g − 5)/4⌋ colors so that every color appears in every face. This is nearly tight, as...
Drawing (complete) binary tanglegrams: Hardness, approximation, fixed-parameter tractability (2009)
Buchin, Kevin, Buchin, Maike, Byrka, Jaroslaw, Nullenburg, Martin, Okamoto, Yoshio, Silveira, Rodrigo I., ...
A binary tanglegram is a pair (S, T) of binary trees whose leaf sets are in one-to-one correspondence; matching leaves are connected by inter-tree edges. For applications, for example in...
Abstract How Difficult is it to Walk the Dog? (2008)
Kevin Buchin, Maike Buchin, Christian Knauer, Günter Rote, Carola Wenk
We study the complexity of computing the Fréchet distance (also called dog-leash distance) between two polygonal curves with a total number of n vertices. For two polygonal curves in the plane we...
Drawing (Complete) Binary Tanglegrams: Hardness, Approximation, Fixed-Parameter Tractability (2008)
Buchin, Kevin, Buchin, Maike, Byrka, Jaroslaw, Nöllenburg, Martin, Okamoto, Yoshio, Silveira, Rodrigo I., ...
A \emph{binary tanglegram} is a pair $$ of binary trees whose leaf sets are in one-to-one correspondence; matching leaves are connected by inter-tree edges. For applications, for example in...
Detecting Commuting Patterns by Clustering Subtrajectories ∗ (2008)
Kevin Buchin, Maike Buchin, Joachim Gudmundsson, Maarten Löffler, K. Buchin, M. Buchin, ...
In this paper we consider the problem of detecting commuting patterns in a trajectory. For this we search for similar subtrajectories. To measure spatial similarity we choose the Fréchet distance...
We give lower bounds for the combinatorial complexity of the Voronoi diagram of polygonal curves under the discrete Frechet distance. We show that the Voronoi diagram of n curves in R^d with k...
Can we Compute the Similarity Between Surfaces? (2007)
A suitable measure for the similarity of shapes represented by parameterized curves or surfaces is the Fr\'echet distance. Whereas efficient algorithms are known for computing the Fr\'echet distance...
Polychromatic Colorings of Plane Graphs (2007)
Noga Alon, Robert Berke, Kevin Buchin, Maike Buchin, Péter Csorba, Saswata Shannigrahi, ...
We show that the vertices of any plane graph in which every face is of length at least g can be colored by ⌊(3g − 5)/4 ⌋ colors so that every color appears in every face. This is nearly tight,...
Computing the Fréchet Distance Between Simple Polygons (2007)
Kevin Buchin, Maike Buchin, Carola Wenk
We present the first polynomial-time algorithm for computing the Fréchet distance for a non-trivial class of surfaces: simple polygons, i.e., the area enclosed by closed simple polygonal curves,...
How Difficult is it to Walk the Dog (2007)
Kevin Buchin, Maike Buchin, Christian Knauer, Günter Rote, Carola Wenk
We study the complexity of computing the Fréchet distance (also called dog-leash distance) between two polygonal curves with a total number of n vertices. For two polygonal curves in the plane we...
How Difficult is it to Walk the Dog (2007)
Kevin Buchin, Maike Buchin, Christian Knauer, Günter Rote, Carola Wenk
We study the complexity of computing the Fréchet distance (also called dog-leash distance) between two polygonal curves with a total number of n vertices. For two polygonal curves in the plane we...
On rolling cube puzzles (2007)
Kevin Buchin, Maike Buchin, Erik D. Demaine, Martin L. Demaine, Dania El-khechen, Sándor P. Fekete, ...
We analyze the computational complexity of various rolling cube puzzles. 1