Helmut Alt
COMPUTATIONAL ASPECTS OF PACKING PROBLEMS
DEFINITION AND COMPLEXITY OF THE PROBLEMS
problem definition,
NPhardness results,
upper bounds:
1st order theory/existential theory of the reals,
exact packing in 2d.

APPROXIMATION ALGORITHMS 2D
strip packing heuristics for rectangles,
packing of irregular objects (convex polygons)
into a minimum size rectangle.

APPROXIMATION ALGORITHMS 3D
< strip packing,
packing of cuboids or convex polyhedra
by rigid motions,
containers: cuboids or convex bodies.

CIRCLE AND SPHERE PACKING 1
minimum size containers for fixed size sets of circles or spheres,
open problems,
NPhardness of finding a minimum area circular container for a given set of circles
(2d) by reduction from 3partition.

CIRCLE AND SPHERE PACKING 2
densest packing of unit size circles in the plane, FejesToth,
densest packing of unit size spheres in 3dspace, Kepler/Hales,
PTAS for minimum size containers for finite sets of unit
circles/spheres.
 Definition and Complexity of Packing Problems
 Logic, Complexity Theory, and Their Application to Packing Problems
 Approximation Algorithms for Packing Problems in Two Dimensions
 Circle Packing 1 and Packing Threedimensional Convex Objects
 Circle Packing 2
JeanDaniel Boissonnat
Delaunay triangulation of manifolds
1. Delaunay triangulations in Euclidean and Laguerre geometry
1.1. Euclidean case, Delaunay's theorem.
1.2. Weighted points. Affine diagrams. Union of balls.
1.3. Examples of affine diagrams.

2. Good Delaunay triangulations and meshes
2.1. Nets and combinatorial bounds. Delaunay refinement.
2.2. Thickness, protection, stability of Delaunay triangulations.
2.3. Perturbation algorithms. The Local Lovasz Lemma and heuristics.

3. Triangulation of topological spaces
3.1. Topological spaces, equivalences between topological spaces.
3.2. (Abstract) simplicial complexes, nerve theorem.
3.3. Geometric complexes and filtrations : Cech, Rips, alphacomplexes.
3.4. Data structures for simplicial complexes.

4. Reconstruction of submanifolds of R^{d}
4.1. Sets of positive reach.
4.2. Quality of approximation.
4.3. Distance functions and homotopic shape reconstruction.
4.4. The curse of dimensionality, the tangential Delaunay complex.

5. Delaunay triangulation of Riemannian manifolds
5.1. Anisotropic Delaunay triangulation.
5.2. Delaunay triangulation of Riemannian manifolds.
5.3. Statistical spaces. Fischer metric and Bregman divergence.
 Delaunay triangulations of manifolds
 Delaunay triangulation of manifolds 2 (Good triangulations and meshes)
 Delaunay triangulation of manifolds 3 (Triangulation of topological spaces)
 Delaunay triangulation of manifolds 4 (Shape reconstruction)
 Delaunay triangulation of manifolds 5
Carola Wenk
Algorithms for Map Construction and Comparison
MapMatching
Frechet distance
Frechet mapmatching
HMM mapmatching

Map Construction I
Densitybased methods
Intersection linking
Frechetbased

Map Construction II
Frechetclustering
Bundle mapconstruction

Map Comparison
Hausdorff distance
Pathbased distances
Local persistent homologybased distance
Graph samplingbased distance
Local signatures

Extensions
Handling directed edges, multiple lanes, turn restrictions
Map comparison for directed and weighted graphs
Map updates and detecting change
Frechet range queries
 MapMatching
 Map Construction I
 Map Construction II
 Map Comparison
 Extensions