The directed Hausdorff distance between imprecise point sets (2009)
Knauer, Christian, Löffler, Maarten, Scherfenberg, Marc, Wolle, Thomas
We consider the directed Hausdorff distance between point sets in the plane, where one or both point sets consist of imprecise points. An imprecise point is modelled by a disc given by its centre and...
Fixed-parameter tractability and lower bounds for stabbing problems (2009)
Giannopoulos, Panos, Knauer, Christian, Rote, Gunter, Werner, Daniel
We study the following general stabbing problem from a parameterized complexity point of view: Given a set $\mathcal S$ of $n$ translates of an object in $\Rd$, find a set of $k$ lines with the...
Fixed-parameter tractability and lower bounds for stabbing problems (2009)
Giannopoulos, Panos, Knauer, Christian, Rote, Gunter, Werner, Daniel
We study the following general stabbing problem from a parameterized complexity point of view: Given a set $\mathcal S$ of $n$ translates of an object in $\Rd$, find a set of $k$ lines with the...
The parameterized complexity of some geometric problems in unbounded dimension (2009)
Giannopoulos, Panos, Knauer, Christian, Rote, Gunter, Werner, Daniel
We study the parameterized complexity of the following fundamental geometric problems with respect to the dimension $d$: i) Given $n$ points in $\Rd$, compute their minimum enclosing cylinder. ii)...
Computing k-Centers On a Line (2009)
Brass, Peter, Knauer, Christian, Na, Hyeon-Suk, Shin, Chan-Su, Vigneron, Antoine
In this paper we consider several instances of the k-center on a line problem where the goal is, given a set of points S in the plane and a parameter k >= 1, to find k disks with centers on a line l...
Shortest Inspection-Path Queries in Simple Polygons (2009)
Christian Knauer, Günter Rote, Lena Schlipf
Abstract. We want to preprocess a simple n-vertex polygon P to quickly determine the shortest path p from a fixed source point s ∈ P to view a set Q ⊆ P of query points (i.e., such that each...
On the Bounding Boxes Obtained by Principal Component Analysis (2008)
Darko Dimitrov, Christian Knauer, Klaus Kriegel, Günter Rote
Principle component analysis (PCA) is commonly used to compute a bounding box of a point set in R d. In this paper we give bounds on the approximation factor of PCA bounding boxes of convex polygons...
On the Bounding Boxes Obtained by Principal Component Analysis Abstract (2008)
Darko Dimitrov, Christian Knauer, Klaus Kriegel, Günter Rote
Principle component analysis (PCA) is a commonly used to compute a bounding box of a point set in R d. In this paper we give bounds on the approximation factor of PCA bounding boxes of convex...
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...
Sergio Cabello, Panos Giannopoulos, Christian Knauer, Günter Rote
We present an algorithm for the 3-center problem in (R d, L∞), i. e., for finding the smallest side length for 3 cubes that cover a given n-point set in R d, that runs in O(n log n) time for any...
Sergio Cabello, Panos Giannopoulos, Christian Knauer
Abstract We present an algorithm for the 3-center problem in (Rd, L1), i. e., for finding the smallest side length for 3 cubes that cover a given n-point set in Rd, that runs in O(n log n)time for...
doi:10.1093/comjnl/bxm053 Parameterized Complexity of Geometric Problems (2008)
Panos Giannopoulos, Christian Knauer, Sue Whitesides
This paper surveys parameterized complexity results for hard geometric algorithmic problems. It includes fixed-parameter tractable problems in graph drawing, geometric graphs, geometric covering and...
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...
Marc Benkert, Joachim Gudmundsson, Christian Knauer, Esther Moet, René Van Oostrum, Er Wolff
polynomial-time approximation algorithm for
Maximizing the Area of Overlap of two Unions of Disks under Rigid Motion ∗ (2008)
Mark Berg, Sergio Cabello, Panos Giannopoulos, Christian Knauer, René Oostrum, Remco C. Veltkamp
Let A and B be two sets of n resp. m disjoint unit disks in the plane, with m ≥ n. We consider the problem of finding a translation or rigid motion of A that maximizes the total area of overlap...
Computing the Hausdorff Distance of Geometric Patterns and Shapes Helmut Alt (2008)
Peter Braß, Michael Godau, Christian Knauer, Carola Wenk
A very natural distance measure for comparing shapes and patterns is the Hausdorff distance. In this article we develop algorithms for computing the Hausdorff distance in a very general case in which...
[10] H. Alt and M. Godau. Computing the Fréchet distance between two polygonal curves. (2008)
P. Agarwal, S. Har-peled, M. Sharir, H. Alt, K. Mehlhorn, H. Wagener, ...
for points, disks, and balls. Manuscript, 2002. [2] P. Agarwal and M. Sharir. Pipes, cigars, and kreplach: The union of Minkowski sums in three dimensions. Discrete Comput. Geom., 24:645–685, 2000....
Constructing Optimal Highways ∗ Hee-Kap Ahn † Helmut Alt ‡ Tetsuo Asano § Sang Won Bae (2008)
Peter Brass, Otfried Cheong, Christian Knauer, Hyeon-suk Na, Chan-su Shin
Rolf Klein, Christian Knauer, Giri Narasimhan, Michiel Smid
Abstract. Let G be a graph embedded in Euclidean space. For any two vertices of G their dilation denotes the length of a shortest connecting path in G, divided by their Euclidean distance. In this...
Darko Dimitrov, Christian Knauer, Klaus Kriegel, Günter Rote
×�ØÀ�Ö�Û�ÓÒØÖ��ÙØ�Ò�ÛÙÔÔ�Ö�ÓÙÒ�×ÓÒØ���ÔÔÖÓÜ �...
Marc Benkert, Joachim Gudmundsson, Christian Knauer, Esther Moet, René Van Oostrum, Er Wolff
polynomial-time approximation algorithm for
Computing the detour and spanning ratio of paths, trees and cycles in 2D and 3D (2008)
Pankaj K. Agarwal, Rolf Klein, Christian Knauer, Stefan Langerman, Pat Morin, Micha Sharir, ...
The detour and spanning ratio of a graph � embedded in �� � measure how well � approximates Euclidean space and the complete Euclidean graph, respectively. In this paper we describe...
Constructing Optimal Highways ∗ Hee-Kap Ahn † Helmut Alt ‡ Tetsuo Asano § Sang Won Bae (2008)
Peter Brass, Otfried Cheong, Christian Knauer, Hyeon-suk Na, Chan-su Shin
Parameterized Complexity of Geometric Problems (2008)
Giannopoulos, Panos, Knauer, Christian, Whitesides, Sue
This paper surveys parameterized complexity results for hard geometric algorithmic problems. It includes fixed-parameter tractable problems in graph drawing, geometric graphs, geometric covering and...
Fast enumeration of point-hyperplane incidences. (2007)
In this paper we study the complexity of enumerating all incidences between a set of n points P and a set of m hyperplanes H in d-dimensional euclidean space R d. We describe a deterministic...
Helmut Alt, Christian Knauer, Carola Wenk
Abstract. We provide the rst algorithm for matching two polygonal curves P and Q under translations with respect to the Frechet distance. If P and Q consist of m and n segments, respectively, the...
www.cs.uu.nl Guarding Art Galleries by Guarding Witnesses (2007)
Kyung-yong Chwa, Byung-cheol Jo, Christian Knauer, Esther Moet
Let P be a simple polygon. We define a witness set W to be a set of points such that if any (prospective) guard set G guards W, then it is guaranteed that G guards P. We show that not all polygons...
Comparison of distance measures for geometric shapes Helmut Alt (2007)
Helmut Alt, Christian Knauer, Christian Knauer, Carola Wenk, Carola Wenk
We consider planar curves where the arclength between any two points on the curve is at most a constant times their Euclidean distance, which we call -straight curves. Furthermore we consider a...
Constructing Optimal Highways (2007)
Ahn, Hee-Kap, Alt, Helmut, Asano, Tetsuo, Bae, Sang Won, Brass, Peter, Cheong, Otfried, ...
For two points $p$ and $q$ in the plane, a straight line $h$, called a highway, and a real $v>1$, we define the \emph{travel time} (also known as the \emph{city distance}) from $p$ and $q$ to be the...
Dilation-optimal edge deletion in polygonal cycles (2007)
Hee-kap Ahn, Mohammad Farshi, Christian Knauer, Michiel Smid, Yajun Wang
Consider a geometric network G in the plane. The dilation between any two vertices x and y in G is the ratio of the shortest path distance between x and y in G to the Euclidean distance between them....
Upper and lower bounds on the quality of the PCA bounding boxes (2007)
Darko Dimitrov, Christian Knauer, Klaus Kriegel, Günter Rote
Principle component analysis (PCA) is commonly used to compute a bounding box of a point set in R d. The popularity of this heuristic lies in its speed, easy implementation and in the fact that...
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...
Constructing Optimal Highways ∗ (2007)
Otfried Cheong, Christian Knauer, Hyeon-suk Na, Chan-su Shin, Alexander Wolff
For two points p and q in the plane, a straight line h, called a highway, and a real v> 1, we define the travel time (also known as the city distance) from p and q to be the time needed to...
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
Minimum-dilation tour (and path) is NP-hard (2007)
Panos Giannopoulos, Christian Knauer, Dániel Marx
We prove that computing a minimum-dilation (Euclidean) Hamilton circuit or path on a given set of points in the plane is NP-hard. 1
A disk-covering problem with application in optical interferometry (2006)
Nguyen, Trung, Boissonnat, Jean-Daniel, Falzon, Frederic, Knauer, Christian
Given a disk O in the plane called the objective, we want to find n small disks P_1,...,P_n called the pupils such that $\bigcup_{i,j=1}^n P_i \ominus P_j \supseteq O$, where $\ominus$ denotes the...
Minimum-Cost Coverage of Point Sets by Disks (2006)
Arkin, Esther M., Broennimann, Herve, Erickson, Jeff, Fekete, Sandor P., Knauer, Christian, Lenchner, Jonathan, ...
We consider a class of geometric facility location problems in which the goal is to determine a set X of disks given by their centers (t_j) and radii (r_j) that cover a given set of demand points Y...
A polynomial-time approximation algorithm for a geometric dispersion problem (2006)
Benkert, Marc, Gudmundsson, Joachim, Knauer, Christian, Moet, Esther, Oostrum, René Van, Wolff, Alexander
We consider the problem of placing a maximal number of disks in a rectangular region containing obstacles such that no two disks intersect. Let $\alpha$ be a fixed real in $(0,1]$. We are given a...
A polynomial-time approximation algorithm for a geometric dispersion problem. (2006)
Benkert, Marc, Gudmundsson, Joachim, Knauer, Christian, Moet, Esther, Oostrum, René Van, Wolff, Alexander
Fréchet distance for curves, revisited (2006)
Boris Aronov, Sariel Har-peled, Christian Knauer, Yusu Wang, Carola Wenk
Abstract. We revisit the problem of computing the Fréchet distance between polygonal curves, focusing on the discrete Fréchet distance, where only distance between vertices is considered. We...
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...
Annette Ebbers-baumann, Ansgar Grüne, Rolf Klein, Marek Karpinski, Christian Knauer, A. Ebbers-baumann, ...
Let S be a set of points in the plane. What is the minimum possible dilation of all plane graphs that contain S? Even for a set S as simple as five points evenly placed on the circle, this question...
Annette Ebbers-baumann, Ansgar Grüne, Rolf Klein, Marek Karpinski, Christian Knauer
Communicated by Li Zhang Let S be a set of points in the plane. What is the minimum possible dilation of all plane graphs that contain S? Even for a set S as simple as five points evenly placed on...
Marc Benkert, Joachim Gudmundsson, Christian Knauer, René Van Oostrum, Alexander Wolff, Communicated Danny Chen, ...
We consider the following packing problem. Let α be a fixed real in (0, 1]. We are given a bounding rectangle ρ and a set R of n possibly intersecting unit disks whose centers lie in ρ. The task...
A polynomial-time approximation algorithm for a geometric dispersion problem (2006)
Marc Benkert, Joachim Gudmundsson, Christian Knauer, Esther Moet, René Oostrum, Alexander Wolff
We consider the problem of placing a set of disks in a region containing obstacles such that no two disks intersect. We are given a bounding polygon P and a set R of possibly intersecting unit disks...
Minimum-cost coverage of point sets by disks (2006)
Helmut Alt, Esther M. Arkin, Hervé Brönnimann, Jeff Erickson, Sándor P. Fekete, Christian Knauer, ...
We consider a class of geometric facility location problems in which the goal is to determine a set X of disks given by their centers (t j) and radii (r j) that cover a given set of demand points Y...
Configuations with few crossings in topological graphs (2005)
Knauer, Christian, Schramme, Etienne, Spillner, Andreas, Wolff, Alexander
In this paper we study the problem of computing subgraphs of a certain configuration in a given topological graph G such that the number of crossings in the subgraph is minimum. The configurations...
Configuations with few crossings in topological graphs. (2005)
Knauer, Christian, Schramme, Etienne, Spillner, Andreas, Wolff, Alexander
Matching Point Sets with respect to the Earth Mover’s Distance (2005)
Sergio Cabello, Panos Giannopoulos, Christian Knauer, Günter Rote
Let A and B be two sets of m resp. n weighted points in the plane, with m ≤ n. We present (1 + ɛ) and (2+ɛ)-approximation algorithms for the minimum Euclidean Earth Mover’s Distance between A...
Shortest Inspection-Path (2005)
Queries In Simple, Christian Knauer, Günter Rote, Christian Knauer, Günter Rote
We want to preprocess a simple n-vertex polygon P to quickly determine the shortest path from a fixed source point s to some point visible from a query point q P . We call such queries...
Minimum Dilation Triangulations (2005)
Christian Knauer, Christian Knauer, Wolfgang Mulzer, Wolfgang Mulzer
Given a planar graph G, the graph theoretic dilation of G is defined as the maximum ratio of the shortest-path distance and the Euclidean distance between any two vertices of G. Given a planar point...
Embedding Point Sets into Plane Graphs of Small Dilation (2005)
Annette Ebbers-Baumann, Ansgar Grüne, Marek Karpinski, Rolf Klein, Christian Knauer, Andrzej Lingas
Let S be a set of points in the plane. What is the minimum possible dilation of all plane graphs that contain S?EvenforasetS as simple as five points evenly placed on the circle, this question seems...
Matching Point Sets with respect to the Earth Mover’s Distance (2005)
Sergio Cabello, Panos Giannopoulos, Christian Knauer, Günter Rote
The Earth Mover’s Distance (EMD) between two weighted point sets (point distributions) is a distance measure commonly used in computer vision for color-based image retrieval and shape matching. It...
Configurations with few crossings in topological graphs (2005)
Christian Knauer, Étienne Schramm, Andreas Spillner Alex, Er Wolff
In this paper we study the problem of computing subgraphs of a certain configuration in a given topological graph G such that the number of crossings in the subgraph is minimum. The configurations...
Configurations with few crossings in topological graphs (2005)
Christian Knauer, Étienne Schramm, Andreas Spillner, Er Wolff
Abstract. In this paper we study the problem of computing subgraphs of a certain configuration in a given topological graph G such that the number of crossings in the subgraph is minimum. The...
Embedding point sets into plane graphs of small dilation (2005)
Annette Ebbers-baumann, Ansgar Grüne, Marek Karpinski, Rolf Klein, Christian Knauer, Andrzej Lingas
Let S be a set of points in the plane. What is the minimum possible dilation of all plane graphs that contain S? Even for a set S as simple as five points evenly placed on the circle, this question...
Rolf Klein, Christian Knauer, Giri Narasimhan, Michiel Smid
Let G be a graph embedded in Euclidean space. For any two vertices of G their dilation denotes the length of a shortest connecting path in G, divided by their Euclidean distance. In this paper we...
Visibility Maps of Segments and Triangles in 3D* (2005)
Esther Moet, Christian Knauer, Marc Van Kreveld
1 Introduction Computations concerning visibility and the generation of shadows are important to obtain realisticimages in computer graphics. Unfortunately, these computations can be very...
www.cs.uu.nl Visibility Maps of Segments and Triangles in 3D ∗ (2005)
Esther Moet, Christian Knauer, Marc Van Kreveld, Esther Moet, Christian Knauer, Marc Van Kreveld
Let T be a set of n triangles in three-dimensional space, let s be a line segment, and let t be a triangle, both disjoint from T. We consider the visibility map of s with respect to T, i.e., the...
Matching Point Sets with respect to the Earth Mover’s Distance (2005)
Sergio Cabello, Panos Giannopoulos, Christian Knauer, Günter Rote
Shape matching is a fundamental problem in computer vision: given two shapes A and B, one wants to determine how closely A resembles B, according to some distance measure between the shapes. In order...
Comparison of distance measures for planar curves (2004)
Christian Knauer, Carola Wenky
Abstract The Hausdorff distance is a very natural and straightforward distance measure for comparing geometric shapes like curves or other compact sets. Unfortunately, it is not an appropriate...
DOI: 10.1007/s00453-003-1047-0 Covering with Ellipses 1 (2003)
Alon Efrat, Frank Hoffmann, Christian Knauer, Klaus Kriegel, Günter Rote, Carola Wenk
Abstract. We address the problem of how to cover a set of required points by a small number of axis-parallel ellipses that avoid a second set of forbidden points. We study geometric properties of...
DOI: 10.1007/s00453-003-1047-0 Covering with Ellipses 1 (2003)
Alon Efrat, Frank Hoffmann, Christian Knauer, Klaus Kriegel, Günter Rote, Carola Wenk
Abstract. We address the problem of how to cover a set of required points by a small number of axis-parallel ellipses that avoid a second set of forbidden points. We study geometric properties of...
The Area of Overlap of two Unions of Convex Objects under Translation (2003)
Mark De Berg, Panos Giannopoulos, Christian Knauer, Remco C. Veltkamp
Let A and B be two sets of n resp. m disjoint unit discs in the plane, with m n. We consider the problem of nding a translation of A that maximizes the total area of its overlap with B. We rst show...
On the Complexity of the Linkage Reconfiguration Problem (2003)
Helmut Alt, Helmut Alt, Günter Rote, Christian Knauer, Christian Knauer, Sue Whitesides, ...
We consider the problem of recon guring a linkage of rigid straight segments from a given start to a given target position with a continuous nonintersecting motion. The problem is nontrivial even for...
www.cs.uu.nl Guarding Art Galleries by Guarding Witnesses (2003)
Kyung-yong Chwa, Byung-cheol Jo, Christian Knauer, Esther Moet, René Oostrum, Chan-su Shin
Let P be a simple polygon. We define a witness set W to be a set of points such that if any (prospective) guard set G guards W, then it is guaranteed that G guards P. We show that not all polygons...
Computing the Detour of Polygonal Curves (2002)
Pankaj K. Agarwal, Pankaj K. Agarwal, Rolf Klein, Rolf Klein, Christian Knauer, Christian Knauer, ...
Let P be a simple polygonal chain in E with n edges. The detour of P between two points, x and y, is the ratio between the length of P between x any y and their Euclidean distance.
Berlin, Freie University, 2002 (Nicht für den Austausch).
Bounding the Fréchet distance by the Hausdorff distance (2001)
Helmut Alt, Christian Knauer, Carola Wenk
We consider planar curves where the arclength between any two points on the curve is at most a constant times their Euclidean distance, which we call κ-straight curves. We show that the Frechet...
Computing the Hausdorff distance of geometric patterns and shapes (2001)
Helmut Alt, Peter Braß, Michael Godau, Christian Knauer, Carola Wenk
A very natural distance measure for comparing shapes and patterns is the Hausdorff distance. In this article we develop algorithms for computing the Hausdorff distance in a very general case where...
Nearest Neighbour Search in Hausdorff Distance Pattern Spaces (2001)
Peter Braß, Peter Bra, Christian Knauer, Christian Knauer
We devise the first data structure that, with a sufficient amount of preprocessing, answers nearest-neigbour queries among point patterns in d-dimensional Euclidean space with respect to (various...
Alon Efrat, Frank Hoffmann, Alon Efrat, Christian Knauer, Günter Rote, Christian Knauer, ...
We address the problem of how to cover a set of required points by a small number of axis{parallel ellipses that avoid a second set of forbidden points. We study geometric properties of such covers...
Dateiformat: zip, Dateien im PDF-Format.
Testing the Congruence of d-Dimensional Point Sets (2000)
This paper presents an algorithm that tests the congruence of two sets of n points in d-dimensional space in O(n d 1 3 de log n) time. This improves the previous best algorithm for dimensions d 6.
Testing the Congruence of d-Dimensional Point Sets (1999)
This paper presents an algorithm that tests the congruence of two sets of n points in d-dimensional space in O(n d 1 3 de log n) time. This improves the previous best algorithm for dimensions d 6....