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...
Nonnumerical Algorithms and Problems – geometrical (2009)
We present the first polynomial-time algorithm for computing the Fréchet distance for a non-trivial class of surfaces: simple polygons. For this, we show that it suffices to consider homeomorphisms...
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...
Delaunay Triangulations in Linear Time? (Part I) (2008)
We present a new and simple randomized algorithm for constructing the Delaunay triangulation using nearest neighbor graphs for point location. It runs in linear expected time for points in the plane...
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...
Acyclic Orientation of Drawings ⋆ (2008)
Eyal Ackerman, Kevin Buchin, Christian Knauer, Günter Rote
Abstract. Given a set of curves in the plane or a topological graph, we ask for an orientation of the curves or edges which induces an acyclic orientation on the corresponding planar map. Depending...
Kevin Buchin, Simon Plantinga, Günter Rote, Astrid Sturm, Gert Vegter
Project co-funded by the European Commission within FP6 (2002–2006) under contract nr. IST-006413 Given points in convex position in three dimensions, we want to find an approximating convex...
Minimizing the Maximum Interference is Hard (2008)
We consider the following interference model for wireless sensor and ad hoc networks: the receiver interference of a node is the number of transmission ranges it lies in. We model transmission ranges...
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...
Recursive geometry of the flow complex and topology of the flow complex filtration (2008)
Buchin, Kevin, Dey, Tamal K., Giesen, Joachim, John, Matthias
Hatching, Stroke Styles Pointillism (2007)
Kevin Buchin And, Stroke Styles, Kevin Buchin, Maike Walther
Introduction Hatching is a common technique used in Non-Photorealistic Rendering (NPR). For hatching, series of strokes are combined into textures. These compositions of strokes can convey the...
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...
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,...
There are not too many Magic Configurations (2007)
Eyal Ackerman, Kevin Buchin, Christian Knauer, Rom Pinchasi, Günter Rote
A finite planar point set P is called a magic configuration if there is an assignment of positive weights to the points of P such that, for every line l determined by P, the sum of the weights of all...
There are not too many Magic Configurations (2007)
Eyal Ackerman, Kevin Buchin, Christian Knauer, Rom Pinchasi, Günter Rote
A finite planar point set P is called a magic configuration if there is an assignment of positive weights to the points of P such that, for every line l determined by P, the sum of the weights of all...
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
Abstract Acyclic Orientation of Drawings ∗ (2006)
Eyal Ackerman, Kevin Buchin, Christian Knauer, Günter Rote
Given a set of curves in the plane or a topological graph, we ask for an orientation of the curves or edges which induces an acyclic orientation on the corresponding planar map. Depending on the...
Convex Approximation by Spherical Patches (2006)
Kevin Buchin, Simon Plantinga, Günter Rote, Astrid Sturm, Gert Vegter
3 Partially supported by the IST Programme of the EU as a Shared-cost RTD (FET Open) Project under Contract No IST-006413 (ACS – Algorithms for Complex Shapes) Given points in convex position in...
Real-Time Per-Pixel Rendering with Stroke Textures (2003)
For stroke-based renderings, stroke textures are composed of individual strokes in order to cover surface regions. In this paper, we present a real-time rendering technique based on stroke textures...
Minimizing the Maximum Interference is Hard
We consider the following interference model for wireless sensor and ad hoc networks: the receiver interference of a node is the number of transmission ranges it lies in. We model transmission ranges...