93 Result(s)

Chapter and Conference Paper

Packing 2D Disks into a 3D Container

In this article, we consider the problem of finding in three dimensions a minimum volume axis-parallel box into which a given set of unit size disks can be packed under translations. The problem is neither kno...

Helmut Alt, Otfried Cheong, Ji-won Park, Nadja Scharf in WALCOM: Algorithms and Computation (2019)

Chapter and Conference Paper

A Middle Curve Based on Discrete Fréchet Distance

Given a set of polygonal curves we seek to find a middle curve that represents the set of curves. We require that the middle curve consists of points of the input curves and that it minimizes the discrete Fréc...

Hee-Kap Ahn, Helmut Alt, Maike Buchin, Eun** Oh… in LATIN 2016: Theoretical Informatics (2016)

Chapter and Conference Paper

Approximating Minimum-Area Rectangular and Convex Containers for Packing Convex Polygons

We investigate the problem of finding a minimum-area container for the disjoint packing of a set of convex polygons by translations. In particular, we consider axis-parallel rectangles or arbitrary convex sets...

Helmut Alt, Mark de Berg, Christian Knauer in Algorithms - ESA 2015 (2015)

Article

Scandinavian Thins on Top of Cake: New and Improved Algorithms for Stacking and Packing

We show how to compute the smallest rectangle that can enclose any polygon, from a given set of polygons, in nearly linear time; we also present a PTAS for the problem, as well as a linear-time algorithm for t...

Helmut Alt, Esther M. Arkin, Alon Efrat, George Hart… in Theory of Computing Systems (2014)

Chapter and Conference Paper

Bundling Three Convex Polygons to Minimize Area or Perimeter

Given a set \({\mathcal P} =\{P_0,\ldots,P_{k-1}\}\) of k convex polygons having n vertices in total in the plane, we consider the problem ...

Hee-Kap Ahn, Helmut Alt, Sang Won Bae, Dongwoo Park in Algorithms and Data Structures (2013)

Chapter

Fast Sorting Algorithms

This chapter presents two sorting algorithms – Mergesort and Quicksort – that work quickly even for a large number of objects. The author explains the algorithms, compares them theoretically, and suggests how ...

Helmut Alt in Algorithms Unplugged (2011)

Chapter

The Computational Geometry of Comparing Shapes

This article is a survey on methods from computational geometry for comparing shapes that we developed within our work group at Freie Universität Berlin. In particular, we will present the ideas and complexity...

Helmut Alt in Efficient Algorithms (2009)

Chapter and Conference Paper

Shape Matching by Random Sampling

In order to determine the similarity between two planar shapes, which is an important problem in computer vision and pattern recognition, it is necessary to first match the two shapes as good as possible. As s...

Helmut Alt, Ludmila Scharf in WALCOM: Algorithms and Computation (2009)

Chapter

Schnelle Sortieralgorithmen

Wie wichtig das Sortieren ist, wurde schon in Kap. 2 beschrieben. Eine effiziente Suche in einer Menge von Daten, wie die in Kap. 1 vorgestellte Binärsuche, ist nur möglich, wenn die Menge vorher sortiert wurd...

Helmut Alt in Taschenbuch der Algorithmen (2008)

Chapter and Conference Paper

Wooden Geometric Puzzles: Design and Hardness Proofs

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 of puzzles...

Helmut Alt, Hans Bodlaender, Marc van Kreveld, Günter Rote… in Fun with Algorithms (2007)

Article

Foreword

Helmut Alt in Theory of Computing Systems (2005)

Article

Comparison of Distance Measures for Planar Curves

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 distance measure...

Helmut Alt, Christian Knauer, Carola Wenk in Algorithmica (2004)

Chapter

Computing the Hausdorff Distance of Geometric Patterns and Shapes

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 geometric...

Helmut Alt, Peter Braß, Michael Godau… in Discrete and Computational Geometry (2003)