Helmut AltCOMPUTATIONAL ASPECTS OF PACKING PROBLEMS
DEFINITION AND COMPLEXITY OF THE PROBLEMS
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,
NP-hardness of finding a minimum area circular container for a given set of circles
(2d) by reduction from 3-partition.
CIRCLE AND SPHERE PACKING 2
densest packing of unit size circles in the plane, Fejes-Toth,
densest packing of unit size spheres in 3d-space, Kepler/Hales,
PTAS for minimum size containers for finite sets of unit
- 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 Three-dimensional Convex Objects
- Circle Packing 2
Jean-Daniel BoissonnatDelaunay 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, alpha-complexes.
3.4. Data structures for simplicial complexes.
4. Reconstruction of submanifolds of Rd
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 WenkAlgorithms for Map Construction and Comparison
Map Construction I
Map Construction II
Local persistent homology-based distance
Graph sampling-based distance
Handling directed edges, multiple lanes, turn restrictions
Map comparison for directed and weighted graphs
Map updates and detecting change
Frechet range queries
- Map Construction I
- Map Construction II
- Map Comparison