0000000000644494
AUTHOR
Stefan Funke
Packing a trunk - Now with a twist!
In an industry project with a German car manufacturer we are faced with the challenge of placing a maximum number of uniform rigid rectangular boxes in the interior of a car trunk. The problem is of practical importance due to a European industry norm which requires car manufacturers to state the trunk volume according to this measure. No really satisfactory automated solution for this problem has been known in the past. In spite of its NP hardness, combinatorial optimization techniques, which consider only grid-aligned placements, produce solutions which are very close to the one achievable by a human expert in several hours of tedious work. The remaining gap is mostly due to the constrain…
Packing a Trunk
We report on a project with a German car manufacturer. The task is to compute (approximate) solutions to a specific large-scale packing problem. Given a polyhedral model of a car trunk, the aim is to pack as many identical boxes of size 4 × 2 × 1 units as possible into the interior of the trunk. This measure is important for car manufacturers, because it is a standard in the European Union.
How much geometry it takes to reconstruct a 2-manifold in R 3
Known algorithms for reconstructing a 2-manifold from a point sample in R 3 are naturally based on decisions/predicates that take the geometry of the point sample into account. Facing the always present problem of round-off errors that easily compromise the exactness of those predicate decisions, an exact and robust implementation of these algorithms is far from being trivial and typically requires employment of advanced datatypes for exact arithmetic, as provided by libraries like CORE, LEDA, or GMP. In this article, we present a new reconstruction algorithm, one whose main novelties is to throw away geometry information early on in the reconstruction process and to mainly operate combina…