Geodesic Fréchet Distance Inside a Simple Polygon (2009)
We present an alternative to parametric search that applies to both the non-geodesic and geodesic Fréchet optimization problems. This randomized approach is based on a variant of red-blue...
and Problem Complexity—Geometrical problems and computations General Terms Algorithms (2009)
Given a polygonal curve and a geometric graph, we describe an efficient algorithm to find a path in the graph which is most similar to the curve, using the well-known Fréchet distance for curves.
Shortest Path Problems on a Polyhedral Surface (2009)
We develop algorithms to compute edge sequences, Voronoi diagrams, shortest path maps, the Fréchet distance, and the diameter for a polyhedral surface. Distances on the surface are measured either...
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...
Geodesic Fréchet Distance Inside a Simple Polygon ∗ (2008)
Abstract — We present the first algorithm for the geodesic Fréchet distance between two polygonal curves A and B inside a simple polygon P. If A and B have total complexity N and P has complexity...
Adressing the Need for Map-Matching Speed: Localizing Global Curve-Matching Algorithms (2008)
Carola Wenk, All Salas, Dieter Pfoser
Abstract. Tracking data becomes an increasingly available sensor data resource that can be used in a range of applications related to traffic assessment and prediction. Of critical importance in this...
Matching Planar Maps Helmut Alt \Lambda (2008)
y Abstract The subject of this paper are algorithms for measuring the similarity of patterns of line segments in the plane, a standard problem in, e.g. computer vision, geographic information...
Christian A. Duncan, Alon Efrat, Stephen Kobourov, Carola Wenk
Communicated by Editor’s name Traditionally, graph drawing algorithms represent vertices as circles and edges as curves connecting the vertices. We introduce the problem of drawing with “fat ”...
1 Introduction Dynamic Routing 1 (2008)
The intent of this research is to find a way of applying a version of a shortest path algorithm such as Dijkstra’s, or the more general A*, to a graph with
Abstract Matching 2D Patterns of Protein Spots (2008)
Frank Hoffmann, Klaus Kriegel, Carola Wenk
A new algorithmic approach to comparing 2D patterns of protein spots obtained by the 2D gel electrophoresis technique is presented. Both the matching of a local pattern vs. a full 2D gel image and...
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...
Geodesic Fréchet Distance Inside a Simple Polygon ∗ (2008)
Abstract — We present the first algorithm for the geodesic Fréchet distance between two polygonal curves A and B inside a simple polygon P. If A and B have total complexity N and P has complexity...
Geodesic Fr\'echet Distance Inside a Simple Polygon (2008)
Cook IV, Atlas F., Wenk, Carola
We unveil an alluring alternative to parametric search that applies to both the non-geodesic and geodesic Fr\'echet optimization problems. This randomized approach is based on a variant of red-blue...
Geodesic Fréchet Distance Inside a Simple Polygon (2008)
We unveil an alluring alternative to parametric search that applies to both the non-geodesic and geodesic Fréchet optimization problems. This randomized approach is based on a variant of red-blue...
Geodesic Fréchet Distance Inside a Simple Polygon (2008)
We unveil an alluring alternative to parametric search that applies to both the non-geodesic and geodesic Fréchet optimization problems. This randomized approach is based on a variant of red-blue...
Geodesic Fréchet distance inside a simple polygon (2008)
Abstract. We unveil an alluring alternative to parametric search that applies to both the non-geodesic and geodesic Fréchet optimization problems. This randomized approach is based on a variant of...
18. Geodesic Fréchet Distance Inside a Simple Polygon (2008)
We unveil an alluring alternative to parametric search that applies to both the non-geodesic and geodesic Fréchet optimization problems. This randomized approach is based on a variant of red-blue...
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...
We present a simple geometric and combinatorial algorithm for the approximate partial matching problem of small 3D point landmark patterns. It has been designed for and successfully applied in a...
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...
Christian A. Duncan, Alon Efrat, Stephen G. Kobourov, Carola Wenk
Abstract. In this paper, we introduce the problem of drawing with "fat " edges. Traditionally, graph drawing algorithms represent vertices as circles and edges as closed curves...
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...
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...
Addressing the need for map-matching speed: Localizing global curve-matching algorithms (2006)
With vehicle tracking data becoming an important sensor data resource for a range of applications related to traffic assessment and prediction, fast and accurate mapmatching algorithms become a...
On map-matching vehicle tracking data (2005)
Sotiris Brakatsoulas, Dieter Pfoser, Randall Salas, Carola Wenk
Vehicle tracking data is an essential “raw ” material for a broad range of applications such as traffic management and control, routing, and navigation. An important issue with this data is its...
Matching polyhedral terrains using overlays of envelopes (2004)
For a collection F of d-variate piecewise linear functions of overall combinatorial complexity n, the lower envelope E(F) of F is the pointwise minimum of these functions. The minimization diagram...
Matching polyhedral terrains using overlays of envelopes (2004)
For a collection F of d-variate piecewise linear functions of overall combinatorial complexity n, the lower envelope E(F)ofF is the pointwise minimum of these functions. The minimization diagram M(F)...
Shape matching in higher dimensions [Elektronische Ressource] / (2003)
Dateiformat: zip, Dateien im PDF-Format.
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...
Finding a Curve in a Map (2003)
Carola Wenk, Helmut Alt, Alon Efrat, Lingeshwaran Palaniappan, Günter Rote
Given a polygonal curve and a geometric graph, we describe an e#cient algorithm to find a path in the graph which is most similar to the curve, using the well-known Frechet distance for curves.
Finding a Curve in a Map (2003)
Carola Wenk, Helmut Alt, Alon Efrat, Lingeshwaran Palaniappan, Günter Rote
Given a polygonal curve and a geometric graph, we describe an ecient algorithm to nd a path in the graph which is most similar to the curve, using the well-known Frechet distance for curves.
Helmut Alt, Alon Efrat, Günter Rote, Carola Wenk
The subject of this paper are algorithms for measuring the similarity of patterns of line segments in the plane, a standard problem in, e.g., computer vision, geographic information systems, etc....
Helmut Alt, Alon Efrat, Günter Rote, Carola Wenk
The subject of this paper are algorithms for measuring the similarity of patterns of line segments in the plane, a standard problem in, e.g. computer vision, geographic information systems, etc. More...
Finding a Curve in a Map (2003)
Carola Wenk, Helmut Alt, Alon Efrat, Lingeshwaran Palaniappan, Günter Rote
Given a polygonal curve and a geometric graph, we describe an ecient algorithm to nd a path in the graph which is most similar to the curve, using the well-known Frechet distance for curves.
Duncan, Christian A., Efrat, Alon, Kobourov, Stephen G., Wenk, Carola
In this paper, we introduce the problem of drawing with "fat" edges. Traditionally, graph drawing algorithms represent vertices as circles and edges as closed curves connecting the vertices. In this...
Duncan, Christian A., Efrat, Alon, Kobourov, Stephen G., Wenk, Carola
In this paper, we introduce the problem of drawing with "fat" edges. Traditionally, graph drawing algorithms represent vertices as circles and edges as closed curves connecting the vertices. In this...
Shape matching in higher dimensions = Formenvergleich in höheren Dimensionen / (2002)
Berlin, Freie University, Diss., 2002 (Nicht für den Austausch).
Duncan, Christian A., Efrat, Alon, Kobourov, Stephen G., Wenk, Carola
In this paper, we introduce the problem of drawing with "fat" edges. Traditionally, graph drawing algorithms represent vertices as circles and edges as closed curves connecting the vertices. In this...
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...
Christian A. Duncan, Alon Efrat, Stephen G. Kobourov, Carola Wenk
Abstract. In this paper, we introduce the problem of drawing with “fat ” edges. Traditionally, graph drawing algorithms represent vertices as circles and edges as closed curves connecting the...
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...
Applying an Edit Distance to the Matching of Tree Ring Sequences in Dendrochronology (1999)
Abstract. In dendrochronology wood samples are dated according to the tree rings they contain. The dating process consists of comparing the sequence of tree ring widths in the sample to a dated...
Applying an Edit Distance to the Matching of Tree Ring Sequences in Dendrochronology (1999)
In dendrochronology wood samples are dated according to the tree rings they contain. The dating process is a one dimensional matching in which the sequence of tree ring widths in the sample is...
On the Number of Cylinders Touching a Ball (1999)
: In this note we prove an upper bound of seven for the maximum number of unit cylinders touching a unit ball in a packing. This improves a previous bound of eight by Heppers and Szabo. The value...
Matching 2D Patterns of Protein Spots (1997)
Frank Hoffmann, Klaus Kriegel, Carola Wenk
A new algorithmic approach to comparing 2D patterns of protein spots obtained by the 2D gel electrophoresis technique is presented. Both the matching of a local pattern vs. a full 2D gel image and...