In this thesis, we study different kinds of packing problems. A packing is an arrangement of geometric objects in Euclidean space of any fixed dimension such that the interiors of the packed objects are pairwise disjoint. The aim is to optimize some goal function such as the area of the smallest convex container enclosing the objects or the number of objects that can be packed into a given container. Here, we study problems only in two or three dimensions.
The thesis is divided into two parts. In the first part, we study packing equal objects. In most cases, we are given a container and want to compute the maximum number of copies of an object that can be packed into it. We obtain the following results:
The container is a fat parallelogram or triangle: Given a container parallelogram by a base edge and an additional point, there is a polynomial-time approximation scheme (PTAS) to compute the maximum number of copies of an object that can be packed into the container under translation or rigid motions if the following conditions hold: •The inner angles of the container are bounded from below by a constant, i.e., the container is fat. •Either the object to be packed is part of the problem description and not part of the algorithm input or the area of the object to be packed is bounded from below by a constant times its squared diameter.
The same holds for a triangular container given by its side lengths.
The container is an arbitrary triangle: If the container is an arbitrary non-fat triangle given by its side lengths, there can be a constant factor approximation for the maximum number of unit disks that can be packed into it obtained in polynomial time.
The objects to be packed are unit disks or unit spheres: Given a convex container, such that its area is bounded from below by a constant times its squared diameter, there is a PTAS for computing the maximum number of unit disks that can be packed into it. The same holds for any polygonal container, if its description is not part of the input but part of the problem description and the input is just a scaling factor for it. We also obtain a PTAS for a similar problem in three dimensions: Given a sphere by its radius, what is the maximum number of unit spheres that can be packed into it? For this result, we revisit parts of the proof of Hales to obtain the following result: There exists a constant c such that for every packing of infinitely many unit spheres into three dimensional space, the density inside a sphere of radius r is bounded from above by π*√(18)+c/r. It is crucial, that c is, in contrast to the proof of Hales et al., independent of the packing.
Most variants of the problems just mentioned have in common that their input is very concise, i.e., it consists only of a constant number of numbers. Therefore, it seems hard to prove any kind of hardness or give algorithms and indeed, neither one of the problems just mentioned is known to be NP-hard nor to be in NP. To our knowledge, these are the first results of the approximability for this kind of problems with mentioned concise input and therefore, the first about the complexity of this kind of problems.
The next result differs from the previously studied problems in the sense that the input is larger. It is the last result in the first part of the thesis.
Packing unit disks in 3D under translation: In three dimensions, there is to our knowledge no approximation algorithm known for packing objects different from axis-parallel boxes under translation whereas in two dimensions, there is a constant factor approximation for packing convex polygons under translations minimizing the area of the smallest axis-parallel rectangular or convex container. We make a step towards packing more general objects in three dimensions by giving a constant factor approximation for packing unit disks under translation into an axis-parallel box with minimum volume. Furthermore, we show that there can not be a convex container of bounded volume such that all possible unit disks can be packed into it. This is in contrast to the equivalent two dimensional problem where all possible segments with length one can be packed for example into half a circle of radius two.
The second part of the thesis studies the complexity of two basic two-dimensional packing problems. Minimum area container packing: It is known that there can not be a PTAS for Strippacking unless P=NP but there exists a constant factor approximation algorithm. For packing convex polygons under translation into minimum area convex or axis-parallel rectangular containers, there is a constant factor approximation. Unlike for Strippacking, it is not known whether a PTAS can exist or not. We narrow this gap by showing that there can not exist a FPTAS unless P=NP. The same holds when we allow rotations by 90° additionally to translations.
Line segment packing: Kim and Miltzow showed that maximizing the number of line segments from a given set of line segments that can be packed into a simple polygon is NP-hard. We strengthen this result by showing that packing the maximum number of line segments into a square is \NP-hard, albeit we allow parallel line segments, which is not necessary for Kim and Miltzows result.
