Probabilistic Matching of Planar Regions (2009)
Alt, Helmut, Scharf, Ludmila, Schymura, Daria
We analyze a probabilistic algorithm for matching shapes modeled by planar regions under translations and rigid motions (rotation and translation). Given shapes $A$ and $B$, the algorithm computes a...
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.
09111 Abstracts Collection -- Computational Geometry (2009)
Agarwal, Pankaj Kumar, Alt, Helmut, Teillaud, Monique
From March 8 to March 13, 2009, the Dagstuhl Seminar 09111 ``Computational Geometry '' was held in Schloss Dagstuhl~--~Leibniz Center for Informatics. During the seminar, several participants...
ABSTRACT Minimum-Cost Coverage of Point Sets by Disks ∗ (2008)
Helmut Alt, Jeff Erickson, Jonathan Lenchner, Esther M. Arkin, Sándor P. Fekete
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...
[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....
Federal Republic of Germany (2008)
Helmut Alt, Rudolf Fleischer, Michael Kaufmann, Kurt Mehlhorn, Stefan Schirra, Christian Uhrig, ...
Abstract: We study rigid motions of a rectangle amidst polygonal obstacles. The best known algorithms for this problem have running time f~(n 2) where n is the number of obstacle corners. We...
Probabilistic Matching and Resemblance Evaluation of Shapes in Trademark Images ∗ ABSTRACT (2008)
Helmut Alt, Ludmila Scharf, Sven Scholz
We present a novel matching and similarity evaluation method for planar geometric shapes represented by sets of polygonal curves. Given two shapes, the matching algorithm randomly generates a point...
Fachbereich Mathematik und Informatik (2008)
Ludmila Scharf, Betreuer Prof, Dr. Helmut Alt
between sets of curves vorgelegt von
Wooden Geometric Puzzles: Design and Hardness Proofs (2008)
Hans L. Bodlaender, Marc Van Kreveld, Günter Rote, Gerard Tel, Helmut Alt, Hans L. Bodlaender, ...
We discuss some new geometric puzzles and the complexity of their extension to arbitrary sizes. For gate puzzles and two-layer puzzles we prove NP-completeness of solving them. Not only the solution...
Helmut Alt, Hans L. Bodlaender, Marc Kreveld, Gerard Tel, Gerard Tel
Abstract We discuss some new geometric puzzles and the complexity of their extension to arbitrary sizes. For gate puzzles and two-layer puzzles we prove NP-completeness of solving them. Not only the...
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...
Computational Discrete Mathematics Lectures of the Graduate Program (2007)
Algorithmische Diskrete Mathematik, Prof Dr, Helmut Alt, Bettina Felsner
address
Kontrolle Projektbereich Diskrete, Spezialforschungsbereich F, Bericht Nr, Helmut Alt, Helmut Alt, ...
This paper deals with questions from convex geometry related to shape matching. In particular, we consider the problem of moving one convex #gure over another, minimizing the area of their symmetric...
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...
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...
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...
The Voronoi Diagram of Curved Objects (2005)
Alt, Helmut, Cheong, Otfried, Vigneron, Antoine
Voronoi diagrams of curved objects can show certain phenomena that are often considered artifacts: The Voronoi diagram is not connected; there are pairs of objects whose bisector is a closed curve or...
The economics of wind energy within the generation mix (2005)
With more than 15,000 plants of different capacity ranges, Germany has become the world's No. 1 in generating electricity from wind power, covering around 4% of the electricity requirements at home....
The economics of wind energy within the generation mix (2005)
With more than 15,000 plants of different capacity ranges, Germany has become the world's No. 1 in generating electricity from wind power, covering around 4% of the electricity requirements at home....
Space Efficient Hash Tables with Worst Case Constant Access Time (2003)
Fotakis, Dimitris, Pagh, Rasmus, Sanders, Peter, Spirakis, Paul G., Alt, Helmut, Habib, Michel
We generalize Cuckoo Hashing \cite{PagRod01} to \emph{$d$-ary Cuckoo Hashing} and show how this yields a simple hash table data structure that stores $n$ elements in $(1+\epsilon)\,n$ memory cells,...
On the Worst-Case Complexity of the Silhouette of a Polytope (2003)
Helmut Alt, Marc Glisse, Xavier Goaoc
We give conditions under which the worst-case size of the silhouette of a polytope is sub-linear. We provide examples with linear size silhouette if any of these conditions is relaxed. Our bounds are...
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....
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...
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.
Scheduling at Twilight the Easy Way (2002)
Bast, Hannah, Ferreira, Afonso, Alt, Helmut
We investigate particularly simple algorithms for optimizing the tradeoff between load imbalance and assignment overheads in dynamic multiprocessor scheduling scenarios, when the information that is...
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...
Algorithms for Comparing Geometric Patterns (2001)
Contents 1 Introduction 1 I Point set pattern matching in d-dimensional space 5 2 Testing the congruence of point sets in Rd 9
Point-Sets With Few K-Sets (1998)
Helmut Alt, Stefan Felsner, Ferran Hurtado, Marc Noy
A k-set of a finite set S of points in the plane is a subset of cardinality k that can be separated from the rest by a straight line. The question of how many k-sets a set of n points can contain is...
Matching Convex Shapes with Respect to the Symmetric Difference (1997)
Helmut Alt, Ulrich Fuchs, Ulrich Fuchs, Günter Rote, Gunter Rote, Gerald Weber, ...
This paper deals with questions from convex geometry related to shape matching. In particular, we consider the problem of moving one convex figure over another, minimizing the area of their symmetric...
Piecewise Linear Approximation of Bézier-Curves (1997)
Helmut Alt, Emo Welzl, Barbara Wolfers
F24.86> B i;n (t j ) can be precomputed and stored in a table, and the vertices of the approximation can be easily retrieved as linear combinations of the control points. Observe that C has a...
Universal 3-Dimensional Visibility Representations Graphs (1996)
Alt, Helmut, Godau, Michael, Whitesides, Sue
This paper studies 3-dimensional visibility representations of graphs in which objects in 3-d correspond to vertices and vertical visibilities between these objects correspond to edges. We ask which...
Universal 3-Dimensional Visibility Representations Graphs (1996)
Alt, Helmut, Godau, Michael, Whitesides, Sue
This paper studies 3-dimensional visibility representations of graphs in which objects in 3-d correspond to vertices and vertical visibilities between these objects correspond to edges. We ask which...
Universal 3-Dimensional Visibility Representations Graphs (1996)
Alt, Helmut, Godau, Michael, Whitesides, Sue
This paper studies 3-dimensional visibility representations of graphs in which objects in 3-d correspond to vertices and vertical visibilities between these objects correspond to edges. We ask which...
Discrete Geometric Shapes: Matching, Interpolation, and Approximation: A Survey (1996)
Helmut Alt, Leonidas J. Guibas
In this survey we consider geometric techniques which have been used to measure the similarity or distance between shapes, as well as to approximate shapes, or interpolate between shapes. Shape is a...
A Method for Obtaining Randomized Algorithms with Small Tail Probabilities (1996)
Alt, Helmut, Guibas, L., Mehlhorn, Kurt, Karp, Richard M., Wigderson, A.
We study strategies for converting randomized algorithms of the Las Vegas type into randomized algorithms with small tail probabilities.
Universal 3-Dimensional Visibility Representations for Graphs (1995)
Alt, Helmut, Godau, Michael, Whitesides, Sue
This paper studies 3-dimensional visibility representations of graphs in which objects in 3-d correspond to vertices and vertical visibilities between these objects correspond to edges. We ask which...
Universal 3-Dimensional Visibility Representations for Graphs (1995)
Alt, Helmut, Godau, Michael, Whitesides, Sue
This paper studies 3-dimensional visibility representations of graphs in which objects in 3-d correspond to vertices and vertical visibilities between these objects correspond to edges. We ask which...
Universal 3-Dimensional Visibility Representations for Graphs (1995)
Alt, Helmut, Godau, Michael, Whitesides, Sue
This paper studies 3-dimensional visibility representations of graphs in which objects in 3-d correspond to vertices and vertical visibilities between these objects correspond to edges. We ask which...
Universal 3-Dimensional Visibility Representations for Graphs (1995)
Helmut Alt, Helmut Alt, Michael Godau, Michael Godau, Sue Whitesides, Sue Whitesides, ...
This paper studies 3-dimensional visibility representations of graphs in which objects in 3-d correspond to vertices and vertical visibilities between these objects correspond to edges. We ask which...
An application of point pattern matching in astronautics (1994)
Gerald Weber, Lars Knipping, Helmut Alt
We consider a point pattern matching problem occuring in astronautics: Given are pictures from a camera of unknown orientation, showing a section of the starry sky. We want to determine the...
Computing the Largest Inscribed Isothetic Rectangle (1994)
Helmut Alt, David Hsu, Jack Snoeyink
This paper describes an algorithm to compute, in \Theta(log n) time, a rectangle that is contained in a convex n-gon, has sides parallel to the coordinate axes, and has maximum area. With a slight...
Matching Shapes with a Reference Point (1994)
Helmut Alt, Oswin Aichholzer, Günter Rote
For two given point sets, we present a very simple (almost trivial) algorithm to translate one set so that the Hausdorff distance between the two sets is not larger than a constant factor times the...
Matching Shapes with a Reference Point (1994)
Helmut Alt, Oswin Aichholzer, Günter Rote
For two given point sets, we present a very simple (almost trivial) algorithm to translate one set so that the Hausdorff distance between the two sets is not larger than a constant factor times the...
Alt, Helmut, Fleischer, Rudolf, Kaufmann, Michael, Mehlhorn, Kurt, Näher, Stefan, Schirra, Stefan, ...
A Method for Obtaining Randomized Algorithms with Small Tail Probabilities (1991)
Alt, Helmut, Guibas, L., Mehlhorn, Kurt, Karp, Richard M., Wigderson, A.
We study strategies for converting randomized algorithms of the Las Vegas type into randomized algorithms with small tail probabilities.
Alt, Helmut, Fleischer, Rudolf, Kaufmann, Michael, Mehlhorn, Kurt, Näher, Stefan, Schirra, Stefan, ...
Proceedings of the Eighth Annual Symposium on Computational Geometry, pages 102{ (1989)
Helmut Alt, Bernd Behrends, Helmut Alt, Michael Godau, Measuring In, Esther M. Arkin, ...
S. B. Mitchell. An e ciently computable metric for comparing polygonal shapes. In
Deterministic Simulation of Idealized Parallel Computers on More Realistic Ones (1987)
Alt, Helmut, Hagerup, Torben, Mehlhorn, Kurt, Preparata, Franco P.
The authors describe a nonuniform deterministic simulation of PRAMs on module parallel computers (MPCs) and on processor networks of bounded degree. The simulating machines have the same number $n$...
Deterministic Simulation of Idealized Parallel Computers on more Realistic Ones (1987)
Alt, Helmut, Hagerup, Torben, Mehlhorn, Kurt, Preparata, Franco P., Albrecht, Andreas, Jung, Hermann, ...
Deterministic Simulation of Idealized Parallel Computers on More Realistic Ones (1986)
Alt, Helmut, Hagerup, Torben, Mehlhorn, Kurt, Preparata, Franco P., Gruska, Jozef, Rovan, Branislav, ...
Deterministic simulation of idealized parallel computers on more realistic ones (1985)
Alt, Helmut, Hagerup, Torben, Mehlhorn, Kurt, Preparata, Franco P.
Partial Match Retrieval in Implicit Data Structures (1981)
Alt, Helmut, Mehlhorn, Kurt, Munro, J. Ian, Gruska, Jozef, Chytil, Michal
Saarbrücken, Univ., Math.-Naturwiss. Fak., Diss., 1976. (Nicht f. d. Austausch.).
Beitrag zur Spannungs-Blindleistungsregelung mit gesteuerten Netzkennlinien / (1975)
Thesis (doctoral)--Rheinisch-Westfälische Technische Hochschule Aachen, 1975.
Thesis (doctoral)--Technische Universität München, 1973.