Introduction
Packing problems are among the most fundamental and practically motivated problems in computational geometry and combinatorial optimization. They arise in a wide range of real-world scenarios, for instance when cutting shaped pieces from fabric, arranging parts for milling, waterjet cutting and laser cutting, and placing objects for 3D printing (see Figure 1 ). In many of these applications, the objects are irregular and nonconvex, and their edges are not restricted to a fixed set of orientations.
Figure 1. Examples of applications involving irregular packing. Left: Garment pieces arranged on fabric, kindly provided by MIRISYS and produced by their automatic nesting software. Right: Waterjet cutting. The image was cropped from a photograph by Steve Brown Photography, licensed under CC BY 3.0.
The bulk of the theoretical work on geometric packing has focused on axis-parallel rectangles; for surveys with hundreds of references, see [13 , 39 , 40 , 15 ] . A smaller body of theoretical work considers packing convex polygons with unrestricted edge orientations. This includes algorithms for a constant number of pieces [7 , 38 , 4 , 34 ] and approximation algorithms for arbitrary-sized input sets [5 , 6 , 2 , 27 , 1 ] . Related results concern geometric knapsack [33 ] and the exact complexity of packing under rotations [8 ] . For convex objects, classical techniques such as density arguments are effective.
Packing nonconvex polygons remains poorly understood from the viewpoint of polynomial-time approximation algorithms. Early geometric methods capable of handling arbitrary simple polygons were developed by Milenkovic and by Daniels and Milenkovic [32 , 30 , 31 , 29 , 18 ] . They gave exact algorithms for several containment and enclosure problems, as well as algorithms allowing a controlled geometric error, but with running times exponential in the number of pieces. Further exact approaches to irregular nesting have been developed using constraint programming, mixed-integer programming, branch-and-bound and global optimization [14 , 22 , 9 , 26 ] . Some of these methods solve a discretized version of the geometric problem, whereas methods addressing continuous placements generally apply only to relatively small instances. More recently, Gerlach, Hennies and Kleist [23 ] initiated the study of online packing of nonconvex orthogonal polygons.
The scarcity of polynomial-time worst-case results stands in sharp contrast to the extensive operations-research literature on irregular cutting and packing. A series of surveys and bibliographies collectively covering hundreds of works documents mathematical models, geometric techniques, exact approaches, heuristics and metaheuristics [17 SP92, 16 , 11 , 12 , 25 LTO+20, 24 ] . Optimization-based approaches may certify optimality on manageable instances, sometimes only after discretizing the possible placements, whereas heuristic methods are designed to produce high-quality solutions in practice but typically provide no worst-case approximation guarantees. This research has led to multiple software systems used in practice.8 The 2024 edition of the CG:SHOP Challenge (Computational Geometry: Solving Hard Optimization Problems) also concerned a packing problem involving irregular and nonconvex objects [21 ] . Thus, the theoretical gap does not reflect a lack of interest in irregular packing. Rather, there is a striking contrast between a mature experimental and operations-research literature and the very limited theory of polynomial-time approximation.
Every previously known polynomial-time algorithm with an approximation factor of o ( n ) o(n) o ( n ) , i.e., better than what is obtained by packing the convex hulls, for packing an arbitrary number n n n of polygons with arbitrary edge orientations requires the polygons to be convex. In fact, no such algorithm was known even when every input polygon was a quadrilateral, the simplest type of polygon that can be nonconvex. We obtain such algorithms for the entire class of star-shaped polygons, without restricting their combinatorial complexity. Recall that a polygon P P P is said to be star-shaped if there is a point q ∈ P q \in P q ∈ P that sees all of P P P , i.e., for every point p ∈ P p \in P p ∈ P , we have q p ⊆ P qp \subseteq P q p ⊆ P . The set of points for which this holds is called the kernel of P P P . The radius of P P P is the segment from a fixed point q q q in the kernel to a furthest vertex. In concurrent and independent work, de Oliveira Silva, Dell’Arriva, and Miyazawa [19 ] give asymptotic approximation schemes for translational bin packing of nonconvex polygons from classes that satisfy certain structural conditions. Their main example of such a nonconvex class consists of the homothetic copies of a fixed finite set of star-shaped polygons, so only a fixed finite set of edge orientations occurs.
We focus primarily on the minimum-area convex-container problem (MACC). Given a set of n n n polygons, the goal is to place them without overlap so as to minimize the area of their convex hull [5 , 6 ] (related online variants require the container to be an axis-parallel rectangle or square [3 , 20 ] ). Equivalently, we seek a minimum-area convex container whose shape and the placement of the objects are both chosen by the algorithm. We analyze two variants. In the translational variant, the objects may only be translated. In the rotational variant, they may be both translated and rotated.
Our Contribution
Our main result is the following.
Theorem 1. There are polynomial-time O ( log n ) O(\log n) O ( log n ) -approximation algorithms for both translational and rotational packing of n n n star-shaped polygons into a minimum-area convex container .
The translational algorithm is built from simple steps. We first pack the stars into convex mini-containers of total area O ( log n ) ⋅ O P T O(\log n) \cdot\mathrm{OPT} O ( log n ) ⋅ OPT , and then pack the mini-containers as convex objects using existing methods by Alt, de Berg, and Knauer [5 , 6 ] . All nonconvex interactions are handled inside the mini-containers; at the global level only convex geometry remains.
To create the mini-containers, the stars are grouped by size and shape, and similar stars are nested into stacks , much like a stack of bowls. The order within a stack is found using an approximation algorithm for the asymmetric traveling salesperson problem [36 , 37 ] . The convex hulls of the stacks serve as the mini-containers.
In the rotational case, we show that we lose only an extra constant factor by rotating the stars in each mini-container so they have horizontal radii. Our algorithm thus rotates the stars to have horizontal radii and then applies the translational algorithm.
The constants in our analysis are large, mainly due to the very fine grouping of the stars and pessimistic choices of scaling factors. However, the idea of building stacks of similar stars is natural, and we believe that it could also be the basis for practical heuristics, which would be interesting to evaluate experimentally.
The mini-container approach extends to other packing problems for which algorithms are known for convex polygons. In bin packing , the goal is to pack the objects into a minimum number of unit-square bins; in strip packing , the objects are packed into a unit-width strip, and the goal is to minimize the used length of the strip. Rearranging the packing produced in Theorem 1 gives the following. The details are in Section A.
Corollary 2. There exists a constant δ > 0 \delta> 0 δ > 0 such that, if every polygon has diameter at most δ \delta δ , there are polynomial-time O ( log n ) O(\log n) O ( log n ) -approximation algorithms for both translational and rotational bin packing and strip packing of n n n star-shaped polygons.
For stars of comparable size, the algorithms in fact give O ( 1 ) O(1) O ( 1 ) -approximations, that is, if the convex hulls of all input stars have areas within a constant factor of each other (in particular, if all stars are identical). The logarithmic factor is inherent to any algorithm that groups stars by size before packing them into convex mini-containers, as we show in § 2 . The grouping step itself does not use that the polygons are stars, and we formalize it as a reduction for general polygons, proved in Section B. We believe it can be useful for designing algorithms for other classes of polygons.
Theorem 3. For some constants ϵ , δ ∈ ( 0 , 1 ) \epsilon, \delta\in(0, 1) ϵ , δ ∈ ( 0 , 1 ) , if there exists a polynomial-time α \alpha α -approximation translational bin packing algorithm for polygons of diameter at most ϵ \epsilon ϵ and convex hull area at least δ ϵ 2 \delta\epsilon^{2} δ ϵ 2 , then there exists a polynomial-time O ( α log n ) O(\alpha\log n) O ( α log n ) -approximation algorithm for translational packing of n n n polygons into a minimum-area convex container.
Finally, we complement the algorithmic results by proving APX-hardness, even for stars of comparable sizes and constant complexity.
Theorem 4. The translational and rotational variants of minimum-area convex-container packing are APX-hard. In the instances produced by our reduction, each star has at most 17 vertices and the convex hulls are fat and have diameters within a constant factor of each other.
The next section gives an overview of the techniques behind these results.
Technical overview
Our overall approach is to partition the stars and to pack each set of the partition into convex mini-container . We will then use the techniques of Alt, de Berg, and Knauer [5 , 6 ] to pack the mini-containers. In particular, we use the following result as a black box.
Theorem 5 (Theorem 2.2 from [5 , 6 ] ). There exists an O ( N log N ) O(N \log N) O ( N log N ) -time algorithm for packing a given set of convex polygons C 1 , … , C n C_1, \ldots, C_n C 1 , … , C n of total complexity N N N into an axis-aligned rectangle R R R such that
∣ R ∣ ≤ c ⋅ ( ∑ i = 1 n ∣ C i ∣ + ℓ max h max ) |R| \le c \cdot\left(\sum_{i=1}^{n} |C_i| + \ell_{\max} h_{\max}\right) ∣ R ∣ ≤ c ⋅ ( i = 1 ∑ n ∣ C i ∣ + ℓ m a x h m a x ) where ∣ ⋅ ∣ |\cdot| ∣ ⋅ ∣ denotes area, c c c is a constant, and ℓ max \ell_{\max} ℓ m a x and h max h_{\max} h m a x are the maximum horizontal and vertical spans of C 1 , … , C n C_1, \ldots, C_n C 1 , … , C n , respectively.
The goal is to obtain a packing whose convex hull is O ( log n ) ⋅ O P T O(\log n) \cdot\mathrm{OPT} O ( log n ) ⋅ OPT , where O P T \mathrm{OPT} OPT is the area of a minimum convex container for all the stars. To this end, we need two properties: (1) the total area of the mini-containers is O ( log n ) ⋅ O P T O(\log n) \cdot\mathrm{OPT} O ( log n ) ⋅ OPT , and (2) for each mini-container, its extend in every direction is proportional to that of each of the stars that it contains. The latter requirement ensures the bound ℓ max h max = O ( O P T ) \ell_{\max}h_{\max} = O(\mathrm{OPT}) ℓ m a x h m a x = O ( OPT ) in Theorem 5 in the coordinate system where the longest radius is horizontal.
Stacks. For now, consider a much simpler setting: we are given n n n stars P 1 , … , P n P_1,\ldots,P_n P 1 , … , P n that are all copies of the same star P P P . One might ask: For which P P P does packing the convex hulls of the P i P_i P i , instead of the stars themselves, give a good approximation?
The answer is surprisingly nuanced. If P P P is convex, the answer is of course “always”. But there are also polygons of zero area for which the answer is yes. Consider the polygon P P P given by the union of the two segments { 0 } × [ − 1 , 1 ] \{0\} \times[-1,1] { 0 } × [ − 1 , 1 ] and [ − 1 , 1 ] × { 0 } [-1,1] \times\{0\} [ − 1 , 1 ] × { 0 } , forming a plus. For two copies of P P P , no matter how they are arranged, their origins never have ℓ ∞ \ell_\infty ℓ ∞ -distance less than 1. One can, in fact, replace P P P by the square Q = [ − 0.5 , 0.5 ] × [ − 0.5 , 0.5 ] Q = [-0.5,0.5] \times[-0.5,0.5] Q = [ − 0.5 , 0.5 ] × [ − 0.5 , 0.5 ] : any packing of n n n copies of P P P is also a packing of n n n copies of Q Q Q , and vice versa; see Figure 2 a). The convex hull of P P P has twice the area of Q Q Q , so packing the convex hulls of copies of P P P is, up to constants, as good as packing the copies of P P P .
Figure 2. a) Duality between packing copies of a plus-shaped polygon and axis-aligned squares. b) a packing of many L-shapes as a stack in a constant-sized container.
If we instead take P P P to be the union of the two segments { 0 } × [ 0 , 1 ] \{0\} \times[0,1] { 0 } × [ 0 , 1 ] and [ 0 , 1 ] × { 0 } [0,1] \times\{0\} [ 0 , 1 ] × { 0 } , forming an L, the answer is very different. For any ε > 0 \varepsilon> 0 ε > 0 , one can pack n n n copies of P P P into the convex container [ 0 , 1 + ε ] × [ 0 , 1 + ε ] [0,1+\varepsilon] \times[0,1+\varepsilon] [ 0 , 1 + ε ] × [ 0 , 1 + ε ] by forming a stack of nested copies of P P P (see Figure 2 b)), whereas packing the convex hulls requires a container of area Θ ( n ) \Theta(n) Θ ( n ) .
Our main structural insight is that this stacking behavior is the only structure that prevents us from replacing stars by their convex hulls, at a loss of O ( log n ) O(\log n) O ( log n ) .
Size groups and fine types. For arbitrary instances we do not have the luxury of congruent polygons, but we still want to treat the input polygons as somewhat congruent objects. For this, fix for every star P P P a point q P q_P q P in its kernel, its reference point . The radius of P P P is the segment from q P q_P q P to a farthest point R P R_P R P of P P P (ties are broken arbitrarily), and r P r_P r P is its length. The width w P w_P w P of P P P is the largest distance of a point of P P P from the line through the radius, and L P L_P L P is a point attaining it; see Figure 3 . Let r max r_{\max} r m a x and w max w_{\max} w m a x be the maximum radius length and width of any input star.
Figure 3. A star P P P with reference point q P q_P q P , radius q P R P q_PR_P q P R P of length r P r_P r P , and width w P w_P w P attained at L P L_P L P .
We partition the input stars into size groups G a , b \mathcal{G}_{a,b} G a , b , which contains all stars with radius and width of one dyadic scale , i.e., stars P P P such that r P ∈ ( r max / 2 a + 1 , r max / 2 a ] r_P \in(r_{\max}/2^{a+1}, r_{\max}/2^a] r P ∈ ( r m a x / 2 a + 1 , r m a x / 2 a ] and w P ∈ ( w max / 2 b + 1 , w max / 2 b ] w_P \in(w_{\max}/2^{b+1}, w_{\max}/2^b] w P ∈ ( w m a x / 2 b + 1 , w m a x / 2 b ] . Polygons with a > log n a > \log n a > log n or b > log n b > \log n b > log n are packed via their convex hulls: each of these hulls has area O ( r max w max / n ) O(r_{\max}w_{\max}/n) O ( r m a x w m a x / n ) , so together they need area O ( r max w max ) = O ( O P T ) O(r_{\max}w_{\max}) = O(\mathrm{OPT}) O ( r m a x w m a x ) = O ( OPT ) . We are left with polygons in O ( log 2 n ) O(\log^2 n) O ( log 2 n ) size groups , where the size group of a , b a,b a , b has scales r = r max / 2 a r = r_{\max}/2^a r = r m a x / 2 a and w = w max / 2 b w = w_{\max}/2^b w = w m a x / 2 b .
We partition the size groups further into fine types . The orientation of a star is the direction of its radius, directed away from q P q_P q P . We split [ 0 , 2 π ) [0,2\pi) [ 0 , 2 π ) into intervals of length Θ ( w / r ) \Theta(w/r) Θ ( w / r ) , and the fine type of a star is the interval containing its orientation, together with the side of the radius on which L P L_P L P lies; the precise parameters are fixed in § 3.1 . Polygons of one fine type are similar enough that the stacks observed above make sense.
We would now like to pack every fine type independently. The problem is that there might be up to n n n nonempty fine types, and bounding the area of each of them independently against OPT could result in a Θ ( n ) \Theta(n) Θ ( n ) -approximation. Luckily, this is not the case.
A structural theorem for fine types. Consider one fixed size group. Our first main technical contribution is the following theorem.
Theorem 6. Let P \mathcal{P} P be a set of star-shaped polygons in one size group with scales r , w r,w r , w , and let Π \Pi Π be a packing of P \mathcal{P} P in a convex container C C C . Then P \mathcal{P} P can be partitioned into a disjoint union of parts
P = P 1 ∪ ˙ ⋯ ∪ ˙ P t \mathcal{P} = \mathcal{P}_1 \mathbin{\dot\cup} \cdots\mathbin{\dot\cup} \mathcal{P}_t P = P 1 ∪ ˙ ⋯ ∪ ˙ P t such that in every part P j \mathcal{P}_j P j , all the stars are of the same fine type, and, without changing the placement inherited from Π \Pi Π , are contained in a (not necessarily axis-aligned) rectangle B j B_j B j of dimensions O ( r ) × O ( w ) O(r) \times O(w) O ( r ) × O ( w ) . Moreover,
∑ j = 1 t ∣ B j ∣ = O ( ∣ C ∣ ) , \sum_{j=1}^{t} |B_j| = O(|C|), j = 1 ∑ t ∣ B j ∣ = O ( ∣ C ∣ ) , where ∣ C ∣ |C| ∣ C ∣ is the area of C C C .
We sketch the proof here; § 3.2 proves the slightly stronger Theorem 10 . First, split the polygons of the size group by orientation into ( π / 100 ) (\pi/100) ( π /100 ) -radian classes; there are constantly many of these. Within one class, all radii can be considered to be nearly horizontal, and we may take C C C to be a parallelogram with vertical sides of length H H H and horizontal span W W W . Cut C C C into vertical strips of width ε r \varepsilon r ε r , and consider the stars with reference point in a fixed strip. Each of their radii has length more than r / 2 r/2 r /2 and is nearly horizontal, so it crosses two vertical test lines ℓ 1 , ℓ 2 \ell_1,\ell_2 ℓ 1 , ℓ 2 placed Θ ( r ) \Theta(r) Θ ( r ) to the right of the strip; see Figure 4 . Partition each test line into m = O ( H / w ) m=O(H/w) m = O ( H / w ) intervals of length ε w \varepsilon w εw , and assign each star the pair ( a , b ) (a,b) ( a , b ) of intervals crossed by its radius. Two radii ordered one way on ℓ 1 \ell_1 ℓ 1 and the other way on ℓ 2 \ell_2 ℓ 2 would cross in between, which is impossible since every radius lies inside its star. Hence the occupied pairs are monotone in both coordinates, and there are at most 2 m = O ( H / w ) 2m=O(H/w) 2 m = O ( H / w ) of them rather than m 2 m^2 m 2 .
Figure 4. Left: The enclosing parallelogram is cut into vertical strips of width ε r \varepsilon r ε r ; one strip is shown. Two test lines ℓ 1 , ℓ 2 \ell_1,\ell_2 ℓ 1 , ℓ 2 are placed to its right. The reference points and radii assigned to one pair ( a , b ) (a,b) ( a , b ) of intervals are shown. Right: The occupied interval pairs form a monotone sequence in [ m ] 2 [m]^2 [ m ] 2 .
The stars assigned the same pair ( a , b ) (a,b) ( a , b ) and of the same fine type form one part P j \mathcal{P}_j P j . For stars assigned to the same pair ( a , b ) (a,b) ( a , b ) , their reference points lie in a strip of width ε r \varepsilon r ε r , and their radii pass through the same two intervals of length ε w \varepsilon w εw at distance Θ ( r ) \Theta(r) Θ ( r ) , so their orientations differ by O ( w / r ) O(w/r) O ( w / r ) and they belong to constantly many fine types. They also fit, in place, into a rectangle of dimensions O ( r ) × O ( w ) O(r)\times O(w) O ( r ) × O ( w ) . There are O ( W / r ) O(W/r) O ( W / r ) strips, each with O ( H / w ) O(H/w) O ( H / w ) occupied pairs, each contributing area O ( r w ) O(rw) O ( r w ) , so the rectangles over all parts have total area O ( W H ) = O ( ∣ C ∣ ) O(WH)=O(|\mathcal{C}|) O ( W H ) = O ( ∣ C ∣ ) .
Stacks of bowls. By Theorem 6 it suffices to pack each fine type separately. As alluded to above, polygons of one fine type are “congruent enough” that we expect them to admit a nice stack. To find such a stack, we first align the stars of one fine type with each other, as follows. Fix a fine type of a size group with scales r r r and w w w , and let d d d be a direction, depending only on the fine type, that is nearly perpendicular to all its radii. For a star P P P , extend the two segments q P R P q_P R_P q P R P and q P L P q_P L_P q P L P beyond R P R_P R P and L P L_P L P until both endpoints are at height exactly h = Θ ( w ) h=\Theta(w) h = Θ ( w ) above q P q_P q P in direction d d d . The value h h h is common for all stars of the same fine type. We call these two extended segments the arms of P P P , and the polygon Q ( P ) Q(P) Q ( P ) obtained by adding the arms to P P P the bowl of P P P ; see Figure 5 . A bowl (i) extends at most a distance h h h below q P q_P q P in direction d d d , (ii) extends exactly a distance h h h above q P q_P q P , and (iii) satisfies
Figure 5. A star P P P (left) and its bowl Q ( P ) Q(P) Q ( P ) (right). The arms of the bowl are the extensions of q P R P q_P R_P q P R P and q P L P q_P L_P q P L P to height h h h in direction d d d . The bowl sits inside a copy of P P P scaled by the constant α \alpha α .
P ⊂ Q ( P ) ⊂ q P + α ( P − q P ) (1) P \subset Q(P) \subset q_P+\alpha(P-q_P) \tag*{(1)} P ⊂ Q ( P ) ⊂ q P + α ( P − q P ) (1)
for a universal constant α \alpha α ; see Lemma 11 for the detailed proof. By Equation (1) , packing the bowls instead of the stars costs at most a factor α 2 \alpha^2 α 2 , and any packing of bowls contains a valid packing of the stars. This is where star-shapedness of our pieces is crucial: star-shapedness ensures that scaling with q P q_P q P fixed results in a superset of the original polygon P P P .
Stacks of bowls are (informally) defined as follows: a sequence of bowls Q 1 , … , Q j Q_1,\ldots,Q_j Q 1 , … , Q j forms a stack if the reference point of each Q i Q_i Q i lies in the triangle spanned by the arms of Q i − 1 Q_{i-1} Q i − 1 . § 3.3 gives the formal definition, phrased via separators .
Stacking bowls is (almost) optimal. It turns out that packing bowls arbitrarily and packing bowls into stacks are essentially the same.
Theorem 7. Let P \mathcal{P} P be a set of star-shaped polygons of one fine type, and let Π \Pi Π be a packing of P \mathcal{P} P in a convex container C C C . The bowls of the stars in P \mathcal{P} P can be packed into strict stacks in mini-containers with total area O ( ∣ C ∣ ) O(|C|) O ( ∣ C ∣ ) .
We sketch the proof. The details are in § 3.4 ; see in particular Lemma 12. We first replace the stars of a part by their bowls: Scale the packing of P j \mathcal{P}_j P j by the factor α \alpha α and place each bowl Q ( P ) Q(P) Q ( P ) at the scaled copy of q P q_P q P ; see Figure 6 . Each bowl will lie inside its scaled star by Equation (1) , so the bowls do not overlap and fit into the scaled copy of B j B_j B j . Now take two bowls Q 1 , Q 2 Q_1,Q_2 Q 1 , Q 2 of the part with q 2 q_2 q 2 higher than q 1 q_1 q 1 in direction d d d . We will show that, if q 2 q_2 q 2 were outside the triangle spanned by the arms of Q 1 Q_1 Q 1 , an arm of Q 2 Q_2 Q 2 would cross an arm of Q 1 Q_1 Q 1 , which is impossible. Hence the bowls of P j \mathcal{P}_j P j , ordered along d d d , form a strict stack. The scaled rectangles α B j \alpha B_j α B j , of dimensions O ( r ) × O ( w ) O(r) \times O(w) O ( r ) × O ( w ) , are therefore mini-containers holding strict stacks, and by Theorem 6 their total area is α 2 ∑ j ∣ B j ∣ = O ( ∣ C ∣ ) \alpha^2 \sum_j |B_j| = O(|C|) α 2 ∑ j ∣ B j ∣ = O ( ∣ C ∣ ) .
Figure 6. Left: A part P j \mathcal{P}_j P j with the points q i q_i q i , R i R_i R i , L i L_i L i marked. Right: The scaled stars and the packing of the corresponding bowls, which form a stack.
Computing approximately optimal stacks. Stacking bowls is, algorithmically, very easy; see § 3.5 for the details. Fix a fine type, and for two bowls Q i , Q j Q_i,Q_j Q i , Q j let c ( i , j ) c(i,j) c ( i , j ) be the smallest amount by which Q j Q_j Q j has to be placed higher than Q i Q_i Q i , in direction d d d , so that Q i , Q j Q_i,Q_j Q i , Q j form a stack; see Figure 7 . Translations orthogonal to d d d are free, so c ( i , j ) c(i,j) c ( i , j ) is a single number, and c ( i , j ) ≤ 2 h c(i,j) \le2h c ( i , j ) ≤ 2 h . The height of a stack with a fixed order is the sum of c ( i , j ) c(i,j) c ( i , j ) over consecutive bowls, and we need to choose the order minimizing it. This is a asymmetric metric TSP instance for which a constant-factor approximation [36 , 37 ] gives a stack of height H H H within a constant factor of the minimum; see Lemma 19 .
Figure 7. Two stacked bowls and the height c ( i , j ) c(i,j) c ( i , j ) needed to place Q j Q_j Q j above Q i Q_i Q i . The cost c c c itself is not a metric, but c ′ ( i , j ) = min ( c ( i , j ) , h ) c'(i,j)=\min(c(i,j),h) c ′ ( i , j ) = min ( c ( i , j ) , h ) is.
Finally, the tall stack can be split into short stacks. We therefore cut the stack every Θ ( h ) \Theta(h) Θ ( h ) along d d d and enclose each piece in a rectangle of dimensions O ( r ) × O ( w ) O(r) \times O(w) O ( r ) × O ( w ) ; see Lemma 17 . These rectangles are the mini-containers. Their total area will be O ( r H ) O(rH) O ( r H ) . Moreover, each mini-container has spans within a constant factor of the spans of a star inside it.
Algorithm summary. All the ingredients are now in place for the O ( log 2 n ) O(\log^2 n) O ( log 2 n ) -approximation. The algorithm sets aside the small stars, splits the remaining polygons into their fine types, turns them into bowls, stacks the bowls, and cuts the stacks into mini-containers. Then Theorem 5 packs the mini-containers together with the convex hulls of the small stars into a rectangle. See § 3.7 for the details.
In the case of strip and bin packing, we get Corollary 2 by slicing this rectangle along vertical and horizontal lines. We then rearrange the slices, each with its mini-containers, in the strip or the bins. See Section A for the details.
Shaving a log-factor. The factor O ( log 2 n ) O(\log^2 n) O ( log 2 n ) comes from packing the O ( log 2 n ) O(\log^2 n) O ( log 2 n ) size groups independently of each other. Some loss here is unavoidable, as we will show at the end of this paragraph, but we can show that the total loss is actually only O ( log n ) O(\log n) O ( log n ) . Recall that G a , b \mathcal{G}_{a,b} G a , b is the size group with scales r = r max / 2 a r=r_{\max}/2^a r = r m a x / 2 a and w = w max / 2 b w=w_{\max}/2^b w = w m a x / 2 b . For a fixed k k k , the stars in the groups with a + b = k a+b=k a + b = k have comparable convex hull areas, Θ ( r max w max / 2 k ) \Theta(r_{\max}w_{\max}/2^k) Θ ( r m a x w m a x / 2 k ) , but very different shapes, ranging from long and thin (a a a small) to short and fat (a a a large). A charging argument exploits both facts to show that for every k k k ,
∑ a + b = k OPT ( G a , b ) = O ( OPT ) . \sum_{a+b=k} \operatorname{OPT}(\mathcal{G}_{a,b}) = O(\operatorname{OPT}). a + b = k ∑ OPT ( G a , b ) = O ( OPT ) .
Summing over the O ( log n ) O(\log n) O ( log n ) values of k k k gives ∑ a , b OPT ( G a , b ) = O ( log n ) ⋅ OPT \sum_{a,b} \operatorname{OPT}(\mathcal{G}_{a,b})=O(\log n)\cdot\operatorname{OPT} ∑ a , b OPT ( G a , b ) = O ( log n ) ⋅ OPT , which is exactly the bound we need on the total area of the mini-containers.
The charging argument works as follows. Give every star P P P a core, which is a small copy of the triangle q P R P L P q_P R_P L_P q P R P L P sitting above the middle of the radius; see Figure 8 . A core has area Θ ( r P w P ) \Theta(r_Pw_P) Θ ( r P w P ) , so for a + b = k a+b=k a + b = k all cores have the same area, and we can charge the area of a packing to the cores it contains. Two things make this work. Cores of stars from different groups with a + b = k a+b=k a + b = k cannot overlap: a short and fat star whose core covers a point of a long and thin star’s core would have to cross the thin star’s radius; see Lemma 22 for the details. And within one group, all stars whose cores overlap the core of P P P fit into one rectangle of dimensions O ( r ) × O ( w ) O(r) \times O(w) O ( r ) × O ( w ) , because their radii cannot cross that of P P P ; see Lemma 23 for the details. So, a packing of all groups with a + b = k a+b=k a + b = k contains as many disjoint cores as the groups do separately, and each group can be packed into a constant times as many rectangles as it has disjoint cores. The details are included in § 3.6 .
Figure 8. The core of a star P i P_i P i is the gray triangle.
The log n \log n log n in the approximation factor is inherent to our approach. Consider, for k = 0 , … , K k=0,\ldots,K k = 0 , … , K , 4 k 4^k 4 k copies of a plus, scaled by 2 − k 2^{-k} 2 − k ; see Figure 9 . For a single scale we saw earlier that pluses behave like squares, and packing their convex hulls is fine. Across scales, however, the pluses of scale 2 − k 2^{-k} 2 − k nest into the gaps between the pluses of scale 2 − k + 1 2^{-k+1} 2 − k + 1 , so all Θ ( 4 K ) \Theta(4^K) Θ ( 4 K ) pluses fit into a container of area O ( 1 ) O(1) O ( 1 ) , whereas each scale on its own needs area Ω ( 1 ) \Omega(1) Ω ( 1 ) . Any algorithm that packs size groups into separate convex mini-containers thus loses Ω ( log n ) \Omega(\log n) Ω ( log n ) on this instance, and any mini-container based o ( log n ) o(\log n) o ( log n ) -approximation has to mix size groups within a mini-container.
Figure 9. Pluses of Θ ( log n ) \Theta(\log n) Θ ( log n ) different scales nested into a region of constant area. Packing each scale into its own convex mini-containers requires area Ω ( 1 ) \Omega(1) Ω ( 1 ) per scale.
Rotations. In the rotational variant the algorithm chooses the orientation of each star, so fine types are no longer a property of the input. We get around this with a preprocessing step, after which we simply apply our translation-only algorithm. For a size group G G G , let G ^ \widehat{G} G be obtained by rotating every star so that its radius is horizontal. We show in Corollary 35 that
OPT t r a n s ( G ^ ) = Θ ( OPT r o t ( G ) ) , \operatorname{OPT}_{\mathrm{trans}}(\widehat{G}) = \Theta(\operatorname{OPT}_{\mathrm{rot}}(G)), OPT trans ( G ) = Θ ( OPT rot ( G )) ,
where OPT t r a n s \operatorname{OPT}_{\mathrm{trans}} OPT trans and OPT r o t \operatorname{OPT}_{\mathrm{rot}} OPT rot are the optimum values under translation, and under translation and rotation respectively. This allows us to simply run the translational algorithm on G ^ \widehat{G} G ; see Figure 10 .
Figure 10. Left: A stack of one fine type in its rectangle. Right: Rotating all radii to the same orientation only scales the rectangle by a constant factor.
The lower bound is trivial, since a translational packing of G ^ \widehat{G} G is a rotational packing of G G G . For the upper bound, take an optimal rotational packing of G G G , freeze the chosen rotations, and apply Theorems 6 and 7 to the rotated stars (Lemma 28 ). This gives stacks of bowls in rectangles of dimensions O ( r ) × O ( w ) O(r) \times O(w) O ( r ) × O ( w ) with total area O ( O P T r o t ( G ) ) O(\mathrm{OPT}_{\mathrm{rot}}(G)) O ( OPT rot ( G )) , in which the radii are already within an angle of O ( w / r ) O(w/r) O ( w / r ) of each other. It remains to make them exactly parallel without blowing up the rectangles. We show that, with θ i \theta_i θ i the direction of the i i i th radius in stack order,
∑ i ∣ θ i + 1 − θ i ∣ = O ( w / r ) , \sum_i \lvert\theta_{i+1} - \theta_i \rvert= O(w/r), i ∑ ∣ θ i + 1 − θ i ∣ = O ( w / r ) ,
because the arms of consecutive bowls cannot cross, which lets us charge each change of direction to the height of the stack, which is O ( w ) O(w) O ( w ) ; see Lemma 29 . We then straighten the stack bowl by bowl, each time rotating the whole suffix above the current bowl so that the next radius becomes parallel, and shifting it to restore the stack (Lemma 32 ). The total displacement is O ( r ∑ i ∣ θ i + 1 − θ i ∣ ) = O ( w ) O(r \sum_i \lvert\theta_{i+1} - \theta_i \rvert) = O(w) O ( r ∑ i ∣ θ i + 1 − θ i ∣) = O ( w ) across the stack and O ( r ) O(r) O ( r ) along it, so the rectangles only grow by a constant factor; see Theorem 33 .
APX-hardness. We reduce from MAX-VERTEX-DISJOINT-PATH-COVER. Here we are given a directed graph G = ( V , E ) G = (V, E) G = ( V , E ) on V = { 1 , … , n } V = \{1, \ldots, n\} V = { 1 , … , n } with in- and out-degree at most 2, and the goal is to find a set of vertex-disjoint paths covering all vertices and using as many edges as possible. Equivalently, we want an ordering u 1 , … , u n u_1, \ldots, u_n u 1 , … , u n of the vertices maximizing the number of consecutive pairs ( u i , u i + 1 ) (u_i, u_{i+1}) ( u i , u i + 1 ) that are edges. Bosboom, Demaine, Demaine, Hesterberg, Manurangsi and Yodpinyanee [10 ] showed that it is NP-hard to distinguish graphs with a Hamiltonian path, that is, a path cover with ∣ V ∣ − 1 \lvert V \rvert- 1 ∣ V ∣ − 1 edges, from graphs where every path cover has fewer than ( 1 − ε ) ( ∣ V ∣ − 1 ) (1 - \varepsilon)(\lvert V \rvert- 1) ( 1 − ε ) (∣ V ∣ − 1 ) edges, for ε < 1 1396640 \varepsilon< \frac{1}{1396640} ε < 1396640 1 (restated as Lemma 37).
We create a star S i S_i S i for every vertex i i i , designed so that any near-optimal packing is a stack; see Figure 11 . Two long arms give S i S_i S i the overall shape of a wedge, which makes the stars stackable. Below the arms is a spike whose angle encodes i i i , and between the arms are up to two slits whose angles encode the out-neighbours of i i i . The spike of S j S_j S j fits into a slit of S i S_i S i if and only if ( i , j ) ∈ E (i,j) \in E ( i , j ) ∈ E . If it does not fit, stacking S j S_j S j on top of S i S_i S i costs about the height of the spike extra (Lemma 42). A single container piece C C C with even longer arms forces all S i S_i S i to form a stack between its arms in any near-optimal packing (Lemmas 39 to 41 ). If this stack is a Hamiltonian path, that is, every spike sits in a slit of the star directly below, then the stack fits inside the convex hull of C C C (Lemma 38 ). Otherwise it sticks out above C C C by an amount proportional to the number of unmatched pairs. We show, for some constant δ > 0 \delta> 0 δ > 0 , that it is NP-hard to distinguish instances where everything fits inside the convex hull of C C C from instances that need a ( 1 + δ ) (1+\delta) ( 1 + δ ) factor more area; see Theorem 43 .
Figure 11. Left: A graph G G G with in- and out-degree at most 2 and a Hamiltonian path. Right: The corresponding stack of the pieces S i S_i S i inside the convex hull of the container piece C C C .
Algorithm for translational packing
In this section, we present the details of our O ( log n ) O(\log n) O ( log n ) approximation for packing stars translationally into a minimum-area convex container.
In § 3.1 , we define some parameters of stars and show how to partition them into size groups and fine types.
In § 3.2 , we prove a structural theorem for the stars in one size group, which splits a size group into fine types without increasing the cost by more than a constant factor.
In § 3.3 , we show how to transform the original stars into bowls.
In § 3.4 , we prove that packing bowls of each fine type into a stack would only increase the optimal cost by at most a constant factor.
In § 3.5 , we show how to approximately compute the optimal stacks.
In § 3.6 , we show that packing each size group separately would only introduce an O ( log n ) O(\log n) O ( log n ) factor.
In § 3.7 , we put everything together to prove our main theorem for translational packing.
Throughout this section, all placements use translations only. Changes of coordinates only serve for simplicity of analysis and do not really rotate the stars. We write OPT ( P ) \operatorname{OPT}(\mathcal{P}) OPT ( P ) for the infimum area of a convex container admitting a packing of P \mathcal{P} P , and OPT ′ ( P ) \operatorname{OPT}'(\mathcal{P}) OPT ′ ( P ) for the infimum total area of one or more convex containers admitting a packing of P \mathcal{P} P . By definition, OPT ′ ( P ) ≤ OPT ( P ) \operatorname{OPT}'(\mathcal{P}) \le\operatorname{OPT}(\mathcal{P}) OPT ′ ( P ) ≤ OPT ( P ) .
Parameters, size groups, and fine types
For a star-shaped polygon P P P , recall that the kernel of P P P is the set of points in P P P from which all points in P P P are visible. It is well-known that the kernel is convex. We choose an arbitrary reference point q P q_P q P deterministically in the kernel, for instance, the lexicographically maximal kernel vertex. Let R P R_P R P be an arbitrary farthest point in P P P from q P q_P q P , and let r P r_P r P be the radius length , i.e., the distance between q P q_P q P and R P R_P R P :
R P ∈ arg max z ∈ P ∥ z q P ∥ , r P = ∥ R P q P ∥ . R_P \in\underset{z \in P}{\operatorname{arg\,max}}\ \lVert zq_P\rVert,\qquad r_P = \lVert R_Pq_P\rVert. R P ∈ z ∈ P arg max ∥ z q P ∥ , r P = ∥ R P q P ∥ .
Let e ⃗ P = ( R P − q P ) / r P \vec{e}_P = (R_P-q_P)/r_P e P = ( R P − q P ) / r P be the unit vector along the orientation of P P P , i.e., the direction of the radius. Let L P L_P L P be an arbitrary point in P P P that maximizes the distance from the radius line q P R P ‾ \overline{q_PR_P} q P R P , and let
w P = dist ( L P , q P R P ‾ ) w_P = \operatorname{dist}(L_P,\overline{q_PR_P}) w P = dist ( L P , q P R P )
be the width of P P P . Let v ⃗ P \vec{v}_P v P be the unit vector perpendicular to e ⃗ P \vec{e}_P e P pointing toward L P L_P L P . See Figure 12 for an illustration.
Figure 12. Left: The reference point, radius, and transverse width of a star P P P . Right: The black vectors are the direction of the radius and the perpendicular for the star P P P from the left. The red vectors are the vectors defining the fine type of P P P .
Note that w P ≤ r P w_P \le r_P w P ≤ r P and diam ( P ) ≤ 2 r P \operatorname{diam}(P) \le2r_P diam ( P ) ≤ 2 r P . Without loss of generality, we assume that L P L_P L P lies to the left of the directed radius q P R P → \overrightarrow{q_PR_P} q P R P . Let T P T_P T P denote the triangle △ q P L P R P \triangle q_PL_PR_P △ q P L P R P .
Size groups. Let r max = max P r P r_{\max} = \max_P r_P r m a x = max P r P and w max = max P w P w_{\max} = \max_P w_P w m a x = max P w P . We partition the stars into size groups G a , b \mathcal{G}_{a,b} G a , b for integers a , b ≥ 0 a,b \ge0 a , b ≥ 0 according to their radius lengths and widths. Each G a , b \mathcal{G}_{a,b} G a , b consists of stars with r P ∈ ( r / 2 , r ] r_P \in(r/2,r] r P ∈ ( r /2 , r ] and w P ∈ ( w / 2 , w ] w_P \in(w/2,w] w P ∈ ( w /2 , w ] , where r = r max / 2 a r = r_{\max}/2^a r = r m a x / 2 a and w = w max / 2 b w = w_{\max}/2^b w = w m a x / 2 b . We will pack each group separately.
Lemma 8. For a set of stars P \mathcal{P} P , OPT ( P ) = Ω ( r max w max ) \operatorname{OPT}(\mathcal{P}) = \Omega(r_{\max}w_{\max}) OPT ( P ) = Ω ( r m a x w m a x ) .
Proof. The convex hull of a star of width w P w_P w P contains a disk of radius Ω ( w P ) \Omega(w_P) Ω ( w P ) . So in any packing, the container must have spans of Ω ( w max ) \Omega(w_{\max}) Ω ( w m a x ) in all directions and a span of r max r_{\max} r m a x in one direction.
Without loss of generality, we only consider the groups where a , b ≤ log 2 n a,b \le\log_2 n a , b ≤ log 2 n . All other stars can be packed individually, since the total area of them is O ( r max w max ) O(r_{\max}w_{\max}) O ( r m a x w m a x ) .
Fine types. From now on, we only consider one size group G a , b \mathcal{G}_{a,b} G a , b with scales r = r max / 2 a r = r_{\max}/2^a r = r m a x / 2 a and w = w max / 2 b w = w_{\max}/2^b w = w m a x / 2 b . We are going to further partition the stars into fine types according to their orientations.
Define N = 100 ⌈ r / w ⌉ N = 100\lceil r/w\rceil N = 100 ⌈ r / w ⌉ as the number of fine types in the size group and
δ = 2 π N ≤ π 50 (2) \delta= \frac{2\pi}{N} \le\frac{\pi}{50} \tag*{(2)} δ = N 2 π ≤ 50 π (2)
as the angle range of each fine type. Let D = { ( cos k δ , sin k δ ) : 0 ≤ k < N } D = \{(\cos k\delta,\sin k\delta) : 0 \le k < N\} D = {( cos k δ , sin k δ ) : 0 ≤ k < N } be the set of N N N equally distributed unit vectors.
We create a fine type τ \tau τ for each vector d ⃗ τ ∈ D \vec{d}_\tau\in D d τ ∈ D , and let u ⃗ τ \vec{u}_\tau u τ be the unit vector obtained by rotating d ⃗ τ \vec{d}_\tau d τ by 90 degrees clockwise. For each star P P P , we associate it with the unique fine type τ \tau τ such that the clockwise angular displacement β P \beta_P β P from v ⃗ P \vec{v}_P v P toward d ⃗ τ \vec{d}_\tau d τ is in [ δ , 2 δ ) [\delta,2\delta) [ δ , 2 δ ) . In other words,
d ⃗ τ = sin β P e ⃗ P + cos β P v ⃗ P , u ⃗ τ = cos β P e ⃗ P − sin β P v ⃗ P , β P ∈ [ δ , 2 δ ) . \vec{d}_\tau= \sin\beta_P\vec{e}_P + \cos\beta_P\vec{v}_P,\qquad
\vec{u}_\tau= \cos\beta_P\vec{e}_P - \sin\beta_P\vec{v}_P,\qquad
\beta_P \in[\delta,2\delta). d τ = sin β P e P + cos β P v P , u τ = cos β P e P − sin β P v P , β P ∈ [ δ , 2 δ ) .
See Figure 12 (right) for an illustration.
The orientations of the stars of each fine type form an angular interval of length δ = Θ ( w / r ) \delta= \Theta(w/r) δ = Θ ( w / r ) . Consequently, an interval shorter than δ \delta δ intersects with at most two fine types.
A structural theorem for fine types
We start with an elementary enclosure lemma.
Lemma 9. Every compact convex set C C C of positive area is contained in a vertical parallelogram (that is, a parallelogram with two vertical sides) T T T with ∣ T ∣ ≤ 2 ∣ C ∣ |T| \le2|C| ∣ T ∣ ≤ 2∣ C ∣ .
Proof. Choose a leftmost point p p p and a rightmost point q q q of C C C . Apply a vertical shear making p q pq pq horizontal, and let T ′ T' T ′ be the axis-aligned bounding rectangle of the sheared set. If its width and height are W W W and H H H respectively, the triangles with common base p q pq pq and apices at a highest and a lowest point have disjoint interiors and total area W H / 2 WH/2 W H /2 . They lie in the sheared convex set. The inverse shear maps T ′ T' T ′ to the required parallelogram and preserves area.
The next theorem captures the main structural insight for the original stars. This is a stronger version of Theorem 6 in the sense that it records more local information about the reference points. This is needed later when we transform the stars into bowls.
Theorem 10. Let P \mathcal{P} P be a set of stars in one size group with scales r r r , w w w , and let Π \Pi Π be a packing of P \mathcal{P} P in a convex container C C C . For any 0 < c < 0.1 0<c<0.1 0 < c < 0.1 and 0 < ε < c / 100 0<\varepsilon<c/100 0 < ε < c /100 , there exists a partition
P = P 1 ∪ ˙ ⋯ ∪ ˙ P t . \mathcal{P}=\mathcal{P}_1\dot\cup\cdots\dot\cup\mathcal{P}_t. P = P 1 ∪ ˙ ⋯ ∪ ˙ P t . such that each part P j \mathcal{P}_j P j only contains stars of one fine type τ j \tau_j τ j and we have the following properties (under the placement inherited from Π \Pi Π ):
(i) In each P j \mathcal{P}_j P j , the reference points span at most 10 ε r 10\varepsilon r 10 ε r along u ⃗ τ j \vec{u}_{\tau_j} u τ j and 10 ε w 10\varepsilon w 10 εw along d ⃗ τ j \vec{d}_{\tau_j} d τ j .
(ii) All stars in P j \mathcal{P}_j P j lie in a rectangle B j B_j B j of dimensions O ( r ) × O ( w ) O(r)\times O(w) O ( r ) × O ( w ) , whose sides are parallel to u ⃗ τ j \vec{u}_{\tau_j} u τ j and d ⃗ τ j \vec{d}_{\tau_j} d τ j respectively. Moreover,
∑ j = 1 t ∣ B j ∣ = O ε ( ∣ C ∣ ) . \sum_{j=1}^{t}|B_j|=O_{\varepsilon}(|C|). j = 1 ∑ t ∣ B j ∣ = O ε ( ∣ C ∣ ) .
Proof. We first divide the stars into O ( 1 ) O(1) O ( 1 ) groups such that in each group, the orientations of the stars span at most π / 100 \pi/100 π /100 . Consider one such group. Choose coordinates such that the clockwise angular displacement from each orientation to the positive x x x -axis is in [ 0 , π / 100 ) [0,\pi/100) [ 0 , π /100 ) . Let T T T be the enclosing vertical parallelogram of C C C from Lemma 9. Let R R R be the horizontal span of T T T and W W W be the vertical side length of T T T . Then R W = ∣ T ∣ ≤ 2 ∣ C ∣ RW=|T|\le2|C| R W = ∣ T ∣ ≤ 2∣ C ∣ . Moreover, we have R = Ω ( r ) R=\Omega(r) R = Ω ( r ) and W = Ω ( w ) W=\Omega(w) W = Ω ( w ) .
Then, we partition T T T into O ( R / ( ε r ) ) O(R/(\varepsilon r)) O ( R / ( ε r )) vertical strips of width ε r \varepsilon r ε r , and consider each strip separately. For all stars whose reference points lie in a strip x ∈ [ X k , X k + ε r ) x\in[X_k,X_k+\varepsilon r) x ∈ [ X k , X k + ε r ) , since 0 < c < 0.1 0<c<0.1 0 < c < 0.1 and 0 < ε < c / 100 0<\varepsilon<c/100 0 < ε < c /100 , their radii must cross the two vertical lines
ℓ k , 1 : x = x k + c r , ℓ k , 2 : x = x k + 2 c r . \ell_{k,1}:x=x_k+cr,\qquad\ell_{k,2}:x=x_k+2cr. ℓ k , 1 : x = x k + cr , ℓ k , 2 : x = x k + 2 cr .
Now we partition each of ℓ k , 1 ∩ T \ell_{k,1}\cap T ℓ k , 1 ∩ T and ℓ k , 2 ∩ T \ell_{k,2}\cap T ℓ k , 2 ∩ T into m = O ( W / ( ε w ) ) m=O(W/(\varepsilon w)) m = O ( W / ( εw )) intervals of lengths at most ε w \varepsilon w εw . We say a pair ( a , b ) (a,b) ( a , b ) is occupied if there exists a star whose radius crosses the a a a -th interval on ℓ k , 1 \ell_{k,1} ℓ k , 1 and the b b b -th interval on ℓ k , 2 \ell_{k,2} ℓ k , 2 , ordered from bottom to top. Notice that if a < a ′ a<a' a < a ′ and b > b ′ b>b' b > b ′ , then ( a , b ) (a,b) ( a , b ) and ( a ′ , b ′ ) (a',b') ( a ′ , b ′ ) cannot be both occupied, since otherwise the radii must intersect. So, there are at most 2 m = O ( W / ( ε w ) ) 2m=O(W/(\varepsilon w)) 2 m = O ( W / ( εw )) occupied pairs in each vertical strip. See Figure 13 for an illustration.
Figure 13. Left: The enclosing parallelogram is cut into vertical strips of width ε r \varepsilon r ε r ; one strip is shown. Two test lines ℓ 1 , ℓ 2 \ell_1,\ell_2 ℓ 1 , ℓ 2 are placed to its right. The reference points and radii assigned to one pair ( a , b ) (a,b) ( a , b ) of intervals are shown. Right: The occupied interval pairs form a monotone sequence in [ m ] 2 [m]^2 [ m ] 2 .
Consider each occupied pair ( a , b ) (a,b) ( a , b ) . Note that the slopes of the radii of the stars corresponding to ( a , b ) (a,b) ( a , b ) differ by at most 2 ε w / ( c r ) 2\varepsilon w/(cr) 2 εw / ( cr ) . Since ε < c / 100 \varepsilon<c/100 ε < c /100 , these stars belong to at most 2 fine types. Therefore, we can partition all stars in P \mathcal{P} P into t = O ( R W / ( ε 2 r w ) ) t=O(RW/(\varepsilon^2rw)) t = O ( R W / ( ε 2 r w )) subsets P j \mathcal{P}_j P j such that the stars in each P j \mathcal{P}_j P j correspond to the same occupied pair in the same vertical strip and share the same fine type τ j \tau_j τ j .
Consider each P j \mathcal{P}_j P j . Consider any two stars P 1 , P 2 ∈ P j P_1,P_2 \in\mathcal{P}_j P 1 , P 2 ∈ P j . Write q P 1 = ( x 1 , y 1 ) q_{P_1}=(x_1,y_1) q P 1 = ( x 1 , y 1 ) and q P 2 = ( x 2 , y 2 ) q_{P_2}=(x_2,y_2) q P 2 = ( x 2 , y 2 ) . Since P 1 P_1 P 1 and P 2 P_2 P 2 are in the same vertical strip,
∣ x 1 − x 2 ∣ ≤ ε r . (3) |x_1-x_2| \le\varepsilon r. \tag*{(3)} ∣ x 1 − x 2 ∣ ≤ ε r . (3)
Let p = ( x p , y p ) p=(x_p,y_p) p = ( x p , y p ) be the point on the line q P 1 R P 1 ‾ \overline{q_{P_1}R_{P_1}} q P 1 R P 1 such that y p = y 2 y_p=y_2 y p = y 2 . Then
∣ ( q P 2 − q P 1 ) ⋅ v ⃗ P 1 ∣ = dist ( q P 2 , q P 1 R P 1 ‾ ) ≤ ∥ p q P 2 ∥ ≤ 3 ε w (4) |(q_{P_2}-q_{P_1})\cdot\vec{v}_{P_1}|=\operatorname{dist}(q_{P_2},\overline{q_{P_1}R_{P_1}})\le\|pq_{P_2}\|\le3\varepsilon w \tag*{(4)} ∣ ( q P 2 − q P 1 ) ⋅ v P 1 ∣ = dist ( q P 2 , q P 1 R P 1 ) ≤ ∥ p q P 2 ∥ ≤ 3 εw (4)
since P 1 P_1 P 1 and P 2 P_2 P 2 correspond to the same occupied pair and p p p and q P 2 q_{P_2} q P 2 are at most c r cr cr far from ℓ ⋅ , 1 \ell_{\cdot,1} ℓ ⋅ , 1 . Recall that the angle between e ⃗ P 1 \vec{e}_{P_1} e P 1 and the positive x x x -axis is at most π / 100 \pi/100 π /100 . So, by Equations (3) and (4) , we have
∣ ( q P 2 − q P 1 ) ⋅ e ⃗ P 1 ∣ ≤ 2 ε r . (5) |(q_{P_2}-q_{P_1})\cdot\vec{e}_{P_1}|\le2\varepsilon r. \tag*{(5)} ∣ ( q P 2 − q P 1 ) ⋅ e P 1 ∣ ≤ 2 ε r . (5)
Recall that the angle from e ⃗ P 1 \vec{e}_{P_1} e P 1 to u ⃗ τ j \vec{u}_{\tau_j} u τ j is β P 1 < 2 δ < ( π / 25 ) w / r \beta_{P_1}<2\delta<(\pi/25)w/r β P 1 < 2 δ < ( π /25 ) w / r . So, by Equations (4) and (5) , we have
∣ ( q P 2 − q P 1 ) ⋅ u ⃗ τ j ∣ ≤ 3 ε r , ∣ ( q P 2 − q P 1 ) ⋅ d ⃗ τ j ∣ ≤ 4 ε w , |(q_{P_2}-q_{P_1})\cdot\vec{u}_{\tau_j}|\le3\varepsilon r,\qquad|(q_{P_2}-q_{P_1})\cdot\vec{d}_{\tau_j}|\le4\varepsilon w, ∣ ( q P 2 − q P 1 ) ⋅ u τ j ∣ ≤ 3 ε r , ∣ ( q P 2 − q P 1 ) ⋅ d τ j ∣ ≤ 4 εw ,
which proves (i). Combining (i) with that all stars in P j \mathcal{P}_j P j share the same fine type τ j \tau_j τ j , it is straightforward to see that the dimensions of the bounding rectangle with sides parallel to u ⃗ τ j \vec{u}_{\tau_j} u τ j and d ⃗ τ j \vec{d}_{\tau_j} d τ j are O ( r ) × O ( w ) O(r)\times O(w) O ( r ) × O ( w ) . The total area is O ( t r w ) = O ( R W / ε 2 ) = O ε ( ∣ C ∣ ) O(trw)=O(RW/\varepsilon^2)=O_{\varepsilon}(|\mathcal{C}|) O ( t r w ) = O ( R W / ε 2 ) = O ε ( ∣ C ∣ ) .
Stacks of bowls
We are now going to pack each fine type separately. We focus on one fine type τ \tau τ with orthogonal unit vectors d ⃗ τ \vec{d}_{\tau} d τ and u ⃗ τ \vec{u}_{\tau} u τ . The first step is to transform each star into a bowl which has useful properties.
Bowls. Let d ⃗ , u ⃗ \vec{d},\vec{u} d , u be orthogonal unit vectors. We say that a (possibly weakly simple) star-shaped polygon Q Q Q is a bowl aligned along ( d ⃗ , u ⃗ ) (\vec{d},\vec{u}) ( d , u ) with height h > 0 h>0 h > 0 if it has a specified kernel point q Q q_Q q Q and specified points L Q , R Q L_Q,R_Q L Q , R Q such that
d ⃗ ⋅ ( L Q − q Q ) = d ⃗ ⋅ ( R Q − q Q ) = h , u ⃗ ⋅ L Q < u ⃗ ⋅ R Q , ∀ z ∈ Q , − h ≤ d ⃗ ⋅ ( z − q Q ) ≤ h . \vec{d}\cdot(L_Q-q_Q)=\vec{d}\cdot(R_Q-q_Q)=h,\qquad\vec{u}\cdot L_Q<\vec{u}\cdot R_Q,\qquad\forall z\in Q,\ -h\le\vec{d}\cdot(z-q_Q)\le h. d ⋅ ( L Q − q Q ) = d ⋅ ( R Q − q Q ) = h , u ⋅ L Q < u ⋅ R Q , ∀ z ∈ Q , − h ≤ d ⋅ ( z − q Q ) ≤ h .
We call the two segments q Q L Q q_QL_Q q Q L Q and q Q R Q q_QR_Q q Q R Q the two finite arms of Q Q Q . Note that a bowl is also a star; since q Q , L Q , R Q q_Q,L_Q,R_Q q Q , L Q , R Q also follow their original definition, e.g., R Q R_Q R Q is one of the farthest points from q Q q_Q q Q .
Separators and stacks. Given such a bowl Q Q Q , we define its separator to be the union of these two arms and the two outward rays perpendicular to d ⃗ \vec{d} d .
Separator ( Q ) = { L Q − t u ⃗ : t ≥ 0 } ∪ L Q q Q ∪ q Q R Q ∪ { R Q + t u ⃗ : t ≥ 0 } . \operatorname{Separator}(Q)=\{L_Q-t\vec{u}:t\geq0\}\cup L_Qq_Q\cup q_QR_Q\cup\{R_Q+t\vec{u}:t\geq0\}. Separator ( Q ) = { L Q − t u : t ≥ 0 } ∪ L Q q Q ∪ q Q R Q ∪ { R Q + t u : t ≥ 0 } .
We say that a packing of bowls with the same directions d ⃗ \vec{d} d , u ⃗ \vec{u} u and height h h h forms a stack if their separators are pairwise disjoint. We say that the packing forms a strict stack if, in addition, each separator does not intersect with any other bowl. See Figure 14 for an illustration.
Figure 14. Bowls and their separators. The finite arms belong to the bowls; the two tails extend indefinitely perpendicular to the alignment direction. Disjoint separators define the stack order. The left shows a strict stack , and the right shows a non-strict stack.
Without loss of generality, we assume that d ⃗ \vec{d} d is upward and u ⃗ \vec{u} u is right. Then a separator is a simple curve with two horizontal ray tails at the same height, which divides the plane into an upper region and a lower region. So, in a stack, we can order these disjoint separators (and hence the bowls) vertically.
Lemma 11. For every star P P P of fine type τ \tau τ , there is a bowl Q ( P ) = Q τ ( P ) Q(P)=Q_\tau(P) Q ( P ) = Q τ ( P ) with directions d ⃗ τ , u ⃗ τ \vec{d}_\tau,\vec{u}_\tau d τ , u τ and height h = 100 w h=100w h = 100 w , such that
P ⊆ Q τ ( P ) ⊆ q P + α ( P − q P ) (6) P\subseteq Q_\tau(P)\subseteq q_P+\alpha(P-q_P) \tag*{(6)} P ⊆ Q τ ( P ) ⊆ q P + α ( P − q P ) (6) for some universal constant α > 1 \alpha>1 α > 1 . Moreover,
q Q τ ( P ) = q P q_{Q_\tau(P)}=q_P q Q τ ( P ) = q P ;
R Q τ ( P ) R_{Q_\tau(P)} R Q τ ( P ) lies on the ray q P R P → \overrightarrow{q_PR_P} q P R P , L Q τ ( P ) L_{Q_\tau(P)} L Q τ ( P ) lies on the ray q P L P → \overrightarrow{q_PL_P} q P L P ;
In coordinates with axes { u ⃗ τ , d ⃗ τ } \{\vec{u}_\tau,\vec{d}_\tau\} { u τ , d τ } and origin q Q q_Q q Q , we have
R Q = ( h a Q , h ) , L Q = ( h b Q , h ) , 7 r w ≤ a Q ≤ 32 r w , − 4 r w ≤ b Q ≤ 3 r w . (7) R_Q=(ha_Q,h),\qquad L_Q=(hb_Q,h),\qquad\frac{7r}{w}\leq a_Q\leq\frac{32r}{w},\qquad-\frac{4r}{w}\leq b_Q\leq\frac{3r}{w}. \tag*{(7)} R Q = ( h a Q , h ) , L Q = ( h b Q , h ) , w 7 r ≤ a Q ≤ w 32 r , − w 4 r ≤ b Q ≤ w 3 r . (7)
Proof. Consider a star P P P of fine type τ \tau τ . Note that L P − q P = x e ⃗ P + w P v ⃗ P L_P-q_P=x\vec{e}_P+w_P\vec{v}_P L P − q P = x e P + w P v P for some ∣ x ∣ ≤ r |x|\leq r ∣ x ∣ ≤ r . By Equation (2) and β P ∈ [ δ , 2 δ ) \beta_P\in[\delta,2\delta) β P ∈ [ δ , 2 δ ) , w P ∈ ( w / 2 , w ] w_P\in(w/2,w] w P ∈ ( w /2 , w ] , we have
d ⃗ τ ⋅ ( R P − q P ) = r P sin β P ∈ ( 0.01 w , 0.13 w ) (8) \vec{d}_\tau\cdot(R_P-q_P)=r_P\sin\beta_P\in(0.01w,0.13w) \tag*{(8)} d τ ⋅ ( R P − q P ) = r P sin β P ∈ ( 0.01 w , 0.13 w ) (8)
and
d ⃗ τ ⋅ ( L P − q P ) = x sin β P + w P cos β P ∈ ( 0.49 w , 1.13 w ) . (9) \vec{d}_{\tau} \cdot(L_P-q_P)=x\sin\beta_P+w_P\cos\beta_P\in(0.49w,1.13w). \tag*{(9)} d τ ⋅ ( L P − q P ) = x sin β P + w P cos β P ∈ ( 0.49 w , 1.13 w ) . (9)
For every p ∈ P p\in P p ∈ P , write p − q P = s e ⃗ P + t v ⃗ P p-q_P=s\vec{e}_P+t\vec{v}_P p − q P = s e P + t v P , where ∣ s ∣ ≤ r |s|\le r ∣ s ∣ ≤ r and ∣ t ∣ ≤ w |t|\le w ∣ t ∣ ≤ w . Similarly, ∣ d ⃗ τ ⋅ ( p − q P ) ∣ ≤ 1.13 w |\vec{d}_{\tau}\cdot(p-q_P)|\le1.13w ∣ d τ ⋅ ( p − q P ) ∣ ≤ 1.13 w .
Let h = 100 w h=100w h = 100 w . We extend the rays q P R P q_PR_P q P R P and q P L P q_PL_P q P L P to points R Q R_Q R Q and L Q L_Q L Q such that
d ⃗ τ ⋅ ( R Q − q P ) = d ⃗ τ ⋅ ( L Q − q P ) = h , \vec{d}_{\tau}\cdot(R_Q-q_P)=\vec{d}_{\tau}\cdot(L_Q-q_P)=h, d τ ⋅ ( R Q − q P ) = d τ ⋅ ( L Q − q P ) = h ,
and let the bowl Q = Q τ ( P ) Q=Q_{\tau}(P) Q = Q τ ( P ) be P ∪ q R Q ∪ q L Q P\cup qR_Q\cup qL_Q P ∪ q R Q ∪ q L Q . See Figure 15 for an illustration. By Equations (8) and (9) , both extensions are bounded by a universal constant factor. It is straightforward to check that R Q R_Q R Q and L Q L_Q L Q match their definitions.
Figure 15. The star P P P and the bowl Q ( P ) Q(P) Q ( P ) .
In coordinates with axes { u ⃗ τ , d ⃗ τ } \{\vec{u}_{\tau},\vec{d}_{\tau}\} { u τ , d τ } , let R Q = ( h a Q , h ) R_Q=(ha_Q,h) R Q = ( h a Q , h ) and L Q = ( h b Q , h ) L_Q=(hb_Q,h) L Q = ( h b Q , h ) . Then we have
a Q = cot β P , b Q = x cos β P − w P sin β P x sin β P + w P cos β P . a_Q=\cot\beta_P,\qquad b_Q=\frac{x\cos\beta_P-w_P\sin\beta_P}{x\sin\beta_P+w_P\cos\beta_P}. a Q = cot β P , b Q = x sin β P + w P cos β P x cos β P − w P sin β P .
Equation (7) follows from Equation (2) and β P ∈ [ δ , 2 δ ) \beta_P\in[\delta,2\delta) β P ∈ [ δ , 2 δ ) , ∣ x ∣ ≤ r |x|\le r ∣ x ∣ ≤ r , w P ∈ ( w / 2 , w ] w_P\in(w/2,w] w P ∈ ( w /2 , w ] .
Equation (6) shows that replacing the stars with bowls will only increase the optimum by at most a constant factor α 2 \alpha^2 α 2 . To see this, we can take the optimal packing of α \alpha α -times-larger input stars, which has area α 2 OPT ( P ) \alpha^2\operatorname{OPT}(P) α 2 OPT ( P ) . Then a feasible packing of the bowls follows by matching the reference points with the corresponding scaled stars. Therefore, it suffices to compute a constant approximate packing for the bowls. Then, to obtain a packing of the original stars, we place each P i P_i P i at the location of Q ( P i ) Q(P_i) Q ( P i ) , sharing the same reference point.
Stacking bowls is (almost) optimal
We now show that the structural packing from Theorem 10 can be used to obtain a stack packing of bowls. Let α \alpha α be the constant from Equation (6) , and apply Theorem 10 to a packing of the scaled stars P ′ = α P P'=\alpha P P ′ = α P . For each part P j ′ P'_j P j ′ with bounding rectangle B j B_j B j , replace every scaled star α P ∈ P j ′ \alpha P\in P'_j α P ∈ P j ′ by its corresponding bowl Q ( P ) Q(P) Q ( P ) , keeping the reference point fixed. Since Q ( P ) ⊆ α P Q(P)\subseteq\alpha P Q ( P ) ⊆ α P , this gives a feasible packing of Q j = { Q ( P ) : α P ∈ P j ′ } Q_j=\{Q(P):\alpha P\in P'_j\} Q j = { Q ( P ) : α P ∈ P j ′ } inside B j B_j B j . See Figure 6 for an illustration.
It remains to show that the bowls in each rectangle B j B_j B j form a stack. Fix a part P j ′ P'_j P j ′ , and let τ \tau τ be its common fine type, with scales α r \alpha r α r and α w \alpha w α w . All bowls in Q j Q_j Q j therefore share the directions d ⃗ τ \vec{d}_{\tau} d τ and u ⃗ τ \vec{u}_{\tau} u τ . Moreover, Theorem 10 guarantees that their reference points are close together. We use this property in the next lemma to show that their separators are pairwise disjoint, and hence that the bowls form a stack.
Lemma 12. Let α \alpha α be the constant in Lemma 11 . Apply Theorem 10 to a packing of P ′ = α P \mathcal{P}' = \alpha P P ′ = α P in a convex container C C C . For every j j j , the bowls
Q j = { Q ( P ) : α P ∈ P j ′ } Q_j = \{Q(P) : \alpha P \in\mathcal{P}'_j\} Q j = { Q ( P ) : α P ∈ P j ′ } admit a stack packing in a rectangle B ^ j \widehat{B}_j B j of dimensions O ( r ) × O ( w ) O(r) \times O(w) O ( r ) × O ( w ) , with sides parallel to their common directions u ⃗ τ j , d ⃗ τ j \vec{u}_{\tau_j}, \vec{d}_{\tau_j} u τ j , d τ j , such that
∑ j ∣ B ^ j ∣ = O ( ∣ C ∣ ) . \sum_j |\widehat{B}_j| = O(|C|). j ∑ ∣ B j ∣ = O ( ∣ C ∣ ) .
Proof. Fix any j j j . Let P j ′ , B j \mathcal{P}'_j, B_j P j ′ , B j be defined in Theorem 10 . For each P ′ = α P ∈ P j ′ P' = \alpha P \in\mathcal{P}'_j P ′ = α P ∈ P j ′ , place the bowl Q ( P ) Q(P) Q ( P ) such that q Q ( P ) = q P ′ q_{Q(P)} = q_{P'} q Q ( P ) = q P ′ . By Equation (6) , we have Q ( P ) ⊆ P ′ Q(P) \subseteq P' Q ( P ) ⊆ P ′ , so the bowls are feasible and lie in B ^ j = B j \widehat{B}_j = B_j B j = B j . The area bound follows from Theorem 10 (ii). The only remaining thing is to show that the induced packing for Q j Q_j Q j forms a stack.
Now we use the coordinate system along u ⃗ τ j \vec{u}_{\tau_j} u τ j and d ⃗ τ j \vec{d}_{\tau_j} d τ j . For any point p p p , we use ( x ( p ) , y ( p ) ) (x(p), y(p)) ( x ( p ) , y ( p )) to denote its coordinates. Consider any pair of bowls Q 1 Q_1 Q 1 and Q 2 Q_2 Q 2 and translate q Q 1 q_{Q_1} q Q 1 to the origin. Write q Q 2 = ( X , Y ) q_{Q_2} = (X, Y) q Q 2 = ( X , Y ) where Y ≥ 0 Y \ge0 Y ≥ 0 without loss of generality. By Theorem 10 (i), ∣ X ∣ ≤ 10 ε r |X| \le10\varepsilon r ∣ X ∣ ≤ 10 ε r and Y ≤ 10 ε w Y \le10\varepsilon w Y ≤ 10 εw . Recall that y ( L Q 1 ) = y ( R Q 1 ) = h > 10 ε w y(L_{Q_1}) = y(R_{Q_1}) = h > 10\varepsilon w y ( L Q 1 ) = y ( R Q 1 ) = h > 10 εw by Lemma 11 , so q Q 2 q_{Q_2} q Q 2 is below the line L Q 1 R Q 1 ‾ \overline{L_{Q_1}R_{Q_1}} L Q 1 R Q 1 .
Claim 13. q Q 2 q_{Q_2} q Q 2 is in the triangle T Q 1 T_{Q_1} T Q 1 .
Proof. We will show that if q Q 2 q_{Q_2} q Q 2 is to the left of q Q 1 L Q 1 q_{Q_1}L_{Q_1} q Q 1 L Q 1 , then q Q 2 R Q 2 → \overrightarrow{q_{Q_2}R_{Q_2}} q Q 2 R Q 2 intersects with q Q 1 L Q 1 → \overrightarrow{q_{Q_1}L_{Q_1}} q Q 1 L Q 1 , and similarly, if q Q 2 q_{Q_2} q Q 2 is to the right of q Q 1 R Q 1 q_{Q_1}R_{Q_1} q Q 1 R Q 1 , then q Q 2 L Q 2 → \overrightarrow{q_{Q_2}L_{Q_2}} q Q 2 L Q 2 intersects with q Q 1 R Q 1 → \overrightarrow{q_{Q_1}R_{Q_1}} q Q 1 R Q 1 .
Recall that a Q 1 , b Q 1 , a Q 2 , b Q 2 a_{Q_1}, b_{Q_1}, a_{Q_2}, b_{Q_2} a Q 1 , b Q 1 , a Q 2 , b Q 2 are defined in Equation (7) . If q Q 2 q_{Q_2} q Q 2 is to the left of q Q 1 L Q 1 q_{Q_1}L_{Q_1} q Q 1 L Q 1 , then X < b Q 1 Y X < b_{Q_1}Y X < b Q 1 Y . The two rays q Q 2 R Q 2 → \overrightarrow{q_{Q_2}R_{Q_2}} q Q 2 R Q 2 and q Q 1 L Q 1 → \overrightarrow{q_{Q_1}L_{Q_1}} q Q 1 L Q 1 intersect at ( ⋅ , Y + t ) (\cdot, Y+t) ( ⋅ , Y + t ) where
t = b Q 1 Y − X a Q 2 − b Q 1 ≤ 30 ε r − ( − 10 ε r ) 7 r / w − 3 r / w = 10 ε w < h − Y , t = \frac{b_{Q_1}Y-X}{a_{Q_2}-b_{Q_1}} \le\frac{30\varepsilon r - (-10\varepsilon r)}{7r/w - 3r/w} = 10\varepsilon w < h-Y, t = a Q 2 − b Q 1 b Q 1 Y − X ≤ 7 r / w − 3 r / w 30 ε r − ( − 10 ε r ) = 10 εw < h − Y ,
so this is an intersection of the two segments.
If q Q 2 q_{Q_2} q Q 2 is to the right of q Q 1 R Q 1 q_{Q_1}R_{Q_1} q Q 1 R Q 1 , then X > a Q 1 Y X > a_{Q_1}Y X > a Q 1 Y . The two rays q Q 2 L Q 2 → \overrightarrow{q_{Q_2}L_{Q_2}} q Q 2 L Q 2 and q Q 1 R Q 1 → \overrightarrow{q_{Q_1}R_{Q_1}} q Q 1 R Q 1 intersect at ( ⋅ , Y + t ) (\cdot, Y+t) ( ⋅ , Y + t ) where
t = X − a Q 1 Y a Q 1 − b Q 2 ≤ 10 ε r − 7 ε r 7 r / w − 3 r / w = 3 ε w 4 < h − Y , t = \frac{X-a_{Q_1}Y}{a_{Q_1}-b_{Q_2}} \le\frac{10\varepsilon r - 7\varepsilon r}{7r/w - 3r/w} = \frac{3\varepsilon w}{4} < h-Y, t = a Q 1 − b Q 2 X − a Q 1 Y ≤ 7 r / w − 3 r / w 10 ε r − 7 ε r = 4 3 εw < h − Y ,
so this is an intersection of the two segments.
:::
By Claim 13 , if Y > 0 Y > 0 Y > 0 , then q Q 2 q_{Q_2} q Q 2 is above Separator ( Q 1 ) \operatorname{Separator}(Q_1) Separator ( Q 1 ) . Furthermore, the two arms of Q 2 Q_2 Q 2 can only leave the triangle through L Q 1 R Q 1 ‾ \overline{L_{Q_1}R_{Q_1}} L Q 1 R Q 1 to avoid intersections. So the two separators are disjoint. If Y = 0 Y = 0 Y = 0 , then q Q 1 = q Q 2 q_{Q_1} = q_{Q_2} q Q 1 = q Q 2 and y ( L Q 1 ) = y ( R Q 1 ) = y ( L Q 2 ) = y ( R Q 2 ) = h y(L_{Q_1}) = y(R_{Q_1}) = y(L_{Q_2}) = y(R_{Q_2}) = h y ( L Q 1 ) = y ( R Q 1 ) = y ( L Q 2 ) = y ( R Q 2 ) = h . By the feasibility, the two separators must also be (weakly) disjoint. Since any pair of separators are disjoint, the bowls form a stack.
In summary, we show that there exists a packing of the bowls as stacks into small rectangles with a total area comparable to the optimal packing of the original stars into multiple convex containers.
Corollary 14. Let P \mathcal{P} P be a set of stars in the same size group and let Q = { Q ( P ) : P ∈ P } \mathcal{Q} = \{Q(P) : P \in\mathcal{P}\} Q = { Q ( P ) : P ∈ P } . Then there exists a packing of Q \mathcal{Q} Q into rectangles of total area O ( OPT ′ ( P ) ) O(\operatorname{OPT}'(\mathcal{P})) O ( OPT ′ ( P )) , each containing a stack of bowls and having dimensions O ( r ) × O ( w ) O(r) \times O(w) O ( r ) × O ( w ) with sides parallel to u ⃗ τ , d ⃗ τ \vec{u}_\tau, \vec{d}_\tau u τ , d τ , where τ \tau τ is the common fine type of the stars in it.
Proof. Consider the optimal packing of the original stars into multiple convex containers. For each container C C C , we apply Theorem 10 and Lemma 12 to C C C and the stars in it.
Let OPT s t a c k ( Q τ ) \operatorname{OPT}_{\mathrm{stack}}(Q_\tau) OPT stack ( Q τ ) denote the infimum area of packing all bowls of type τ \tau τ into a convex container, under the constraint that they must form a stack. We have the following lemma.
Lemma 15. For a set of stars P P P in the same size group,
∑ τ OPT s t a c k ( Q τ ) = O ( OPT ′ ( P ) ) . \sum_{\tau}\operatorname{OPT}_{\mathrm{stack}}(Q_\tau)=O(\operatorname{OPT}'(P)). τ ∑ OPT stack ( Q τ ) = O ( OPT ′ ( P )) .
Proof. Consider the packing of Q Q Q in Corollary 14 . For each fine type τ \tau τ , all the rectangles that contain bowls of this type have dimensions O ( r ) × O ( w ) O(r) \times O(w) O ( r ) × O ( w ) along the same directions u ⃗ τ \vec{u}_\tau u τ , d ⃗ τ \vec{d}_\tau d τ . We put them one above another along d ⃗ τ \vec{d}_\tau d τ . If there are t τ t_\tau t τ rectangles, then they fit in an O ( r ) × O ( t τ w ) O(r) \times O(t_\tau w) O ( r ) × O ( t τ w ) large rectangle. It is straightforward to see that the bowls in this large rectangle still form a stack, and the area of it is at most a constant times the total area of the initial rectangles. Summing over the types, the total area is still O ( OPT ′ ( P ) ) O(\operatorname{OPT}'(P)) O ( OPT ′ ( P )) .
Computing approximately optimal stacks
In this subsection, we consider bowls from one fine type τ \tau τ . Note that the separators of the bowls in a stack are disjoint, so they have a natural order along d ⃗ τ \vec{d}_\tau d τ . Therefore, to pack a set of bowls into a stack, the key part is to compute the order. We model this as an asymmetric TSP problem.
Recall that the bowls have the same heights h = 100 w h=100w h = 100 w . Without loss of generality, we assume d ⃗ τ \vec{d}_\tau d τ is upward. We start with a simple lower bound of the area of a stack.
Lemma 16. If a stack has vertical span H H H , then its minimum convex container C C C has area Ω ( r H ) \Omega(rH) Ω ( r H ) .
Proof. Let P P P be a star in the stack. The span of P P P along e ⃗ P \vec{e}_P e P is at least r / 2 r/2 r /2 , and the angle between e ⃗ P \vec{e}_P e P and u ⃗ τ \vec{u}_\tau u τ is at most 2 δ ≤ π / 25 2\delta\le\pi/25 2 δ ≤ π /25 by Equation (2) . So the horizontal span of the stack is Ω ( r ) \Omega(r) Ω ( r ) .
The next lemma shows that a tall stack can be split into short strict stacks with bounded total area.
Lemma 17. In polynomial time, a stack of vertical span H H H can be partitioned into O ( H / h ) O(H/h) O ( H / h ) strict stacks, each fitting in an O ( r ) × O ( h ) O(r) \times O(h) O ( r ) × O ( h ) rectangle with sides parallel to u ⃗ τ \vec{u}_\tau u τ and d ⃗ τ \vec{d}_\tau d τ .
Proof. Partition the reference points into O ( H / h ) O(H/h) O ( H / h ) horizontal strips of height h / 2 h/2 h /2 . For each strip, consider the bowls whose reference points are in this strip. The vertical span of them is O ( h ) O(h) O ( h ) . Since they form a stack, their separators are disjoint. Then these reference points must all be in the triangle T Q T_Q T Q where Q Q Q is the lowest bowl, which means the horizontal span of these bowls is O ( r ) O(r) O ( r ) . So they fit in an O ( r ) × O ( h ) O(r) \times O(h) O ( r ) × O ( h ) rectangle.
Now we prove they form a strict stack. Let Q 1 Q_1 Q 1 and Q 2 Q_2 Q 2 be two bowls in the same strip such that Separator ( Q 1 ) \operatorname{Separator}(Q_1) Separator ( Q 1 ) is (weakly) below Separator ( Q 2 ) \operatorname{Separator}(Q_2) Separator ( Q 2 ) . Clearly, Q 1 Q_1 Q 1 cannot intersect with Separator ( Q 2 ) \operatorname{Separator}(Q_2) Separator ( Q 2 ) since the bowls have the same heights. On the other hand, q Q 2 q_{Q_2} q Q 2 is in the triangle T Q 1 T_{Q_1} T Q 1 . Since q Q 2 q_{Q_2} q Q 2 is the reference point of Q 2 Q_2 Q 2 , for any point p ∈ Q 2 p \in Q_2 p ∈ Q 2 , p q Q 2 pq_{Q_2} p q Q 2 cannot intersect with both q Q 1 L Q 1 q_{Q_1}L_{Q_1} q Q 1 L Q 1 and q Q 1 R Q 1 q_{Q_1}R_{Q_1} q Q 1 R Q 1 . So Q 2 Q_2 Q 2 does not intersect with Separator ( Q 1 ) \operatorname{Separator}(Q_1) Separator ( Q 1 ) .
We remark that the total area of the rectangles in Lemma 17 is O ( r H ) O(rH) O ( r H ) , although the area of the convex hull of the original stack may be much larger. This will be important for our algorithm. By Lemmas 16 and 17 , when considering stack packing, we only need to care about the height of the stack.
The next corollary shows that we can restrict our attention to strict stacks at only a constant-factor increase in height.
Corollary 18. If some bowls admit a stack of vertical span H H H , then they admit a strict stack of vertical span O ( H ) O(H) O ( H ) .
Proof. We simply put the rectangles in Lemma 17 one above another along d ⃗ τ \vec{d}_{\tau} d τ .
For two bowls Q i , Q j Q_i,Q_j Q i , Q j , we write Q i ≺ Q j Q_i \prec Q_j Q i ≺ Q j if we place them in a strict stack with Q i Q_i Q i below Q j Q_j Q j . Note that if Q i ≺ Q j ≺ Q k Q_i \prec Q_j \prec Q_k Q i ≺ Q j ≺ Q k , then the Separator(Q j Q_j Q j ) separates Q i Q_i Q i from Q k Q_k Q k . So, when we construct a strict stack, we only need to make sure that each adjacent pair of bowls do not intersect.
Lemma 19. In polynomial time, a bowl class Q τ Q_{\tau} Q τ can be packed into O ( r ) × O ( h ) O(r) \times O(h) O ( r ) × O ( h ) rectangles with sides parallel to u ⃗ τ \vec{u}_{\tau} u τ and d ⃗ τ \vec{d}_{\tau} d τ and total area O ( O P T s t a c k ( Q τ ) ) O(\mathrm{OPT}_{\mathrm{stack}}(Q_{\tau})) O ( OPT stack ( Q τ )) .
Proof. Suppose the optimal stack packing of Q τ Q_{\tau} Q τ has vertical span H H H . By Corollary 18 , Q τ Q_{\tau} Q τ also admits a strict stack of vertical span H ′ = O ( H ) H'=O(H) H ′ = O ( H ) . We only need to approximate the minimum height of the strict stack.
Let Q τ = { Q 1 , Q 2 , … , Q m } Q_{\tau}=\{Q_1,Q_2,\ldots,Q_m\} Q τ = { Q 1 , Q 2 , … , Q m } . For i , j ∈ [ 1 , m ] i,j\in[1,m] i , j ∈ [ 1 , m ] , let c ( i , j ) ≤ 2 h c(i,j)\le2h c ( i , j ) ≤ 2 h be the minimum increase of the height (i.e. the minimum value of ( q Q 2 − q Q 1 ) ⋅ d ⃗ τ (q_{Q_2}-q_{Q_1})\cdot\vec{d}_{\tau} ( q Q 2 − q Q 1 ) ⋅ d τ ) when placing Q i ≺ Q j Q_i\prec Q_j Q i ≺ Q j . In particular, let c ( i , i ) = 0 c(i,i)=0 c ( i , i ) = 0 . Notice that for any strict stack of three bowls Q i ≺ Q j ≺ Q k Q_i\prec Q_j\prec Q_k Q i ≺ Q j ≺ Q k , removing Q j Q_j Q j gives us a strict stack of the other two bowls Q i ≺ Q k Q_i\prec Q_k Q i ≺ Q k . So c ( i , k ) ≤ c ( i , j ) + c ( j , k ) c(i,k)\le c(i,j)+c(j,k) c ( i , k ) ≤ c ( i , j ) + c ( j , k ) . In other words, c c c is a directed metric.
Since the bowls admit a strict stack of vertical span H ′ H' H ′ , by the definition of c c c , they admit a Hamiltonian path of length at most H ′ H' H ′ . So they admit a Hamiltonian cycle of length at most H ′ + 2 h = O ( H ) H'+2h=O(H) H ′ + 2 h = O ( H ) . We apply the constant-factor approximation for metric asymmetric TSP in [36 ] , then delete the most expensive edge. This gives us a Hamiltonian path of length O ( H ) O(H) O ( H ) in polynomial time.
From the Hamiltonian path, it is straightforward to get a strict stack of Q τ Q_{\tau} Q τ of vertical span O ( H ) O(H) O ( H ) . Then we partition them into O ( r ) × O ( h ) O(r)\times O(h) O ( r ) × O ( h ) rectangles by Lemma 17 . The total area of the rectangles is O ( r H ) O(rH) O ( r H ) . On the other hand, O P T s t a c k ( Q τ ) = Ω ( r H ) \mathrm{OPT}_{\mathrm{stack}}(Q_{\tau})=\Omega(rH) OPT stack ( Q τ ) = Ω ( r H ) by Lemma 16 .
We summarize our conclusion for packing one size group in the following lemma.
Lemma 20. For a set of stars P \mathcal{P} P in the same size group, one can compute in polynomial time a packing into rectangular mini-containers of total area O ( O P T ′ ( P ) ) O(\mathrm{OPT}'(\mathcal{P})) O ( OPT ′ ( P )) . Each mini-container has dimensions O ( r ) × O ( w ) O(r)\times O(w) O ( r ) × O ( w ) with sides parallel to u ⃗ τ , d ⃗ τ \vec{u}_{\tau},\vec{d}_{\tau} u τ , d τ , where τ \tau τ is the common fine type of all stars in this mini-container.
Proof. We first partition the stars into fine types and compute the corresponding bowls by Lemma 11 . Then we compute the mini-containers for each bowl class separately by Lemma 19 . The total area of the mini-containers is O ( O P T ′ ( P ) ) O(\mathrm{OPT}'(\mathcal{P})) O ( OPT ′ ( P )) by Lemma 15 . Finally, we replace each bowl with the original star at the same reference point.
For a direction z z z , let span z ( S ) \operatorname{span}_z(S) span z ( S ) denote the span of S S S in that direction. The following corollary shows that the span of a mini-container in any direction is comparable to any star in it.
Corollary 21. Every mini-container B B B in Lemma 20 satisfies
span z ( B ) = O ( span z ( P ) ) \operatorname{span}_z(B)=O(\operatorname{span}_z(P)) span z ( B ) = O ( span z ( P )) for every direction z z z and every star P P P in B B B .
Proof. The mini-container has dimensions O ( r ) × O ( w ) O(r)\times O(w) O ( r ) × O ( w ) along u ⃗ τ , d ⃗ τ \vec{u}_{\tau},\vec{d}_{\tau} u τ , d τ . The star has dimensions Ω ( r ) × Ω ( w ) \Omega(r)\times\Omega(w) Ω ( r ) × Ω ( w ) along e ⃗ P , v ⃗ P \vec{e}_P,\vec{v}_P e P , v P . The angle between u ⃗ τ \vec{u}_{\tau} u τ and e ⃗ P \vec{e}_P e P (d ⃗ τ \vec{d}_{\tau} d τ and v ⃗ P \vec{v}_P v P ) is less than 2 δ = O ( w / r ) 2\delta=O(w/r) 2 δ = O ( w / r ) .
Shaving a log-factor
Recall that there are O ( log 2 n ) O(\log^{2} n) O ( log 2 n ) size groups, and we pack the stars of each size group separately. This would naturally introduce an approximation ratio of O ( log 2 n ) O(\log^{2} n) O ( log 2 n ) .
In this subsection, we show that packing the size groups separately increases the total area by only an O ( log n ) O(\log n) O ( log n ) factor. The key observation concerns stars with much larger radii but much smaller widths than others. We associate a triangular core with each star and show that the cores of such stars must be disjoint in any feasible packing. These disjoint cores give an area lower bound that allows us to divide the size groups into O ( log n ) O(\log n) O ( log n ) classes. This improves the final approximation ratio to O ( log n ) O(\log n) O ( log n ) .
Cores. Let q P ′ = ( q P + R P ) / 2 + w P v ⃗ P / 10 q'_P=(q_P+R_P)/2+w_P\vec{v}_P/10 q P ′ = ( q P + R P ) /2 + w P v P /10 , R P ′ = q P ′ + ( R P − q P ) / 10 R'_P=q'_P+(R_P-q_P)/10 R P ′ = q P ′ + ( R P − q P ) /10 and L P ′ = q P ′ + ( L P − q P ) / 10 L'_P=q'_P+(L_P-q_P)/10 L P ′ = q P ′ + ( L P − q P ) /10 . We define the core of P P P , denoted by K P K_P K P , as the triangle △ q P ′ R P ′ L P ′ \triangle q'_P R'_P L'_P △ q P ′ R P ′ L P ′ . In other words, it is a 0.1-scale copy of T P T_P T P located “above” the middle point of the radius. See Figure 16 for an illustration.
Figure 16. The core of a star P P P is the gray triangle K P K_P K P .
By definition, we have
K P ⊆ T P K_P \subseteq T_P K P ⊆ T P
and
∣ K P ∣ = Θ ( r P w P ) . (10) |K_P|=\Theta(r_Pw_P). \tag*{(10)} ∣ K P ∣ = Θ ( r P w P ) . (10)
It is straightforward to check that, for any point p ∈ K P p\in K_P p ∈ K P ,
dist ( p , q P R P ) , dist ( p , q P L P ) , dist ( p , L P R P ) ≥ w P / 20. (11) \operatorname{dist}(p,q_PR_P),\operatorname{dist}(p,q_PL_P),\operatorname{dist}(p,L_PR_P)\ge w_P/20. \tag*{(11)} dist ( p , q P R P ) , dist ( p , q P L P ) , dist ( p , L P R P ) ≥ w P /20. (11)
Consider the coordinates along e ⃗ P \vec{e}_P e P and v ⃗ P \vec{v}_P v P centered at q P q_P q P . We further have
K P ⊆ [ 0.4 r P , 0.6 r P ] × [ 0.1 w P , 0.2 w P ] . (12) K_P\subseteq[0.4r_P,0.6r_P]\times[0.1w_P,0.2w_P]. \tag*{(12)} K P ⊆ [ 0.4 r P , 0.6 r P ] × [ 0.1 w P , 0.2 w P ] . (12)
The next lemma shows that the cores of stars with very different shapes must be disjoint.
Lemma 22. Let P 1 , P 2 P_1,P_2 P 1 , P 2 be two stars such that r P 1 > 10 r P 2 r_{P_1}>10r_{P_2} r P 1 > 10 r P 2 and w P 2 > 10 w P 1 w_{P_2}>10w_{P_1} w P 2 > 10 w P 1 . In any packing, K P 1 ∩ K P 2 = ∅ K_{P_1}\cap K_{P_2}=\varnothing K P 1 ∩ K P 2 = ∅ .
Proof. Suppose for contradiction that K P 1 ∩ K P 2 ≠ ∅ K_{P_1}\cap K_{P_2}\ne\varnothing K P 1 ∩ K P 2 = ∅ . Consider the coordinates along e ⃗ P 1 \vec{e}_{P_1} e P 1 and v ⃗ P 1 \vec{v}_{P_1} v P 1 centered at q P 1 q_{P_1} q P 1 . Let p = ( x p , y p ) p=(x_p,y_p) p = ( x p , y p ) be an arbitrary point in K P 1 ∩ K P 2 K_{P_1}\cap K_{P_2} K P 1 ∩ K P 2 . By Equation (12) , x p ∈ [ 0.4 r P 1 , 0.6 r P 1 ] x_p\in[0.4r_{P_1},0.6r_{P_1}] x p ∈ [ 0.4 r P 1 , 0.6 r P 1 ] and y p ∈ [ 0.1 w P 1 , 0.2 w P 1 ] y_p\in[0.1w_{P_1},0.2w_{P_1}] y p ∈ [ 0.1 w P 1 , 0.2 w P 1 ] . Since p ∈ K P 2 ⊆ T P 2 p\in K_{P_2}\subseteq T_{P_2} p ∈ K P 2 ⊆ T P 2 , any point in T P 2 T_{P_2} T P 2 is at a distance at most 2 r P 2 < 0.2 r P 1 2r_{P_2}<0.2r_{P_1} 2 r P 2 < 0.2 r P 1 from p p p . So, T P 2 T_{P_2} T P 2 is in the strip 0.2 r P 1 < x < 0.8 r P 1 0.2r_{P_1}<x<0.8r_{P_1} 0.2 r P 1 < x < 0.8 r P 1 . Since q P 1 R P 1 q_{P_1}R_{P_1} q P 1 R P 1 cut this strip at y = 0 y=0 y = 0 and y p > 0 y_p>0 y p > 0 , T P 2 T_{P_2} T P 2 lies in y ≥ 0 y\ge0 y ≥ 0 due to connectivity of P 2 P_2 P 2 .
On the other hand, consider the disk D D D centered at p p p with radius w P 2 / 20 > 0.5 w P 1 w_{P_2}/20>0.5w_{P_1} w P 2 /20 > 0.5 w P 1 . Since y p ≤ 0.2 w P 1 y_p\le0.2w_{P_1} y p ≤ 0.2 w P 1 , D D D intersects y < 0 y<0 y < 0 . By Equation (11) , D ⊆ T P 2 D\subseteq T_{P_2} D ⊆ T P 2 . So T P 2 T_{P_2} T P 2 intersects y < 0 y<0 y < 0 , which is a contradiction.
The next lemma proves an upper bound of packing stars in the same size group with intersecting cores. Note that the lower bound of packing each single core is Ω ( r ) × Ω ( w ) \Omega(r) \times\Omega(w) Ω ( r ) × Ω ( w ) .
Lemma 23. Let P P P be a star in the size group with scales r r r and w w w . There is an O ( r ) × O ( w ) O(r) \times O(w) O ( r ) × O ( w ) rectangle that contains all stars P ′ P' P ′ in the same group such that K P ′ ∩ K P ≠ ∅ K_{P'} \cap K_P \ne\emptyset K P ′ ∩ K P = ∅ .
Proof. Consider the coordinates along e ⃗ P \vec{e}_P e P and v ⃗ P \vec{v}_P v P centered at q P q_P q P . Consider one such P ′ P' P ′ . Let p = ( x p , y p ) p=(x_p,y_p) p = ( x p , y p ) be an arbitrary point in K P ′ ∩ K P K_{P'} \cap K_P K P ′ ∩ K P . Let θ \theta θ be the angle between the two radius lines q P R P q_PR_P q P R P and q P ′ R P ′ q_{P'}R_{P'} q P ′ R P ′ . For each radius line, by Equation (12) , the distance from p p p is at most 0.2 w 0.2w 0.2 w , and the perpendicular projection of p p p lies at distance at least 0.2 r 0.2r 0.2 r from both q P q_P q P (q P ′ q_{P'} q P ′ ) and R P R_P R P (R P ′ R_{P'} R P ′ ). See Figure 17 .
Figure 17. The point p p p and the two radius lines.
The two radii q P R P q_PR_P q P R P and q P ′ R P ′ q_{P'}R_{P'} q P ′ R P ′ are part of the stars, so they cannot intersect. Therefore, we have 0.4 w / sin θ ≥ 0.2 r 0.4w/\sin\theta\ge0.2r 0.4 w / sin θ ≥ 0.2 r , so sin θ ≤ 2 w / r \sin\theta\le2w/r sin θ ≤ 2 w / r . Consider any point z = ( x z , y z ) ∈ P ′ z=(x_z,y_z) \in P' z = ( x z , y z ) ∈ P ′ . Since p ∈ T P ′ p \in T_{P'} p ∈ T P ′ , ∣ x z − x p ∣ ≤ 2 r cos θ + 2 w sin θ = O ( r ) |x_z-x_p| \le2r\cos\theta+2w\sin\theta=O(r) ∣ x z − x p ∣ ≤ 2 r cos θ + 2 w sin θ = O ( r ) and ∣ y z − y p ∣ ≤ 2 r sin θ + 2 w cos θ = O ( w ) |y_z-y_p| \le2r\sin\theta+2w\cos\theta=O(w) ∣ y z − y p ∣ ≤ 2 r sin θ + 2 w cos θ = O ( w ) . Combining these with p ∈ K P p \in K_P p ∈ K P and Equation (12) proves the lemma.
Combining the above lemmas, we can prove that, for all the stars with similar sizes, packing each group separately will only increase the cost by a constant factor.
Lemma 24. Let P \mathcal{P} P be a set of stars such that the sizes r P ⋅ w P r_P \cdot w_P r P ⋅ w P for all P ∈ P P \in\mathcal{P} P ∈ P differ by at most a constant factor. Then,
∑ G : size group OPT ′ ( G ) = O ( OPT ′ ( P ) ) . \sum_{G:\ \text{size group}} \operatorname{OPT}'(G)=O(\operatorname{OPT}'(\mathcal{P})). G : size group ∑ OPT ′ ( G ) = O ( OPT ′ ( P )) . Proof. Recall that each size group G a , b \mathcal{G}_{a,b} G a , b has r = r max / 2 a r=r_{\max}/2^a r = r m a x / 2 a and w = w max / 2 b w=w_{\max}/2^b w = w m a x / 2 b . We divide all size groups into O ( log n ) O(\log n) O ( log n ) classes, such that each class C i , j \mathcal{C}_{i,j} C i , j (i ∈ [ 0 , O ( log n ) ] i \in[0,O(\log n)] i ∈ [ 0 , O ( log n )] , j ∈ [ 0 , 4 ] j \in[0,4] j ∈ [ 0 , 4 ] ) consists of the groups G a , b \mathcal{G}_{a,b} G a , b where a + b = i a+b=i a + b = i and a m o d 5 = j a\bmod5=j a mod 5 = j . Since all stars have similar sizes r P ⋅ w P r_P \cdot w_P r P ⋅ w P , there are only a constant number of classes that have non-empty size groups. So it suffices to look at one such class C i , j \mathcal{C}_{i,j} C i , j .
Consider the optimal packing of C i , j \mathcal{C}_{i,j} C i , j . Let I ( P ′ ) I(P') I ( P ′ ) denote the size of the maximum independent set of the cores of P ′ P' P ′ (that is, the maximum number of cores that are disjoint). For each class C i , j \mathcal{C}_{i,j} C i , j , by Lemma 22 , the cores of stars from different size groups are disjoint. So
∑ G ∈ C i , j I ( G ) = I ( C i , j ) . (13) \sum_{G\in\mathcal{C}_{i,j}} I(G)=I(\mathcal{C}_{i,j}). \tag*{(13)} G ∈ C i , j ∑ I ( G ) = I ( C i , j ) . (13) Since each core has an area of Ω ( r max w max / 2 i ) \Omega(r_{\max}w_{\max}/2^i) Ω ( r m a x w m a x / 2 i ) by Equation (10) and lies in the convex hull of the star, we have
OPT ( C i , j ) = Ω ( I ( C i , j ) r max w max / 2 i ) . (14) \operatorname{OPT}(\mathcal{C}_{i,j})=\Omega(I(\mathcal{C}_{i,j})r_{\max}w_{\max}/2^i). \tag*{(14)} OPT ( C i , j ) = Ω ( I ( C i , j ) r m a x w m a x / 2 i ) . (14) On the other hand, by Lemma 23 , we have
OPT ( G ) = O ( I ( G ) r max w max / 2 i ) . (15) \operatorname{OPT}(G)=O(I(G)r_{\max}w_{\max}/2^i). \tag*{(15)} OPT ( G ) = O ( I ( G ) r m a x w m a x / 2 i ) . (15) Combining Equations (13) to (15) proves the lemma.
We conclude this subsection with the following corollary.
Corollary 25. For a set of stars P \mathcal{P} P ,
∑ G : size group OPT ′ ( G ) = O ( log n ) ⋅ OPT ( P ) . \sum_{\mathcal{G}:\ \text{size group}} \operatorname{OPT}^{\prime}(\mathcal{G}) = O(\log n)\cdot\operatorname{OPT}(\mathcal{P}). G : size group ∑ OPT ′ ( G ) = O ( log n ) ⋅ OPT ( P ) . Proof. Recall that stars with sizes smaller than r max w max / n r_{\max}w_{\max}/n r m a x w m a x / n can be packed individually at a cost of OPT ( P ) \operatorname{OPT}(\mathcal{P}) OPT ( P ) . Then it simply follows from Lemma 24 .
The complete translational algorithm
Finally, we put everything together to get an O ( log n ) O(\log n) O ( log n ) -approximate algorithm. We first give a lemma that follows easily from our previous results.
Lemma 26. For a set of stars P \mathcal{P} P , in polynomial time, we can compute a packing of P \mathcal{P} P into a set of convex mini-containers of total area O ( log n ) ⋅ OPT ( P ) O(\log n)\cdot\operatorname{OPT}(\mathcal{P}) O ( log n ) ⋅ OPT ( P ) . Every mini-container B B B satisfies
span z ( B ) = O ( span z ( P ) ) (16) \operatorname{span}_{z}(B) = O(\operatorname{span}_{z}(\mathcal{P})) \tag*{(16)} span z ( B ) = O ( span z ( P )) (16) for every direction z z z and every star P P P that B B B contains.
Proof. We pack all stars with r P < r max / n r_{P}<r_{\max}/n r P < r m a x / n or w P < w max / n w_{P}<w_{\max}/n w P < w m a x / n individually into its convex hull. The total area of them is O ( r max w max ) = O ( OPT ( P ) ) O(r_{\max}w_{\max})=O(\operatorname{OPT}(\mathcal{P})) O ( r m a x w m a x ) = O ( OPT ( P )) by Lemma 8 . For these mini-containers, Equation (16) trivially holds.
The remaining stars are partitioned into O ( log 2 n ) O(\log^{2}n) O ( log 2 n ) size groups. We pack each size group separately by Lemma 20 . The total area is
∑ G : size group O ( OPT ′ ( G ) ) . \sum_{\mathcal{G}:\ \text{size group}} O(\operatorname{OPT}^{\prime}(\mathcal{G})). G : size group ∑ O ( OPT ′ ( G )) . By Corollary 25, this equals O ( log n ) ⋅ OPT ( P ) O(\log n)\cdot\operatorname{OPT}(\mathcal{P}) O ( log n ) ⋅ OPT ( P ) . For these mini-containers, Equation (16) follows from Corollary 21 .
We can now bound the approximation factor of our algorithm.
Theorem 27. For a set of stars P \mathcal{P} P , in polynomial time, we can compute a packing of P \mathcal{P} P into a rectangle of area O ( log n ) ⋅ OPT ( P ) O(\log n)\cdot\operatorname{OPT}(\mathcal{P}) O ( log n ) ⋅ OPT ( P ) .
Proof. We use the packing of Lemma 26 into convex mini-containers of total area O ( log n ) ⋅ OPT ( P ) O(\log n)\cdot\operatorname{OPT}(\mathcal{P}) O ( log n ) ⋅ OPT ( P ) . Then we apply Theorem 5 to these mini-containers in the coordinate system where the longest radius (whose length is r max r_{\max} r m a x ) is horizontal.
Let ℓ max \ell_{\max} ℓ m a x and h max h_{\max} h m a x be the maximum horizontal and vertical spans of these mini-containers respectively. It only remains to show that OPT ( P ) = Ω ( ℓ max h max ) \operatorname{OPT}(\mathcal{P})=\Omega(\ell_{\max}h_{\max}) OPT ( P ) = Ω ( ℓ m a x h m a x ) . By Equation (16) , r max = Ω ( ℓ max ) r_{\max}=\Omega(\ell_{\max}) r m a x = Ω ( ℓ m a x ) and there exists a star P P P whose vertical span is h P = Ω ( h max ) h_{P}=\Omega(h_{\max}) h P = Ω ( h m a x ) . Since the minimum convex container of P P P must contain the longest radius, which is a horizontal segment of length r max r_{\max} r m a x , and the star P P P , we have OPT ( P ) = Ω ( r max h P ) = Ω ( ℓ max h max ) \operatorname{OPT}(\mathcal{P})=\Omega(r_{\max}h_{P})=\Omega(\ell_{\max}h_{\max}) OPT ( P ) = Ω ( r m a x h P ) = Ω ( ℓ m a x h m a x ) .
Algorithm for rotational packing
The preceding section gives an algorithm for packing stars by translations: it replaces stars by bowls, arranges bowls in stacks, and packs the resulting rectangular mini-containers. Let us now consider the setting, in which we are also allowed both translations and rotations in order to pack stars. We will show that, within each size group, requiring all radius vectors to point in the same direction increases the minimum container area by only a constant factor. We can then rotate the input stars to this direction and apply the translational algorithm of § 3 , including the stack-packing procedure of Lemma 19 .
Fix a size group G = G a , b \mathcal{G} = \mathcal{G}_{a,b} G = G a , b from the preceding section. As before, r max r_{\max} r m a x and w max w_{\max} w m a x denote the maximum input radius and width. The scales of the group are r = r max / 2 a r = r_{\max}/2^a r = r m a x / 2 a and w = w max / 2 b w = w_{\max}/2^b w = w m a x / 2 b . The normalized bowls have height h = 100 w h = 100w h = 100 w . For a star P i P_i P i , let q i q_i q i denote its reference point and R ( P i ) R(P_i) R ( P i ) its distinguished radius endpoint, as in the preceding section. Its directed radius vector is R ( P i ) − q i R(P_i)-q_i R ( P i ) − q i . We choose these reference points and endpoints once and carry them along under all transformations. Constants below are independent of the number of pieces and the ratio r / h r/h r / h .
We first apply the previous construction to a packing whose chosen rotations are held fixed. It gives small rectangles containing stacks whose radius directions are already close. The remaining task is to make these directions equal. After a preliminary division into locally separated blocks, we take every third bowl and enclose it between its two neighboring separators. We process the resulting enclosures from bottom to top, rotating all remaining enclosures about the current reference point at each step. The sum of the successive angle changes bounds the total upward translation, and hence the increase in the rectangle’s height.
Lemma 28. Fix a constant ε \varepsilon ε with 0 < ε ≤ 10 − 6 0 < \varepsilon\le10^{-6} 0 < ε ≤ 1 0 − 6 . Given a rotational packing of one size group into a convex container C C C , the stars can be replaced by containing bowls and packed, using translations of their fixed orientations, into rectangular mini-containers of dimensions O ( r ) × O ( h ) O(r) \times O(h) O ( r ) × O ( h ) and total area O ( ∣ C ∣ ) O(|C|) O ( ∣ C ∣ ) . Within each mini-container, let d d d denote the common bowl-alignment direction and let u u u denote the perpendicular direction pointing towards the distinguished radius. The mini-container may be replaced by a rectangle whose sides are parallel to u u u and d d d , with respective lengths O ( r ) O(r) O ( r ) and O ( h ) O(h) O ( h ) . These rectangles can all be enlarged to common dimensions κ r × κ h \kappa r \times\kappa h κ r × κh , for a fixed constant κ \kappa κ , while retaining the total-area bound. We have:
the bowls have common height h h h , alignment direction d d d , and pairwise disjoint separators;
their radii are Θ ( r ) \Theta(r) Θ ( r ) and their widths are Θ ( h ) \Theta(h) Θ ( h ) ;
their directed radius angles lie in an interval of length at most ε h / r \varepsilon h/r ε h / r ;
each bowl contains its corresponding star, with the same reference point and distinguished radius ray.
Moreover, no point of one bowl lies in the interior of another bowl in the same mini-container. This includes the two added radial arms, which may have zero width. All hidden constants are universal after fixing ε \varepsilon ε .
Proof. Fix the orientations of the stars in the given packing and regard it as a translational instance, keeping the chosen reference points and radius witnesses; fine types are computed from these orientations. Apply Corollary 14 . It returns the bowls Q i = Q ( P i ) Q_i = Q(P_i) Q i = Q ( P i ) of Lemma 11 , packed into rectangles of dimensions O ( r ) × O ( w ) = O ( r ) × O ( h ) O(r) \times O(w) = O(r) \times O(h) O ( r ) × O ( w ) = O ( r ) × O ( h ) , each with sides parallel to the directions u , d u,d u , d of the common fine type of its bowls, and of total area O ( ∣ C ∣ ) O(|C|) O ( ∣ C ∣ ) . Each rectangle holds a stack of bowls of one fine type; the stack property gives height h h h and pairwise disjoint separators. Each Q i Q_i Q i contains P i P_i P i together with its reference point and distinguished radius ray, and has radius Θ ( r ) \Theta(r) Θ ( r ) and width Θ ( h ) \Theta(h) Θ ( h ) , by Lemma 11 . This gives items 1, 2 and 4, but with the angular span of item 3 replaced by that of a fine type, which we now reduce.
By Equation (2) , the directed radius angles of the stars of one fine type lie in an interval of length δ = 2 π / N ≤ 2 π w / ( 100 r ) = ( 2 π / 10 4 ) h / r \delta= 2\pi/N \le2\pi w/(100r) = (2\pi/10^4)h/r δ = 2 π / N ≤ 2 π w / ( 100 r ) = ( 2 π /1 0 4 ) h / r . Split this interval into m = ⌈ 2 π / ( 10 4 ε ) ⌉ m = \lceil2\pi/(10^4\varepsilon)\rceil m = ⌈ 2 π / ( 1 0 4 ε )⌉ consecutive subintervals of length at most ε h / r \varepsilon h/r ε h / r , and split each stack into the at most m m m subsequences of bowls whose angles fall into the same subinterval, each in its inherited order. A subsequence of a stack is again a stack: its separators are among the original ones and hence remain pairwise disjoint, its bowls still have height h h h and alignment direction d d d , and it lies in the rectangle of the original stack. We place each subsequence, by a translation, in its own copy of that rectangle and call the result a mini-container. This multiplies the number of rectangles, and hence their total area, by at most m = O ( 1 / ε ) m = O(1/\varepsilon) m = O ( 1/ ε ) , so the total area is still O ( ∣ C ∣ ) O(|\mathcal{C}|) O ( ∣ C ∣ ) . Within each mini-container the directed radius angles now lie in an interval of length at most ε h / r \varepsilon h/r ε h / r , which is item 3.
In the proof of Lemma 12 each Q i Q_i Q i is placed inside the dilated star F ( P i ) F(P_i) F ( P i ) , and these are polygons with pairwise disjoint interiors; hence no point of Q i Q_i Q i lies in the interior of Q j Q_j Q j for i ≠ j i \ne j i = j , and this persists under the translations into the mini-containers, including the passage to subsequences.
Finally, Corollary 14 allows all rectangles to be enlarged to common dimensions κ r × κ h \kappa r \times\kappa h κ r × κh while keeping the area estimate; this applies verbatim to the copies above. The constants depend on ε \varepsilon ε but not on r / h r/h r / h or on the number of stars.
It therefore suffices to straighten the containing bowls.
Coordinates and separators. Fix one mini-container with bowls Q 1 , … , Q k Q_1,\ldots,Q_k Q 1 , … , Q k . Choose coordinates with horizontal axis along the common type direction u u u and vertical axis along the alignment direction d d d , so that u = ( 1 , 0 ) u=(1,0) u = ( 1 , 0 ) and d = ( 0 , 1 ) d=(0,1) d = ( 0 , 1 ) . Signed rotations are measured in these coordinates, which may reverse the orientation of the ambient plane. Write q i = ( x i , t i ) q_i=(x_i,t_i) q i = ( x i , t i ) , L i = L ( Q i ) L_i=L(Q_i) L i = L ( Q i ) , and R i = R ( Q i ) R_i=R(Q_i) R i = R ( Q i ) . Let σ i = Separator ( Q i ) \sigma_i=\operatorname{Separator}(Q_i) σ i = Separator ( Q i ) be the separator defined in the preceding section: the chain L i q i R i L_iq_iR_i L i q i R i , together with the horizontal rays extending outward from L i L_i L i and R i R_i R i . We call these rays its tails and the segments q i L i , q i R i q_iL_i,q_iR_i q i L i , q i R i its finite arms. The separator divides the plane into an upper and a lower component. Write Above ( σ i ) \operatorname{Above}(\sigma_i) Above ( σ i ) and Below ( σ i ) \operatorname{Below}(\sigma_i) Below ( σ i ) for their closures, with the upper component containing points of sufficiently large vertical coordinate. Order the bowls by their separators from bottom to top. Their tails have heights t i + h t_i+h t i + h , so their reference-point heights t i t_i t i follow this order as well. Below the tails, the upper component is precisely the triangle q i L i R i q_iL_iR_i q i L i R i . Define the normalized horizontal coordinates A i A_i A i and B i B_i B i of the two arm endpoints by R i − q i = ( r A i , h ) R_i-q_i=(rA_i,h) R i − q i = ( r A i , h ) and L i − q i = ( r B i , h ) L_i-q_i=(rB_i,h) L i − q i = ( r B i , h ) . Using the estimates in Equation (7) and h = 100 w h=100w h = 100 w , we obtain
700 ≤ A i ≤ 3200 − 400 ≤ B i ≤ 300. (17) 700 \le A_i \le3200 \qquad-400 \le B_i \le300. \tag*{(17)} 700 ≤ A i ≤ 3200 − 400 ≤ B i ≤ 300. (17)
In particular, A i − B i ≥ 400 A_i-B_i\ge400 A i − B i ≥ 400 , a margin we will use repeatedly. Throughout, bowls and separators may touch along their boundaries, and the stack order between separators is understood weakly at such contacts, as in the preceding section; what makes contacts harmless is the nonpenetration property of Lemma 28 , which keeps the zero-width arms of one bowl out of the interior of every other. Note that two separators can coincide only if their bowls share the reference point and both arm directions, and then, since the two bowls have disjoint interiors and are both star-shaped about the common point, at most one of them has interior points outside the common closed triangle q L R qLR q L R ; we place that bowl below the other in the stack. Finally, let θ i \theta_i θ i be the angle that R i − q i R_i-q_i R i − q i makes with the positive horizontal axis. All these angles lie in a short common interval, and we take real representatives there, so that differences of angles never wrap around. The next lemma bounds the sum of successive angle changes. This will bound the total displacement in the rotation procedure.
Figure 18. A bowl Q i = P i ∪ q i L i ∪ q i R i Q_i=P_i\cup q_iL_i\cup q_iR_i Q i = P i ∪ q i L i ∪ q i R i in the coordinates ( u , d ) (u,d) ( u , d ) of its mini-container, with its separator σ i \sigma_i σ i (two finite arms and two horizontal tails at height t i + h t_i+h t i + h ), the triangle q i L i R i q_iL_iR_i q i L i R i , and the normalized arm coordinates A i , B i A_i,B_i A i , B i of Equation (17) .
Figure 19. Two consecutive separators of a stack. Since q i + 1 q_{i+1} q i + 1 lies in the triangle q i L i R i q_iL_iR_i q i L i R i , the right arm of σ i + 1 \sigma_{i+1} σ i + 1 must exit through the top chord at or left of R i R_i R i ; a steeper arm (dashed) would cross the right tail of σ i \sigma_i σ i . This bounds A i + 1 − A i A_{i+1}-A_i A i + 1 − A i by O ( Δ i / h ) O(\Delta_i/h) O ( Δ i / h ) .
Lemma 29. For the bowls in stack order,
∑ i = 1 k − 1 ∣ θ i + 1 − θ i ∣ = O ( h / r ) . \sum_{i=1}^{k-1} \lvert\theta_{i+1}-\theta_i\rvert=O(h/r). i = 1 ∑ k − 1 ∣ θ i + 1 − θ i ∣ = O ( h / r ) . The same bound holds for every subsequence in the inherited order.
Proof. For each i < k i<k i < k , put Δ i = t i + 1 − t i \Delta_i=t_{i+1}-t_i Δ i = t i + 1 − t i . If Δ i < h \Delta_i<h Δ i < h , the point q i + 1 q_{i+1} q i + 1 lies in the triangle q i L i R i q_iL_iR_i q i L i R i , because it is above σ i \sigma_i σ i and below its tails. At height t i + h t_i+h t i + h , the right arm of σ i + 1 \sigma_{i+1} σ i + 1 must lie no farther right than R i R_i R i ; otherwise it would cross the right tail of σ i \sigma_i σ i . Therefore x i + 1 + r A i + 1 ( 1 − Δ i / h ) ≤ x i + r A i x_{i+1}+rA_{i+1}(1-\Delta_i/h)\le x_i+rA_i x i + 1 + r A i + 1 ( 1 − Δ i / h ) ≤ x i + r A i . Since q i + 1 q_{i+1} q i + 1 lies in the triangle, we also have x i + 1 ≥ x i + r B i Δ i / h x_{i+1}\ge x_i+rB_i\Delta_i/h x i + 1 ≥ x i + r B i Δ i / h . It follows that A i + 1 − A i ≤ ( A i + 1 − B i ) Δ i / h ≤ 2 M Δ i / h A_{i+1}-A_i\le(A_{i+1}-B_i)\Delta_i/h\le2M\Delta_i/h A i + 1 − A i ≤ ( A i + 1 − B i ) Δ i / h ≤ 2 M Δ i / h . For Δ i ≥ h \Delta_i\ge h Δ i ≥ h the last bound on the positive part is automatic from Equation (17) . Thus, in both cases, max { A i + 1 − A i , 0 } ≤ 2 M Δ i / h \max\{A_{i+1}-A_i,0\}\le2M\Delta_i/h max { A i + 1 − A i , 0 } ≤ 2 M Δ i / h .
The reference points lie in a rectangle of height O ( h ) O(h) O ( h ) , so ∑ i Δ i = O ( h ) \sum_i\Delta_i=O(h) ∑ i Δ i = O ( h ) and the sum of the positive changes of A i A_i A i is O ( 1 ) O(1) O ( 1 ) . The negative changes have the same total up to A 1 − A k = O ( 1 ) A_1-A_k=O(1) A 1 − A k = O ( 1 ) . Consequently, ∑ i ∣ A i + 1 − A i ∣ = O ( 1 ) \sum_i\lvert A_{i+1}-A_i\rvert=O(1) ∑ i ∣ A i + 1 − A i ∣ = O ( 1 ) .
Since A i ≥ 700 A_i\ge700 A i ≥ 700 , the radius angle is θ i = arctan ( h / ( r A i ) ) \theta_i=\arctan(h/(rA_i)) θ i = arctan ( h / ( r A i )) . For every A ≥ 700 A\ge700 A ≥ 700 ,
∣ d d A arctan ( h r A ) ∣ = h / r A 2 + ( h / r ) 2 ≤ h 700 2 r . \left\lvert\frac{d}{dA}\arctan\left(\frac{h}{rA}\right)\right\rvert=\frac{h/r}{A^2+(h/r)^2}\le\frac{h}{700^2r}. d A d arctan ( r A h ) = A 2 + ( h / r ) 2 h / r ≤ 70 0 2 r h .
::: The mean value theorem and the bound on the total variation of A i A_i A i give
∑ i ∣ θ i + 1 − θ i ∣ ≤ h 7002 r ∑ i ∣ A i + 1 − A i ∣ = O ( h / r ) . \sum_i |\theta_{i+1}-\theta_i| \le\frac{h}{7002r}\sum_i |A_{i+1}-A_i| = O(h/r). i ∑ ∣ θ i + 1 − θ i ∣ ≤ 7002 r h i ∑ ∣ A i + 1 − A i ∣ = O ( h / r ) .
A subsequence has no greater total variation: each of its jumps is bounded by the sum of the original consecutive jumps it skips, and these skipped ranges are disjoint.
Although the separators of a stack are disjoint, a separator may still pass through the interior of another bowl. This is inconvenient for rotations: moving a separator does not automatically preserve the position of a bowl lying across it. We therefore split the stack into a constant number of consecutive blocks in which every separator avoids the interior of every other bowl. This lets us enclose individual bowls between neighboring separators and move these enclosures as rigid objects.
Lemma 30. A stack in a mini-container can be partitioned into O ( 1 ) O(1) O ( 1 ) consecutive blocks such that, within each block, no separator meets the interior of another bowl. Boundary contacts are allowed.
Proof. Partition the reference points by the height intervals [ ν h / 2 , ( ν + 1 ) h / 2 ) [\nu h/2,(\nu+1)h/2) [ ν h /2 , ( ν + 1 ) h /2 ) ; this gives O ( 1 ) O(1) O ( 1 ) consecutive blocks. Fix i < j i<j i < j in one block, so 0 ≤ t j − t i < h / 2 0\le t_j-t_i<h/2 0 ≤ t j − t i < h /2 . In the ( u , d ) (u,d) ( u , d ) -frame of the fine type, every point of P k P_k P k has d d d -coordinate within 1.13 w 1.13w 1.13 w of t k t_k t k (a point at signed distances x ′ , ω ′ x',\omega' x ′ , ω ′ along and across the radius line has d d d -coordinate x ′ sin β + ω ′ cos β x'\sin\beta+\omega'\cos\beta x ′ sin β + ω ′ cos β with ∣ x ′ ∣ ≤ r |x'|\le r ∣ x ′ ∣ ≤ r , ∣ ω ′ ∣ ≤ w |\omega'|\le w ∣ ω ′ ∣ ≤ w , sin β ≤ π 25 w \sin\beta\le\frac{\pi}{25}w sin β ≤ 25 π w ). Hence the interiors of Q i Q_i Q i and Q j Q_j Q j lie below height t i + h / 2 + 1.13 w < min ( t i , t j ) + h t_i+h/2+1.13w<\min(t_i,t_j)+h t i + h /2 + 1.13 w < min ( t i , t j ) + h , where both pairs of tails are, and the finite arms are excluded by Lemma 28 .
Enclosing every third bowl. We now enclose each retained bowl between its neighboring separators. These bounded enclosures can be moved as rigid objects, carrying the bowls inside them.
Lemma 31. Apart from at most two end bowls, a locally separated block can be partitioned into three subsequences. In each subsequence, every bowl lies in a bounded polygonal region, called its enclosure. Consecutive enclosures are separated by two of the original separators, and all enclosures lie in an O ( r ) × O ( h ) O(r)\times O(h) O ( r ) × O ( h ) rectangle.
Proof. Index the block by 1 , … , ℓ 1,\ldots,\ell 1 , … , ℓ and set aside its first and last bowls, which are packed individually at cost O ( r h ) O(rh) O ( r h ) . Let S S S be a vertical strip of width O ( r ) O(r) O ( r ) containing all bowls and all finite arms, and for 2 ≤ i ≤ ℓ − 1 2\le i\le\ell-1 2 ≤ i ≤ ℓ − 1 put
E i = S ∩ Above ( σ i − 1 ) ∩ Below ( σ i + 1 ) . E_i=S\cap\operatorname{Above}(\sigma_{i-1})\cap\operatorname{Below}(\sigma_{i+1}). E i = S ∩ Above ( σ i − 1 ) ∩ Below ( σ i + 1 ) . Inside S S S each separator is a simple arc joining the two walls, so E i E_i E i is a bounded polygon of horizontal span O ( r ) O(r) O ( r ) and vertical span O ( h ) O(h) O ( h ) .
We claim Q i ⊆ E i Q_i\subseteq E_i Q i ⊆ E i . Its arms lie on σ i \sigma_i σ i , which lies weakly between σ i − 1 \sigma_{i-1} σ i − 1 and σ i + 1 \sigma_{i+1} σ i + 1 . The rest of Q i Q_i Q i is the star P i P_i P i , whose interior is connected and by Lemma 30 meets neither σ i − 1 \sigma_{i-1} σ i − 1 nor σ i + 1 \sigma_{i+1} σ i + 1 , so it lies on one side of each; since q i q_i q i is between the two separators, that side is the right one unless q i q_i q i itself lies on σ i − 1 \sigma_{i-1} σ i − 1 or σ i + 1 \sigma_{i+1} σ i + 1 . In that degenerate case, P i P_i P i contains the two segments q i R P i q_iR_{P_i} q i R P i and q i L P i q_iL_{P_i} q i L P i in the directions ( r A i , h ) (rA_i,h) ( r A i , h ) and ( r B i , h ) (rB_i,h) ( r B i , h ) ; if P i P_i P i were on the wrong side of, say, σ i − 1 \sigma_{i-1} σ i − 1 , both segments would lie on σ i − 1 ∩ σ i \sigma_{i-1}\cap\sigma_i σ i − 1 ∩ σ i , forcing σ i = σ i − 1 \sigma_i=\sigma_{i-1} σ i = σ i − 1 , and then Q i Q_i Q i would be the bowl with interior points outside the common triangle, which the tie-break convention places below Q i − 1 Q_{i-1} Q i − 1 , not above. The same argument applies to σ i + 1 \sigma_{i+1} σ i + 1 .
Finally, group the indices by residue modulo 3. Between E i E_i E i and E i + 3 E_{i+3} E i + 3 lie σ i + 1 \sigma_{i+1} σ i + 1 and σ i + 2 \sigma_{i+2} σ i + 2 , so the enclosures of a class are pairwise disjoint, separated by two original separators, and in stack order.
Each enclosure is now moved as a rigid object, carrying its bowl with it. Thus feasibility reduces to keeping the enclosures disjoint. At a step of the procedure, the prefix consists of the enclosures already aligned, and the suffix consists of all remaining enclosures in their original order.
Lemma 32. Let E 1 , … , E m E_1,\ldots,E_m E 1 , … , E m be one subsequence of enclosures from Lemma 31 , relabeled in their inherited order. For each i i i , let q i q_i q i be the reference point of its bowl and let θ i \theta_i θ i be its original radius angle, as above. Let I 0 I_0 I 0 be a common interval of length at most ϵ h / r \epsilon h/r ϵ h / r containing these angles. For any prescribed θ ∗ ∈ I 0 \theta_* \in I_0 θ ∗ ∈ I 0 , the enclosures can be repacked in an O ( r ) × O ( h ) O(r) \times O(h) O ( r ) × O ( h ) rectangle with disjoint interiors, in their original order, and with all radius vectors pointing in direction θ ∗ \theta_* θ ∗ .
Proof. Write H = h / r H=h/r H = h / r ; then 0 < H < 200 0 < H < 200 0 < H < 200 . By Equation (17) , 700 ≤ A i ≤ 3200 700 \le A_i \le3200 700 ≤ A i ≤ 3200 and − 400 ≤ B i ≤ 300 -400 \le B_i \le300 − 400 ≤ B i ≤ 300 . Fix I = [ 400 , 600 ] I=[400,600] I = [ 400 , 600 ] with midpoint s 0 = 500 s_0=500 s 0 = 500 , and J = ( 450 , 550 ) J=(450,550) J = ( 450 , 550 ) . For s ∈ I s \in I s ∈ I let v s = ( r s , h ) v_s=(rs,h) v s = ( r s , h ) and F s ( x , y ) = x − ( s / H ) y F_s(x,y)=x-(s/H)y F s ( x , y ) = x − ( s / H ) y , so that the lines parallel to v s v_s v s are the level sets of F s F_s F s . Along a separator, from the left tail to the right tail, F s F_s F s increases by r ( s − B i ) ≥ 100 r r(s-B_i) \ge100r r ( s − B i ) ≥ 100 r on the left arm, by r ( A i − s ) ≥ 100 r r(A_i-s) \ge100r r ( A i − s ) ≥ 100 r on the right arm, and strictly along both tails (Figure 20 ). Hence every line parallel to v s v_s v s meets each separator exactly once, and it meets the separators in stack order. A common rotation through an angle ∣ γ ∣ ≤ ϵ H |\gamma| \le\epsilon H ∣ γ ∣ ≤ ϵH changes F s ( z ) F_s(z) F s ( z ) by at most 1 + ( s / H ) 2 ∣ γ ∣ ∥ z ∥ ≤ ϵ ( H + s ) ∥ z ∥ \sqrt{1+(s/H)^2}|\gamma|\lVert z\rVert\le\epsilon(H+s)\lVert z\rVert 1 + ( s / H ) 2 ∣ γ ∣ ∥ z ∥ ≤ ϵ ( H + s ) ∥ z ∥ , which is below 100 r 100r 100 r for an arm (∥ z ∥ ≤ 3400 r \lVert z\rVert\le3400r ∥ z ∥ ≤ 3400 r ) and below 1 1 1 for a unit tail direction once ϵ ≤ 10 − 6 \epsilon\le10^{-6} ϵ ≤ 1 0 − 6 ; so the same conclusions hold after any such rotation. Let
Figure 20. The cone K K K of admissible translation directions for a separator. Along σ i \sigma_i σ i , from the left tail to the right tail, the functional F s F_s F s is strictly increasing, with increments of at least 100 r 100r 100 r on the two arms; hence every line parallel to v s v_s v s meets σ i \sigma_i σ i exactly once.
K = { λ ( r s , h ) : λ > 0 , s ∈ J } , K=\{\lambda(rs,h):\lambda>0,\ s\in J\}, K = { λ ( r s , h ) : λ > 0 , s ∈ J } ,
an open cone with K + K ⊆ K K+K\subseteq K K + K ⊆ K , since the parameter of a sum is a weighted average.
The invariant. For i < j i<j i < j , p ∈ E i p\in E_i p ∈ E i and z ∈ E j z\in E_j z ∈ E j we maintain p − z ∉ K p-z\notin K p − z ∈ / K . It holds for the original family, and after any common translation and common rotation by at most ϵ H \epsilon H ϵH : a line in a direction of K K K meets the upper bounding separator of E i E_i E i no later than the lower bounding separator of E j E_j E j , so it cannot pass through E j E_j E j before E i E_i E i , as p − z ∈ K p-z\in K p − z ∈ K would require. The invariant forbids a common interior point, since an open disk in E i ∩ E j E_i\cap E_j E i ∩ E j contains two points whose difference is a small vector of K K K .
The step. Put θ 0 = θ ∗ \theta_0=\theta_* θ 0 = θ ∗ and δ i = θ i − 1 − θ i \delta_i=\theta_{i-1}-\theta_i δ i = θ i − 1 − θ i for i = 1 , … , m i=1,\ldots,m i = 1 , … , m . At step i i i the prefix E 1 , … , E i − 1 E_1,\ldots,E_{i-1} E 1 , … , E i − 1 is already aligned and fixed; rotate the suffix E i , … , E m E_i,\ldots,E_m E i , … , E m about its current reference point q i q_i q i through δ i \delta_i δ i , so that bowl i i i now points at θ ∗ \theta_* θ ∗ , and then translate the suffix by T i = c τ i ( r s 0 , h ) T_i=c\tau_i(rs_0,h) T i = c τ i ( r s 0 , h ) with τ i = ∣ δ i ∣ / H \tau_i=|\delta_i|/H τ i = ∣ δ i ∣/ H and a universal constant c c c fixed below (Figure 21 ). Since the suffix has only undergone common rigid motions, its diameter is still that of the original O ( r ) × O ( h ) O(r)\times O(h) O ( r ) × O ( h ) rectangle, at most L r Lr L r , so the rotation displaces each of its points by at most L r ∣ δ i ∣ = L τ i h Lr|\delta_i|=L\tau_i h L r ∣ δ i ∣ = L τ i h . Writing the net displacement of a point as τ i ( r ( c s 0 + e x ) , h ( c + e y ) ) \tau_i(r(cs_0+e_x),h(c+e_y)) τ i ( r ( c s 0 + e x ) , h ( c + e y )) with ∣ e x ∣ ≤ L H ≤ 200 L |e_x|\le LH\le200L ∣ e x ∣ ≤ L H ≤ 200 L and ∣ e y ∣ ≤ L |e_y|\le L ∣ e y ∣ ≤ L , its direction parameter s ′ = ( c s 0 + e x ) / ( c + e y ) s'=(cs_0+e_x)/(c+e_y) s ′ = ( c s 0 + e x ) / ( c + e y ) satisfies ∣ s ′ − s 0 ∣ ≤ 200 L ( 1 + s 0 ) / ( c − 200 L ) |s'-s_0|\le200L(1+s_0)/(c-200L) ∣ s ′ − s 0 ∣ ≤ 200 L ( 1 + s 0 ) / ( c − 200 L ) , which is below 50 for c c c large. Thus every point of the suffix moves by a vector of K K K (if δ i = 0 \delta_i=0 δ i = 0 nothing moves).
Figure 21. One step of the sweep, for three enclosures of a residue class: the prefix (orange, already aligned, radius at θ ∗ \theta_\ast θ ∗ ) and the suffix E i E_i E i , E i + 1 E_{i+1} E i + 1 (green). δ i = θ ∗ − θ i \delta_i=\theta_\ast-\theta_i δ i = θ ∗ − θ i is the angle between the arm of bowl i i i and the common direction. Light green is E i + K E_i+K E i + K and E i + 1 + K E_{i+1}+K E i + 1 + K . The step rotates the suffix about q i q_i q i through δ i \delta_i δ i and translates it by T i ∈ K T_i\in K T i ∈ K , which moves every suffix point by a vector of K K K . Afterwards bowl i i i points at θ ∗ \theta_\ast θ ∗ and the prefix is unchanged.
The invariant survives the step. Within the prefix nothing changed. Within the suffix the motion is common, and its total rotation since the original configuration is θ ∗ − θ i \theta_\ast-\theta_i θ ∗ − θ i , of absolute value at most ϵ H \epsilon H ϵH as both angles lie in I 0 I_0 I 0 . For p p p in the prefix and z z z in the suffix with new position z ′ z' z ′ , we have z ′ − z ∈ K z'-z\in K z ′ − z ∈ K ; if p − z ′ p-z' p − z ′ were in K K K (or zero), then p − z = ( p − z ′ ) + ( z ′ − z ) ∈ K p-z=(p-z')+(z'-z)\in K p − z = ( p − z ′ ) + ( z ′ − z ) ∈ K , against the invariant before the step. Hence the prefix and the moved suffix are disjoint, and after all m m m steps the enclosures have pairwise disjoint interiors, in their original order, with every radius at θ ∗ \theta_\ast θ ∗ .
Size. By Lemma 29 applied to the subsequence, ∑ i = 1 m ∣ δ i ∣ ≤ ∣ θ ∗ − θ 1 ∣ + ∑ i > 2 ∣ δ i ∣ = O ( h / r ) \sum_{i=1}^{m}|\delta_i|\le|\theta_\ast-\theta_1|+\sum_{i>2}|\delta_i|=O(h/r) ∑ i = 1 m ∣ δ i ∣ ≤ ∣ θ ∗ − θ 1 ∣ + ∑ i > 2 ∣ δ i ∣ = O ( h / r ) . The translations total ∑ i ( T i ) y = c r ∑ i ∣ δ i ∣ = O ( h ) \sum_i(T_i)_y=cr\sum_i|\delta_i|=O(h) ∑ i ( T i ) y = cr ∑ i ∣ δ i ∣ = O ( h ) vertically and ∑ i ( T i ) x = c s 0 ( r 2 / h ) ∑ i ∣ δ i ∣ = O ( r ) \sum_i(T_i)_x=cs_0(r^2/h)\sum_i|\delta_i|=O(r) ∑ i ( T i ) x = c s 0 ( r 2 / h ) ∑ i ∣ δ i ∣ = O ( r ) horizontally, and the rotations displace any point by at most L r ∑ i ∣ δ i ∣ = O ( h ) = O ( r ) Lr\sum_i|\delta_i|=O(h)=O(r) L r ∑ i ∣ δ i ∣ = O ( h ) = O ( r ) in total. So the final configuration lies in an O ( r ) × O ( h ) O(r)\times O(h) O ( r ) × O ( h ) rectangle.
Theorem 33. For a mini-container from Lemma 28 , all its stars can be rotationally repacked into a rectangle with side lengths O ( r ) O(r) O ( r ) and O ( h ) O(h) O ( h ) . Their directed radii then point in one common direction, and the side of length O ( r ) O(r) O ( r ) is parallel to that direction.
Proof. Lemma 30 splits the mini-container into O ( 1 ) O(1) O ( 1 ) locally separated blocks. Fix a target angle θ ∗ \theta_\ast θ ∗ that occurs among the bowls; it lies in the common angle interval of every block. In each block apply Lemma 31 and then Lemma 32 to each of the three classes with this θ ∗ \theta_\ast θ ∗ , and rotate each of the O ( 1 ) O(1) O ( 1 ) end bowls to θ ∗ \theta_\ast θ ∗ individually. This yields O ( 1 ) O(1) O ( 1 ) rectangles of span O ( r ) O(r) O ( r ) along u u u and O ( h ) O(h) O ( h ) along d d d , each holding bowls whose radii all point in direction θ ∗ \theta_\ast θ ∗ ; the rectangles are placed independently.
Since θ ∗ \theta_\ast θ ∗ is the radius angle of some bowl, A i ≥ 700 A_i\ge700 A i ≥ 700 in Equation (17) gives ∣ sin θ ∗ ∣ ≤ h / ( 700 r ) |\sin\theta_\ast|\le h/(700r) ∣ sin θ ∗ ∣ ≤ h / ( 700 r ) . A rectangle with spans W = O ( r ) W=O(r) W = O ( r ) along u u u and V = O ( h ) V=O(h) V = O ( h ) along d d d therefore has span ∣ W ∣ ∣ cos θ ∗ ∣ + ∣ V ∣ ∣ sin θ ∗ ∣ = O ( r ) + O ( h 2 / r ) = O ( r ) |W||\cos\theta_\ast|+|V||\sin\theta_\ast|=O(r)+O(h^2/r)=O(r) ∣ W ∣∣ cos θ ∗ ∣ + ∣ V ∣∣ sin θ ∗ ∣ = O ( r ) + O ( h 2 / r ) = O ( r ) in direction θ ∗ \theta_\ast θ ∗ and span ∣ W ∣ ∣ sin θ ∗ ∣ + ∣ V ∣ ∣ cos θ ∗ ∣ = O ( h ) |W||\sin\theta_\ast|+|V||\cos\theta_\ast|=O(h) ∣ W ∣∣ sin θ ∗ ∣ + ∣ V ∣∣ cos θ ∗ ∣ = O ( h ) perpendicular to it, using h < 200 r h<200r h < 200 r . Rebox each packing in a rectangle aligned with θ ∗ \theta_\ast θ ∗ of these
dimensions, stack the O ( 1 ) O(1) O ( 1 ) boxes perpendicular to θ ∗ \theta_* θ ∗ , and replace each bowl by the star it contains. The result is a rectangle of side lengths O ( r ) O(r) O ( r ) along and O ( h ) O(h) O ( h ) across the common radius direction, as claimed.
We conclude with the main theorem from this section, which enables our algorithm for the rotational case.
Theorem 34. For one size group G \mathcal{G} G , every rotational packing into a convex container C C C yields, for some integer m ≥ 1 m \ge1 m ≥ 1 , a rotational packing into rectangles C 1 , … , C m C_1,\ldots,C_m C 1 , … , C m with the following properties:
each rectangle has dimensions O ( r ) × O ( w ) O(r) \times O(w) O ( r ) × O ( w ) ;
all directed distinguished radii point horizontally to the right in every rectangle;
after enlarging the rectangles to common dimensions κ r × κ w \kappa r \times\kappa w κ r × κ w for a fixed universal constant κ \kappa κ , their total area is O ( ∣ C ∣ ) O(|C|) O ( ∣ C ∣ ) .
Consequently, the entire group can be packed into a single convex container of area O ( ∣ C ∣ ) O(|C|) O ( ∣ C ∣ ) with all directed radii horizontal.
Proof. Lemma 28 gives N N N mini-containers of common dimensions κ r × κ h \kappa r \times\kappa h κ r × κh with N κ 2 r h = O ( ∣ C ∣ ) N\kappa^2rh = O(|C|) N κ 2 r h = O ( ∣ C ∣ ) . By Theorem 33 , the stars of each mini-container can be repacked into a rectangle with side C 1 r C_1r C 1 r along their common radius direction and side C 1 h C_1h C 1 h across it, for a universal constant C 1 C_1 C 1 . Rotate each such packing as a whole until its radii point to the right; its rectangle is then axis-parallel, of width C 1 r C_1r C 1 r and height C 1 h C_1h C 1 h . Enlarge all N N N rectangles to C 1 r × C 1 h C_1r \times C_1h C 1 r × C 1 h and stack them vertically. The result has width C 1 r C_1r C 1 r , height N C 1 h NC_1h N C 1 h and area N C 1 2 r h = O ( ∣ C ∣ ) NC_1^2rh = O(|C|) N C 1 2 r h = O ( ∣ C ∣ ) ; as h = 100 w h = 100w h = 100 w , this is the claim. □
Corollary 35. Let G ^ \widehat{\mathcal{G}} G be obtained by rotating each input star so that its radius vector points in the positive horizontal direction. Write O P T t r a n s \mathrm{OPT}_{\mathrm{trans}} OPT trans and O P T r o t \mathrm{OPT}_{\mathrm{rot}} OPT rot for the minimum area of a convex container when translations alone, or translations and rotations, respectively, are allowed. Then
O P T r o t ( G ) ≤ O P T t r a n s ( G ^ ) ≤ κ ′ O P T r o t ( G ) \mathrm{OPT}_{\mathrm{rot}}(\mathcal{G}) \le\mathrm{OPT}_{\mathrm{trans}}(\widehat{\mathcal{G}}) \le\kappa' \mathrm{OPT}_{\mathrm{rot}}(\mathcal{G}) OPT rot ( G ) ≤ OPT trans ( G ) ≤ κ ′ OPT rot ( G ) for a universal constant κ ′ \kappa' κ ′ . The common per-group translational algorithm from the preceding section consequently applies to G ^ \widehat{\mathcal{G}} G with only constant additional loss.
Proof. O P T r o t ( G ) ≤ O P T t r a n s ( G ^ ) \mathrm{OPT}_{\mathrm{rot}}(\mathcal{G}) \le\mathrm{OPT}_{\mathrm{trans}}(\widehat{\mathcal{G}}) OPT rot ( G ) ≤ OPT trans ( G ) holds as any translational packing of G ^ \widehat{\mathcal{G}} G is a rotational packing of G \mathcal{G} G . Apply Theorem 34 to rotational packings approaching the infimum. In the resulting packings every star is a translate of its copy in G ^ \widehat{\mathcal{G}} G , which gives the displayed bound. The algorithm then runs the translational pipeline of Lemmas 11 and 19 and Corollary 14 on G ^ \widehat{\mathcal{G}} G ; the enclosures of this section serve only the existence proof. □
We now obtain the rotational analogue of Lemma 26.
Lemma 36. For a set of stars P \mathcal{P} P , in polynomial time, we can compute a rotation of each star and a packing of the rotated stars into a set of convex mini-containers of total area O ( log n ) ⋅ O P T r o t ( P ) O(\log n) \cdot\mathrm{OPT}_{\mathrm{rot}}(\mathcal{P}) O ( log n ) ⋅ OPT rot ( P ) . Every mini-container B B B satisfies
span z ( B ) = O ( span z ( P ) ) \operatorname{span}_{z}(B) = O(\operatorname{span}_{z}(\mathcal{P})) span z ( B ) = O ( span z ( P )) for every direction z z z and every star P P P that B B B contains, where P P P is taken in its rotated position.
Proof. Rotate each star so that its distinguished radius points horizontally to the right, and let P ^ \widehat{\mathcal{P}} P denote the resulting family. Rotations preserve r P r_P r P and w P w_P w P , so the size groups do not change.
As in Lemma 26, pack each star satisfying r P < r max / n r_P < r_{\max}/n r P < r m a x / n or w P < w max / n w_P < w_{\max}/n w P < w m a x / n individually into the convex hull of its rotated copy. These hulls have total area O ( r max w max ) = O ( OPT r o t ( P ) ) O(r_{\max}w_{\max}) = O(\operatorname{OPT}_{\mathrm{rot}}(\mathcal{P})) O ( r m a x w m a x ) = O ( OPT rot ( P )) by Lemma 8 ; taking a convex hull does not change any span.
For every remaining size group G \mathcal{G} G , run Lemma 20 on G ^ \widehat{\mathcal{G}} G . The resulting mini-containers have total area O ( OPT t r a n s ( G ^ ) ) O(\operatorname{OPT}_{\mathrm{trans}}(\widehat{\mathcal{G}})) O ( OPT trans ( G )) ; indeed, the bound of that corollary is no larger than a constant multiple of the minimum area of a single convex container. Their span guarantee is precisely Corollary 21 .
It remains to bound the sum over the size groups. Consider an optimal rotational packing of P \mathcal{P} P , and let P ∗ \mathcal{P}^{*} P ∗ denote the stars with the orientations used in this packing. Write G ∗ \mathcal{G}^{*} G ∗ for the corresponding stars of G \mathcal{G} G . By Corollary 35,
OPT t r a n s ( G ^ ) = O ( OPT r o t ( G ) ) = O ( OPT ( G ∗ ) ) . \operatorname{OPT}_{\mathrm{trans}}(\widehat{\mathcal{G}}) = O(\operatorname{OPT}_{\mathrm{rot}}(\mathcal{G})) = O(\operatorname{OPT}(\mathcal{G}^{*})). OPT trans ( G ) = O ( OPT rot ( G )) = O ( OPT ( G ∗ )) .
Here the second bound holds because a translational packing of G ∗ \mathcal{G}^{*} G ∗ is also a rotational packing of G \mathcal{G} G .
The proof of Lemma 24 in fact gives the stronger single-container estimate
∑ G OPT ( G ∗ ) = O ( log n ) ⋅ OPT ( P ∗ ) . \sum_{\mathcal{G}} \operatorname{OPT}(\mathcal{G}^{*}) = O(\log n) \cdot\operatorname{OPT}(\mathcal{P}^{*}). G ∑ OPT ( G ∗ ) = O ( log n ) ⋅ OPT ( P ∗ ) .
To see this directly, for each class C i , j C_{i,j} C i , j considered in that proof, Equations (13) to (15) yield ∑ G ∈ C i , j OPT ( G ∗ ) = O ( OPT ( C i , j ∗ ) ) \sum_{\mathcal{G}\in C_{i,j}} \operatorname{OPT}(\mathcal{G}^{*}) = O(\operatorname{OPT}(C_{i,j}^{*})) ∑ G ∈ C i , j OPT ( G ∗ ) = O ( OPT ( C i , j ∗ )) . There are O ( log n ) O(\log n) O ( log n ) such classes for the remaining stars, and OPT ( C i , j ∗ ) ≤ OPT ( P ∗ ) \operatorname{OPT}(C_{i,j}^{*}) \le\operatorname{OPT}(\mathcal{P}^{*}) OPT ( C i , j ∗ ) ≤ OPT ( P ∗ ) for each one. Consequently the total area of the computed mini-containers is
O ( ∑ G OPT t r a n s ( G ^ ) ) = O ( log n ) ⋅ OPT ( P ∗ ) = O ( log n ) ⋅ OPT r o t ( P ) . O\left(\sum_{\mathcal{G}} \operatorname{OPT}_{\mathrm{trans}}(\widehat{\mathcal{G}})\right) = O(\log n) \cdot\operatorname{OPT}(\mathcal{P}^{*}) = O(\log n) \cdot\operatorname{OPT}_{\mathrm{rot}}(\mathcal{P}). O ( G ∑ OPT trans ( G ) ) = O ( log n ) ⋅ OPT ( P ∗ ) = O ( log n ) ⋅ OPT rot ( P ) .
Adding the singleton mini-containers proves the claim.
The rotational part of Theorem 1 now follows by applying Theorem 5 to these mini-containers. All stars, including the singleton ones, have horizontal distinguished radii. Thus each rotated star has horizontal span O ( r max ) O(r_{\max}) O ( r m a x ) and vertical span O ( w max ) O(w_{\max}) O ( w m a x ) , and Lemma 36 gives the same bounds for every mini-container. In particular, ℓ max h max = O ( r max w max ) = O ( OPT r o t ( P ) ) \ell_{\max}h_{\max} = O(r_{\max}w_{\max}) = O(\operatorname{OPT}_{\mathrm{rot}}(\mathcal{P})) ℓ m a x h m a x = O ( r m a x w m a x ) = O ( OPT rot ( P )) by Lemma 8 , whose proof is rotation invariant. The convex packing algorithm therefore returns a rectangle of area O ( log n ) ⋅ OPT r o t ( P ) O(\log n) \cdot\operatorname{OPT}_{\mathrm{rot}}(\mathcal{P}) O ( log n ) ⋅ OPT rot ( P ) .
APX-hardness
In this section, we show that star packing with constant-complexity pieces is APX hard, with or without rotations.
The problem MAX-VERTEX-DISJOINT-PATH-COVER. We will reduce from a problem called MAX-VERTEX-DISJOINT-PATH-COVER. In the problem MAX-VERTEX-DISJOINT-PATH-COVER(d d d ), we are given a directed graph G = ( V , E ) G = (V, E) G = ( V , E ) where the in- and out-degree of each vertex is at most d d d . We want to determine the largest number of edges in a path cover . A path cover is a set of disjoint, directed paths in G G G (possibly including single-vertex paths) such that every vertex of G G G is contained in a path. When G G G has a Hamiltonian path, then there is a path cover with ∣ V ∣ − 1 |V|-1 ∣ V ∣ − 1 edges, which is the most possible. So we can view this problem as an approximation version of HAMILTONIAN-PATH. If G G G has no edges, then the largest path cover is of size 0.
Bosboom, Demaine, Demaine, Hesterberg, Manurangsi and Yodpinyanee [10 ] show that, for some small ϵ > 0 \epsilon> 0 ϵ > 0 , MAX-VERTEX-DISJOINT-PATH-COVER is NP-hard to approximate to within a 1 − ϵ 1-\epsilon 1 − ϵ factor:
Lemma 37. ([10 ] , Theorem 2) For any ϵ < 1 1396640 \epsilon< \frac{1}{1396640} ϵ < 1396640 1 , the following is true: for any language λ \lambda λ in NP, there is a polynomial-time function that takes as input an instance φ \varphi φ of λ \lambda λ and outputs an instance ψ \psi ψ of MAX-VERTEX-DISJOINT-PATH-COVER(2). If φ \varphi φ is a “yes” instance, then ψ \psi ψ has a path cover with ∣ V ∣ − 1 |V|-1 ∣ V ∣ − 1 edges. If φ \varphi φ is a “no” instance, then the largest path cover in ψ \psi ψ has at most ( 1 − ϵ ) ( ∣ V ∣ − 1 ) (1-\epsilon)(|V|-1) ( 1 − ϵ ) ( ∣ V ∣ − 1 ) .
Reduction from MAX-DISJOINT-PATH-COVER to star packing. Our reduction encodes a directed graph using star-shaped polygons. Each vertex is represented by a polygon with a narrow spike and up to two slits. The spike of one polygon fits into a slit of another precisely when the corresponding directed edge exists. Thus, a directed path can be represented by a tightly nested stack of polygons.
The main difficulty is to ensure that an arbitrary packing cannot avoid this encoding. We introduce an additional container polygon and show that every sufficiently good packing must place the vertex polygons inside it, in a common nesting order and with nearly fixed orientations. Consecutive polygons corresponding to a missing edge must then be separated by an additional vertical distance. Consequently, a graph with no nearly complete path cover requires a container of strictly larger area.
Now we give the formal reduction. We are given a graph G = ( V , E ) G=(V,E) G = ( V , E ) , where each vertex has in- and out-degree at most 2. We want to construct a set of star shaped pieces of constant complexity. Label the vertices in V V V by 1 , … , n 1,\ldots,n 1 , … , n . Let e 1 ( i ) e_1(i) e 1 ( i ) and e 2 ( i ) e_2(i) e 2 ( i ) be the outgoing edges from vertex i i i (if they exist), with e 1 ( i ) < e 2 ( i ) e_1(i)<e_2(i) e 1 ( i ) < e 2 ( i ) . For each vertex i i i , we create one star S i S_i S i with at most 17 vertices. This is illustrated in Figure 22 and Figure 23 . In addition to G G G , the stars depend on two parameters δ 1 < 1 \delta_1<1 δ 1 < 1 and h > 1 h>1 h > 1 , which will be determined later.
Figure 22. The piece S i S_i S i has a spike, with angle determined by i i i , and up to 2 slits corresponding the edges outgoing from i i i . If i i i has fewer outgoing edges, then S i S_i S i has fewer slits.
Figure 23. Close up of the core of S i S_i S i . The width of the spike and the slits is determined by δ 1 \delta_1 δ 1 . The star point for S i S_i S i is illustrated.
We also make one outer container called C C C , which is the 7-gon illustrated in Figure 24 . This depends on a parameter δ 2 \delta_2 δ 2 , which we will set δ 2 = 1 10 \delta_2=\frac{1}{10} δ 2 = 10 1 .
Figure 24. The container piece C C C . The container is symmetric under reflection across a vertical line.
The construction has two different scales. The long arms control the overall nesting of the polygons, while the much smaller spikes and slits encode the edges of the graph. The parameter δ 1 \delta_1 δ 1 controls the angular separation between different spike and slit positions. The parameter h h h determines the length of the arms and makes rotations or incorrect nesting expensive. Finally, the outer polygon C C C forces the vertex polygons to occupy a common stack in any packing whose area is close to ∣ conv ( C ) ∣ |\operatorname{conv}(C)| ∣ conv ( C ) ∣ .
Lemma 38. If G G G has a Hamiltonian path (equivalently, a path cover with ∣ V ∣ − 1 |V|-1 ∣ V ∣ − 1 edges), then all the S i S_i S i can be packed inside the convex hull of C C C , even if rotations are not allowed.
Proof. An example is shown in Figure 25 . If there is an edge from i i i to j j j , then the spike on S i S_i S i fits into one of the slits in S j S_j S j . So a Hamiltonian path in G G G can be used to construct a stack of the S i S_i S i , where each piece has height n + 1 n+1 n + 1 above the one below it. The total height of the stack, from the bottom of the spike on the lowest S i S_i S i to the top of the highest, is h ( n + 1 ) + n ( n + 1 ) + 1 2 ( n + 1 ) h(n+1)+n(n+1)+\frac{1}{2}(n+1) h ( n + 1 ) + n ( n + 1 ) + 2 1 ( n + 1 ) . The slopes of the inner walls of C C C are such that one of the pieces S i S_i S i fits exactly inside C C C , with the base of the spike of S i S_i S i exactly 1 2 ( n + 1 ) \frac{1}{2}(n+1) 2 1 ( n + 1 ) units above the base of C C C .
Figure 25. Left: a graph G G G with max in/out-degree 2, and a marked Hamiltonian path. Right: the corresponding S i S_i S i stacking inside the container piece.
We now want to show that, if the best disjoint path cover in G G G has ( 1 − ϵ ) ( ∣ V ∣ − 1 ) (1-\epsilon)(|V|-1) ( 1 − ϵ ) ( ∣ V ∣ − 1 ) edges, then any packing of the C C C and S i S_i S i has cost at least 1 + Ω ( ϵ ) 1+\Omega(\epsilon) 1 + Ω ( ϵ ) times the cost of the packing described above. The idea is illustrated in Figure 26 .
Figure 26. Left: a graph G G G where the optimal disjoint path cover has ∣ V ∣ − 2 |V|-2 ∣ V ∣ − 2 edges. The path cover consists of the edge from 1 to 3 and a 0-length path containing vertex 2. Right: the pieces C C C and S i S_i S i that we construct packed according to this path cover. Piece S 1 S_1 S 1 is stacked inside S 2 S_2 S 2 , but there is no edge from 2 to 1, so the spike of S 1 S_1 S 1 does not fit into one of the slits in S 2 S_2 S 2 . For sufficiently chosen δ \delta δ and h h h , we will show that that stacking a pair of pieces like this requires us to use extra height proportional to the length of a spike.
We now fix some packing, and orient it so that C C C is oriented as in Figure 24 . The area of the convex hull of C C C is:
A 0 = ( h + 1 h + δ 2 ) ( h + n + 1 ) 2 ( n + 1 ) 2 A_0=\left(\frac{h+1}{h}+\delta_2\right)(h+n+1)^2(n+1)^2 A 0 = ( h h + 1 + δ 2 ) ( h + n + 1 ) 2 ( n + 1 ) 2
We write h = q n h=qn h = q n , where q ≥ 4000 q\ge4000 q ≥ 4000 is some constant to be determined later. We suppose n ≥ 100 n\ge100 n ≥ 100 , so we have q 2 n 4 ≤ A 0 ≤ ( q + 1 q ) 2 ( n + 1 n ) 4 ( 1 + δ 2 ) q 2 n 4 ≤ 3 2 q 2 n 4 q^2n^4\le A_0\le\left(\frac{q+1}{q}\right)^2\left(\frac{n+1}{n}\right)^4(1+\delta_2)q^2n^4\le\frac{3}{2}q^2n^4 q 2 n 4 ≤ A 0 ≤ ( q q + 1 ) 2 ( n n + 1 ) 4 ( 1 + δ 2 ) q 2 n 4 ≤ 2 3 q 2 n 4 . We want to show that, if the packing fits into a convex container of area larger than A 0 A_0 A 0 by at most small small constant factor, then we can find a good disjoint path cover for G G G . We start by proving a few lemmas.
Note that allowing rotations could, in principle, let a spike enter a slit that does not encode an edge of the graph. Our first step rules out this possibility for large rotations. The long arms of each S i S_i S i are almost as tall as the outer polygon C C C . Rotating S i S_i S i substantially forces part of it to extend beyond C C C , increasing the area of their convex hull. Hence a packing of sufficiently small area must keep every S i S_i S i close to its intended orientation.
Lemma 39. If the convex hull of the packing has area less than A 0 + 1 2 q n 4 A_0+\frac{1}{2}qn^4 A 0 + 2 1 q n 4 , then no S i S_i S i is rotated by more than θ ≥ 6 q \theta\ge\frac{6}{q} θ ≥ q 6 (radians, in either direction) compared to the orientation in Figure 22 .
Proof. Suppose S i S_i S i is rotated by θ ≥ 6 q \theta\ge\frac{6}{q} θ ≥ q 6 compared to the orientation in Figure 22 . If θ ≤ π 4 \theta\le\frac{\pi}{4} θ ≤ 4 π then there are points in S i S_i S i that have y y y coordinates differing by at least ( h + 1 ) ( n + 1 ) ( cos ( θ ) + sin ( θ ) ) ≥ ( h + 1 ) ( n + 1 ) ( 1 + 3 q ) (h+1)(n+1)(\cos(\theta)+\sin(\theta))\ge(h+1)(n+1)(1+\frac{3}{q}) ( h + 1 ) ( n + 1 ) ( cos ( θ ) + sin ( θ )) ≥ ( h + 1 ) ( n + 1 ) ( 1 + q 3 ) , as illustrated in Figure 27 (top).
Figure 27. Finding pairs of points with large vertical distance when S i S_i S i is rotated.
When π 4 ≤ θ ≤ 3 π 4 \frac{\pi}{4}\le\theta\le\frac{3\pi}{4} 4 π ≤ θ ≤ 4 3 π , then Figure 27 (bottoms) shows that there are a pair of points with vertical distance 2 ( h + 1 ) ( n + 1 ) sin ( θ ) ≥ ( h + 1 ) ( n + 1 ) ( 1 + 1 10 ) 2(h+1)(n+1)\sin(\theta)\ge(h+1)(n+1)(1+\frac{1}{10}) 2 ( h + 1 ) ( n + 1 ) sin ( θ ) ≥ ( h + 1 ) ( n + 1 ) ( 1 + 10 1 ) .
If S i S_i S i is rotated by 3 π 4 ≤ θ ≤ π − 6 q \frac{3\pi}{4}\le\theta\le\pi-\frac{6}{q} 4 3 π ≤ θ ≤ π − q 6 , then we can flip the picture and get the same bounds on the height difference, only depending on θ − π \theta-\pi θ − π instead of θ \theta θ .
:::
Now C C C has height ( h + n + 1 ) ( n + 1 ) = ( ( q + 1 ) n + 1 ) ( n + 1 ) ≤ ( 1 + 2 q ) ( n + 1 ) ( h + 1 ) (h+n+1)(n+1)=((q+1)n+1)(n+1)\le(1+\frac{2}{q})(n+1)(h+1) ( h + n + 1 ) ( n + 1 ) = (( q + 1 ) n + 1 ) ( n + 1 ) ≤ ( 1 + q 2 ) ( n + 1 ) ( h + 1 ) . So if S i S_i S i is rotated by more than 6 q \frac{6}{q} q 6 but less than π − 6 q \pi-\frac{6}{q} π − q 6 , then it sticks out above or below C C C by at least κ = 1 q ( h + 1 ) ( n + 1 ) \kappa=\frac{1}{q}(h+1)(n+1) κ = q 1 ( h + 1 ) ( n + 1 ) . This means that one of the 3 types of triangles shown in Figure 28 is contained in the convex hull of S i S_i S i and C C C . Such a triangle has area at least 1 2 q ( h + 1 ) 2 ( n + 1 ) 2 ≥ 1 2 q n 4 \frac{1}{2q}(h+1)^2(n+1)^2\ge\frac{1}{2}qn^4 2 q 1 ( h + 1 ) 2 ( n + 1 ) 2 ≥ 2 1 q n 4 .
Figure 28. If two points on S i S_i S i have vertical difference ≥ ( 1 + 1 1000 ) ( h + 1 ) ( n + 1 ) \ge(1+\frac{1}{1000})(h+1)(n+1) ≥ ( 1 + 1000 1 ) ( h + 1 ) ( n + 1 ) , then there is either a point above the top of C C C by at least κ \kappa κ , below the bottom of C C C by at least κ \kappa κ and left of the middle of C C C , or below the bottom of C C C by at least κ \kappa κ and right of the middle of C C C . So the convex hull of S i S_i S i and C C C contains one of the triangles shown.
The remaining case is when S i S_i S i is rotated by close to π \pi π relative to C C C . The only cases to analyze are the ones shown in Figure 29 , which clearly exceed the allowed area.
Figure 29. ≥ cos ( θ − π ) ( 1 + h h + 1 ) ( h + 1 ) ( n + 1 ) − ( h + n + 1 ) ( n + 1 ) \ge\cos(\theta-\pi)\left(1+\frac{h}{h+1}\right)(h+1)(n+1)-(h+n+1)(n+1) ≥ cos ( θ − π ) ( 1 + h + 1 h ) ( h + 1 ) ( n + 1 ) − ( h + n + 1 ) ( n + 1 ) ; ≥ 2 ( h + 1 ) ( n + 1 ) cos ( θ − π ) \ge2(h+1)(n+1)\cos(\theta-\pi) ≥ 2 ( h + 1 ) ( n + 1 ) cos ( θ − π ) ; ≥ h h + 1 cos ( θ − π ) ( h + 1 ) ( n + 1 ) \ge\frac{h}{h+1}\cos(\theta-\pi)(h+1)(n+1) ≥ h + 1 h cos ( θ − π ) ( h + 1 ) ( n + 1 ) ; ≥ ( h + 1 ) ( n + 1 ) \ge(h+1)(n+1) ≥ ( h + 1 ) ( n + 1 ) . If S i S_i S i is close to being completely upside-down, then S i S_i S i and C C C have a convex hull with area much larger than A 0 A_0 A 0 .
Each piece has a room , which is the large concave region of that piece. We say that a piece X X X is stacked inside of Y Y Y if the star point of X X X is inside of the room of Y Y Y .
Lemma 40. If the convex hull of the packing has area less than A 0 + 1 2 q n 4 A_0+\frac{1}{2}qn^4 A 0 + 2 1 q n 4 , then all of the S i S_i S i are stacked inside of C C C .
Proof. It is sufficient to consider a single piece S i S_i S i and C C C . Suppose that S i S_i S i is not stacked inside C C C . Since Lemma 39 applies, the only way for the convex hulls of S i S_i S i and C C C to overlap significantly is if C C C is stacked inside of S i S_i S i , as in Figure 30 .
Figure 30. Trying to stack S i S_i S i outside of C C C . This incurs an extra cost depending on δ 2 \delta_2 δ 2 .
We translate S i S_i S i so that the top left and right vertices of the room of S i S_i S i touch the outer walls of C C C , as in the figure. The inner walls of S i S_i S i have slopes 1 2 \frac{1}{2} 2 1 and − 1 2 -\frac{1}{2} − 2 1 , while the outer walls of C C C have slopes 1 2 ( 1 + δ 2 ) − 1 \frac{1}{2}(1+\delta_2)^{-1} 2 1 ( 1 + δ 2 ) − 1 and − 1 2 ( 1 + δ 2 ) − 1 -\frac{1}{2}(1+\delta_2)^{-1} − 2 1 ( 1 + δ 2 ) − 1 . So out of the two red triangles marked in the figure, one of them has a slope difference of at least ( 1 − ( 1 + δ 2 ) − 1 ) ≥ 1 2 δ 2 (1-(1+\delta_2)^{-1})\ge\frac{1}{2}\delta_2 ( 1 − ( 1 + δ 2 ) − 1 ) ≥ 2 1 δ 2 between the two long edges. The height of this triangle is close to ( h + 1 ) ( n + 1 ) (h+1)(n+1) ( h + 1 ) ( n + 1 ) (for simplicity, say at least 1 2 ( h + 1 ) ( n + 1 ) \frac{1}{2}(h+1)(n+1) 2 1 ( h + 1 ) ( n + 1 ) ), so it has area at least:
1 8 δ 2 ( h + 1 ) 2 ( n + 1 ) 2 ≥ 1 8 δ 2 q 2 n 4 \frac{1}{8}\delta_2(h+1)^2(n+1)^2\ge\frac{1}{8}\delta_2q^2n^4 8 1 δ 2 ( h + 1 ) 2 ( n + 1 ) 2 ≥ 8 1 δ 2 q 2 n 4
Since δ 2 ≥ 8 q \delta_2\ge\frac{8}{q} δ 2 ≥ q 8 , this is at least 1 2 q n 4 \frac{1}{2}qn^4 2 1 q n 4 , as required.
We can now show that the pieces form a stack.
Lemma 41. If the convex hull of the packing has area at most A 0 + 1 2 q n 4 A_0+\frac{1}{2}qn^4 A 0 + 2 1 q n 4 , then there is an ordering t ( 1 ) , … , t ( n ) t(1),\ldots,t(n) t ( 1 ) , … , t ( n ) of 1 , … , n 1,\ldots,n 1 , … , n such that S t ( j ) S_{t(j)} S t ( j ) is stacked inside S t ( i ) S_{t(i)} S t ( i ) for every j > i j>i j > i .
Proof. Lemmas 39 and 40 apply. We create a directed graph Λ \Lambda Λ with vertices 1 , … , n 1,\ldots,n 1 , … , n with a directed edge from i i i to j j j if S j S_j S j is stacked inside S i S_i S i . The orientations of the S i S_i S i are close to the ones shown in Figure 22 , so if S j S_j S j is stacked inside S i S_i S i then the star point of S j S_j S j must be above the star point of S i S_i S i . It follows that Λ \Lambda Λ is acyclic. To prove the claim, we just need to show that Λ \Lambda Λ is complete. Consider two pieces S i S_i S i and S j S_j S j . If neither is stacked inside the other, then the two triangles shown in Figure 31 do not overlap. Each of these triangles has area ( h + 1 ) 2 ( n + 1 ) 2 (h+1)^2(n+1)^2 ( h + 1 ) 2 ( n + 1 ) 2 . Since A 0 ≤ 3 2 q 2 n 4 A_0 \le\frac{3}{2}q^2n^4 A 0 ≤ 2 3 q 2 n 4 , this would mean that the convex hull of the packing exceeds A 0 + 1 2 q 2 n 4 A_0+\frac{1}{2}q^2n^4 A 0 + 2 1 q 2 n 4 .
Figure 31. One of S i S_i S i or S j S_j S j must be stacked in the other, otherwise the triangles shown have area larger than A 0 + 1 2 q n 2 A_0+\frac{1}{2}qn^2 A 0 + 2 1 q n 2 .
Recall that we orient the packing so that C C C has the same orientation as in Figure 24 . We set δ 1 = 1 64 n \delta_1=\frac{1}{64n} δ 1 = 64 n 1 . Consider two consecutive polygons S i , S j S_i,S_j S i , S j in the nesting order. If ( i , j ) ∈ E (i,j)\in E ( i , j ) ∈ E , the spike of S j S_j S j can enter a matching slit of S i S_i S i , allowing the two polygons to nest closely. If ( i , j ) ∉ E (i,j)\notin E ( i , j ) ∈ / E , we show that S j S_j S j must be placed substantially higher. There are two cases. If the relative rotation is small, the spike cannot penetrate deeply into a nonmatching slit because their angles are separated. If the relative rotation is larger, the long arms themselves force a large vertical separation. In either case, a missing edge incurs an additional height of Ω ( n ) \Omega(n) Ω ( n ) . We can now perform the key calculation:
Lemma 42. Suppose the conditions of Lemma 41 are satisfied. If S j S_j S j is stacked inside S i S_i S i , then the star point of S j S_j S j has height at least ( 1 − 12 q ) ( n + 1 ) \left(1-\frac{12}{q}\right)(n+1) ( 1 − q 12 ) ( n + 1 ) above the star point of S i S_i S i . If additionally there is no edge from i i i to j j j in G G G , then the star point of S j S_j S j has height at least ( 1 − 12 q ) ( n + 1 ) + 1 2 ( 1 − 36 q ) n \left(1-\frac{12}{q}\right)(n+1)+\frac{1}{2}\left(1-\frac{36}{q}\right)n ( 1 − q 12 ) ( n + 1 ) + 2 1 ( 1 − q 36 ) n above the star point of S i S_i S i .
Proof. The conditions of Lemma 39 are satisfied, so all the S i S_i S i have orientation close to the one shown in Figure 22 . If S j S_j S j is stacked inside S i S_i S i , the the lowest possible height it can have is when the spike on S j S_j S j fits exactly into one of the slits in S i S_i S i , as in Figure 25 . If S i S_i S i is oriented as in Figure 22 , then the star point of S j S_j S j has height n + 1 n+1 n + 1 above that of S i S_i S i in this case. Note that the horizontal offset between the star points of S i S_i S i and S j S_j S j is at most the vertical offset (so at most n + 1 n+1 n + 1 here). Since S i S_i S i can be rotated by θ ≤ 6 q \theta\le\frac{6}{q} θ ≤ q 6 compared to the orientation in Figure 22 , the star point of S j S_j S j has height at least ( cos ( θ ) − sin ( θ ) ) ( n + 1 ) ≥ ( 1 − 12 q ) ( n + 1 ) (\cos(\theta)-\sin(\theta))(n+1)\ge\left(1-\frac{12}{q}\right)(n+1) ( cos ( θ ) − sin ( θ )) ( n + 1 ) ≥ ( 1 − q 12 ) ( n + 1 ) above that of S i S_i S i (note q ≥ 4000 q\ge4000 q ≥ 4000 ).
This type of stacking only exists when there is an edge from i i i to j j j in G G G . So suppose that there is no such edge. The difference in angle between edges of different possible slits in an S i S_i S i is at least:
arctan ( n − 1 2 δ 1 n + 1 ) − arctan ( n − 1 + 1 2 δ 1 n + 1 ) \arctan\left(\frac{n-\frac{1}{2}\delta_1}{n+1}\right)-\arctan\left(\frac{n-1+\frac{1}{2}\delta_1}{n+1}\right) arctan ( n + 1 n − 2 1 δ 1 ) − arctan ( n + 1 n − 1 + 2 1 δ 1 )
which is at least 1 4 ⋅ 1 − δ 2 n + 1 ≥ 1 8 n \frac{1}{4}\cdot\frac{1-\delta_2}{n+1}\ge\frac{1}{8n} 4 1 ⋅ n + 1 1 − δ 2 ≥ 8 n 1 . First, suppose that the orientations of S i S_i S i and S j S_j S j differ by an angle less than 1 16 n \frac{1}{16n} 16 n 1 . Since there is no edge from i i i to j j j , there is no slit in S i S_i S i that corresponds to the spike on S j S_j S j , and the walls of spike on S j S_j S j differ in angle from the walls of any slit in S i S_i S i by an angle of at least 1 16 n \frac{1}{16n} 16 n 1 . If we orient S i S_i S i as in Figure 22 , then the spike in S j S_j S j sticks into a slit in S i S_i S i by a vertical distance of at most 2 δ 1 sin ( 1 16 n ) \frac{2\delta_1}{\sin\left(\frac{1}{16n}\right)} s i n ( 16 n 1 ) 2 δ 1 , as illustrated in Figure 32 . Since n ≥ 100 n\ge100 n ≥ 100 , we have sin ( 1 16 n ) ≥ 1 32 n \sin\left(\frac{1}{16n}\right)\ge\frac{1}{32n} sin ( 16 n 1 ) ≥ 32 n 1 , so this is at most 64 δ 1 n = 1 64\delta_1n=1 64 δ 1 n = 1 .
Figure 32. If S i S_i S i and S j S_j S j differ in angle by ≤ 1 16 n \leq\frac{1}{16n} ≤ 16 n 1 , then the spike in S j S_j S j can’t go far into a non-matching slit in S i S_i S i .
So the star point of S j S_j S j has a height of ( n + 1 ) + 1 2 n ( cos ( ϕ ) − sin ( ϕ ) ) (n+1)+\frac{1}{2}n(\cos(\phi)-\sin(\phi)) ( n + 1 ) + 2 1 n ( cos ( ϕ ) − sin ( ϕ )) above that of S i S_i S i , where ϕ ≤ 12 q \phi\le\frac{12}{q} ϕ ≤ q 12 is the angle between the orientations of S i S_i S i and S j S_j S j . So this is at least ( n + 1 ) + 1 2 ( 1 − 24 q ) n (n+1)+\frac{1}{2}\left(1-\frac{24}{q}\right)n ( n + 1 ) + 2 1 ( 1 − q 24 ) n .
We changed the orientation of S i S_i S i by at most 6 q \frac{6}{q} q 6 here, so we need to change it back, and we get a height difference of at least ( 1 − 12 q ) ( n + 1 ) + 1 2 ( 1 − 36 q ) n \left(1-\frac{12}{q}\right)(n+1)+\frac{1}{2}\left(1-\frac{36}{q}\right)n ( 1 − q 12 ) ( n + 1 ) + 2 1 ( 1 − q 36 ) n .
Now consider the case that the orientation of S j S_j S j differs from that of S i S_i S i by more than 1 16 n \frac{1}{16n} 16 n 1 . Again, we orient S i S_i S i and S j S_j S j so that it is as in Figure 22 . In this case, the star point of S j S_j S j is at least sin ( 1 16 n ) ( h + 1 ) ( n + 1 ) \sin\left(\frac{1}{16n}\right)(h+1)(n+1) sin ( 16 n 1 ) ( h + 1 ) ( n + 1 ) above the star point of S i S_i S i , as illustrated in Figure 33 . Since ( h + 1 ) ≥ 4000 n (h+1)\ge4000n ( h + 1 ) ≥ 4000 n , this is at least 250 ( n + 1 ) 250(n+1) 250 ( n + 1 ) . Even after orienting S i S_i S i back to its original orientation, this is much larger than the bound claim by the lemma.
Figure 33. If S j S_j S j is rotated by more than 1 16 n \frac{1}{16n} 16 n 1 compared to S i S_i S i , then its star point must be above the red line shown in the figure.
We can now prove that constant complexity star packing is APX-hard:
Theorem 43. For some ϵ > 0 \epsilon>0 ϵ > 0 , it is N P NP N P -hard to approximate the star packing to within a ( 1 + ϵ ) (1+\epsilon) ( 1 + ϵ ) factor, even if the stars are polygons with at most 17 vertices.
Proof. Let ϵ = 1 1396641 \epsilon= \frac{1}{1396641} ϵ = 1396641 1 be a constant small enough for Lemma 37 to apply. We reduce from a MAX-VERTEX-DISJOINT-PATH-COVER instance G = ( V , E ) G = (V,E) G = ( V , E ) , with ∣ V ∣ = n |V| = n ∣ V ∣ = n , produced by Lemma 37 . The construction is as above, with q = 1000 ϵ q = \frac{1000}{\epsilon} q = ϵ 1000 . If G G G has a Hamiltonian path, then Lemma 38 shows that we can pack the pieces in a convex container of area A 0 A_0 A 0 , where A 0 A_0 A 0 is the area of C C C and satisfies
q 2 n 4 ≤ A 0 ≤ 5 2 q 2 n 4 q^2n^4 \leq A_0 \leq\frac{5}{2}q^2n^4 q 2 n 4 ≤ A 0 ≤ 2 5 q 2 n 4
Write α = 1 q = 1 1000 ϵ \alpha= \frac{1}{q} = \frac{1}{1000}\epsilon α = q 1 = 1000 1 ϵ . Write β = α q \beta= \frac{\alpha}{q} β = q α . We suppose that n n n is large enough that 1 n ≤ 1 100 ϵ \frac{1}{n} \leq\frac{1}{100}\epsilon n 1 ≤ 100 1 ϵ .
Suppose now that there exists a packing with convex hull of area at most ( 1 + 2 3 β ) A 0 ≤ A 0 + α q n 4 (1 + \frac{2}{3}\beta)A_0 \leq A_0 + \alpha q n^4 ( 1 + 3 2 β ) A 0 ≤ A 0 + α q n 4 . Since α ≤ 1 2 \alpha\leq\frac{1}{2} α ≤ 2 1 , Lemma 41 applies, and there is an ordering t ( 1 ) , … , t ( n ) t(1), \ldots, t(n) t ( 1 ) , … , t ( n ) of 1 , … , n 1, \ldots, n 1 , … , n such that S t ( i + 1 ) S_{t(i+1)} S t ( i + 1 ) is stacked in S t ( i ) S_{t(i)} S t ( i ) for each i = 1 , … , n − 1 i = 1, \ldots, n - 1 i = 1 , … , n − 1 . We construct a path cover of G G G as follows: for each i = 1 , … , n − 1 i = 1, \ldots, n - 1 i = 1 , … , n − 1 , we add the edge from t ( i ) t(i) t ( i ) to t ( i + 1 ) t(i + 1) t ( i + 1 ) to the cover if it exists. This gives a set of disjoint paths in G G G . For any vertex not covered, we add the zero-length path containing only that vertex. Let m m m be the number of edges in this disjoint path cover.
By applying Lemma 42 to each pair S t ( i ) S_{t(i)} S t ( i ) and S t ( i + 1 ) S_{t(i+1)} S t ( i + 1 ) and summing, the difference in height between the star point of S t ( 1 ) S_{t(1)} S t ( 1 ) and the star point of S t ( n ) S_{t(n)} S t ( n ) is at least ( 1 − 36 q ) ( ( n − 1 ) ( n + 1 ) + 1 2 ( n − 1 − m ) n ) (1 - \frac{36}{q})((n - 1)(n + 1) + \frac{1}{2}(n - 1 - m)n) ( 1 − q 36 ) (( n − 1 ) ( n + 1 ) + 2 1 ( n − 1 − m ) n ) . So the difference in height between the star point of S t ( 1 ) S_{t(1)} S t ( 1 ) and a point on the top opening of S t ( n ) S_{t(n)} S t ( n ) is at least ( 1 − 36 q ) ( ( n − 1 ) ( n + 1 ) + 1 2 ( n − m ) n ) + ( h + 1 ) ( n + 1 ) (1 - \frac{36}{q})((n - 1)(n + 1) + \frac{1}{2}(n - m)n) + (h + 1)(n + 1) ( 1 − q 36 ) (( n − 1 ) ( n + 1 ) + 2 1 ( n − m ) n ) + ( h + 1 ) ( n + 1 ) . The height difference between a point on the top of S t ( n ) S_{t(n)} S t ( n ) and the star point in S t ( n ) S_{t(n)} S t ( n ) is at least ( h + 1 ) ( n + 1 ) (h + 1)(n + 1) ( h + 1 ) ( n + 1 ) , even if S t ( n ) S_{t(n)} S t ( n ) is rotated slightly (see Lemma 39 ).
The height of C C C is ( h + n + 1 ) ( n + 1 ) (h + n + 1)(n + 1) ( h + n + 1 ) ( n + 1 ) . So some S i S_i S i sticks out above the top of C C C by at least:
( 1 − 36 q ) ( ( n − 1 ) ( n + 1 ) + 1 2 ( n − 1 − m ) n ) − n ( n + 1 ) \left(1 - \frac{36}{q}\right)((n - 1)(n + 1) + \frac{1}{2}(n - 1 - m)n) - n(n + 1) ( 1 − q 36 ) (( n − 1 ) ( n + 1 ) + 2 1 ( n − 1 − m ) n ) − n ( n + 1 )
If there is a point in some S i S_i S i a distance of κ \kappa κ above the top of C C C , then the convex hull of the packing has area at least A 0 + ( h + 1 ) ( n + 1 ) κ A_0 + (h + 1)(n + 1)\kappa A 0 + ( h + 1 ) ( n + 1 ) κ . Since we know the area is at most A 0 + α q n 4 A_0 + \alpha q n^4 A 0 + α q n 4 , we have κ ≤ α n 2 \kappa\leq\alpha n^2 κ ≤ α n 2 . So:
1 2 ( 1 − 36 q ) ( n − 1 − m ) n − 36 q ( n − 1 ) ( n + 1 ) − 2 ( n + 1 ) ≤ α n 2 \frac{1}{2}\left(1 - \frac{36}{q}\right)(n - 1 - m)n - \frac{36}{q}(n - 1)(n + 1) - 2(n + 1) \leq\alpha n^2 2 1 ( 1 − q 36 ) ( n − 1 − m ) n − q 36 ( n − 1 ) ( n + 1 ) − 2 ( n + 1 ) ≤ α n 2
1 2 ( n − 1 − m ) n − 54 q ( n − 1 ) ( n + 1 ) − 2 ( n + 1 ) ≤ α n 2 \frac{1}{2}(n - 1 - m)n - \frac{54}{q}(n - 1)(n + 1) - 2(n + 1) \leq\alpha n^2 2 1 ( n − 1 − m ) n − q 54 ( n − 1 ) ( n + 1 ) − 2 ( n + 1 ) ≤ α n 2
1 2 n − 1 − m n − 1 − 54 q − 2 n ≤ 2 α \frac{1}{2}\frac{n - 1 - m}{n - 1} - \frac{54}{q} - \frac{2}{n} \leq2\alpha 2 1 n − 1 n − 1 − m − q 54 − n 2 ≤ 2 α
For the last step, note that we are assuming n n n is large.
If G G G does not have a Hamiltonian path, then Lemma 37 says that the best path of G G G cover has at most ( 1 − ϵ ) ( n − 1 ) (1 - \epsilon)(n - 1) ( 1 − ϵ ) ( n − 1 ) edges. In this case, n − 1 − m ≥ ϵ ( n − 1 ) n - 1 - m \geq\epsilon(n - 1) n − 1 − m ≥ ϵ ( n − 1 ) , so:
1 2 ⋅ n − 1 − m n − 1 − 54 q − 2 n ≥ 1 2 ϵ − 1 10 ϵ − 1 10 ϵ > 2 α \frac{1}{2}\cdot\frac{n - 1 - m}{n - 1} - \frac{54}{q} - \frac{2}{n} \geq\frac{1}{2}\epsilon- \frac{1}{10}\epsilon- \frac{1}{10}\epsilon> 2\alpha 2 1 ⋅ n − 1 n − 1 − m − q 54 − n 2 ≥ 2 1 ϵ − 10 1 ϵ − 10 1 ϵ > 2 α
By the above, this is incompatible with the area of the convex hull being smaller than ( 1 + 2 3 β ) A 0 (1 + \frac{2}{3}\beta)A_0 ( 1 + 3 2 β ) A 0 . So if the area of the convex container is at most ( 1 + 2 3 β ) A 0 (1 + \frac{2}{3}\beta)A_0 ( 1 + 3 2 β ) A 0 , then we can conclude that there exists a Hamiltonian path. So it is NP hard to approximate star packing to within a factor of 1 + 2 3 β 1 + \frac{2}{3}\beta 1 + 3 2 β . Since β = α q = 1 q 2 = 1 10 6 ϵ 2 \beta= \frac{\alpha}{q} = \frac{1}{q^2} = \frac{1}{10^6}\epsilon^2 β = q α = q 2 1 = 1 0 6 1 ϵ 2 does not depend on n n n , this establishes the claim.
AI Methodology
ChatGPT was used to obtain some of the crucial ideas. The model suggested the argument with two test lines in the proof of Theorem 10 , but in the context of packing wedges, i.e., degenerate weakly simple polygons that are the union of two line segments sharing an endpoint. The authors managed to generalize the argument to arbitrary star-shaped polygons and use it to design an O ( log 2 n ) O(\log^2 n) O ( log 2 n ) -approximation algorithm for stars. The model also suggested a version of the argument that our algorithm gives an O ( log n ) O(\log n) O ( log n ) -approximation rather than an O ( log 2 n ) O(\log^2 n) O ( log 2 n ) -approximation, even though we have Θ ( log 2 n ) \Theta(\log^2 n) Θ ( log 2 n ) dyadic size scale combinations of r r r , w w w (Corollary 25). Finally, the model suggested the argument for the rotational algorithm and suggested to obtain APX-hardness by reducing from MAX-DISJOINT-PATH-COVER, but the actual reduction was found by the authors. All ideas from the model have been carefully studied, adjusted and rewritten by the authors. ChatGPT and Claude have also been used as writing aids.
Acknowledgments
M. Abrahamsen, J. Conradi, J. Stade, and H. Zhang are supported by the Independent Research Fund Denmark, grant 1054-00032B, and by the Carlsberg Foundation, grant CF24-1929. A. Khan is partly supported by Google India Research Award, Ittiam Systems CSR grant, the Walmart Center for Tech Excellence at IISc (CSR Grant WMGT-23-0001), and SERB Core Research Grant (CRG/2022/001176) on “Optimization under Intractability and Uncertainty”. S. Wong is supported by the European Union’s Marie Skłodowska-Curie Actions Postdoctoral Fellowship, grant number 101146276. S. Yan is supported by VILLUM Foundation Grant 54451, Basic Algorithms Research Copenhagen (BARC).
Proof of cor:bin-strip
Proof of Corollary 2. Let M \mathcal{M} M be the set of mini-containers computed by Lemma 26 (or Lemma 36 in the rotational case), and let O P T b i n \mathrm{OPT}_{\mathrm{bin}} OPT bin and O P T s t r i p \mathrm{OPT}_{\mathrm{strip}} OPT strip denote the optimum of the bin and strip packing instance, respectively. Recall that plain O P T \mathrm{OPT} OPT is the area of the smallest convex container. We assume that the strip is vertical, i.e., the strip is [ 0 , 1 ] × [ 0 , ∞ ) [0,1] \times[0,\infty) [ 0 , 1 ] × [ 0 , ∞ ) and its length is measured in the y y y -direction. The bins of an optimal bin packing, placed side by side, form a rectangle of area O P T b i n \mathrm{OPT}_{\mathrm{bin}} OPT bin , and the used part of the strip in an optimal strip packing is a rectangle of area O P T s t r i p \mathrm{OPT}_{\mathrm{strip}} OPT strip . Hence O P T ≤ min { O P T b i n , O P T s t r i p } \mathrm{OPT} \le\min\{\mathrm{OPT}_{\mathrm{bin}}, \mathrm{OPT}_{\mathrm{strip}}\} OPT ≤ min { OPT bin , OPT strip } . By Lemma 26 (or Lemma 36 in the rotational case), the total area of M \mathcal{M} M is O ( log n ) ⋅ O P T O(\log n) \cdot\mathrm{OPT} O ( log n ) ⋅ OPT , and thus at most O ( log n ) ⋅ O P T b i n O(\log n) \cdot\mathrm{OPT}_{\mathrm{bin}} O ( log n ) ⋅ OPT bin and O ( log n ) ⋅ O P T s t r i p O(\log n) \cdot\mathrm{OPT}_{\mathrm{strip}} O ( log n ) ⋅ OPT strip .
In the rotational setting, we first rotate each mini-container so that its minimum width is attained in the vertical direction. Let ℓ max \ell_{\max} ℓ m a x and h max h_{\max} h m a x be the maximum horizontal and vertical spans of the mini-containers. Since O P T s t r i p \mathrm{OPT}_{\mathrm{strip}} OPT strip is at least the vertical span of any star (in the rotational setting, its minimum width), (16) gives h max = O ( O P T s t r i p ) h_{\max} = O(\mathrm{OPT}_{\mathrm{strip}}) h m a x = O ( OPT strip ) . Moreover, every mini-container has diameter O ( δ ) O(\delta) O ( δ ) , and we choose δ \delta δ such that ℓ max , h max ≤ 1 4 \ell_{\max}, h_{\max} \le\frac{1}{4} ℓ m a x , h m a x ≤ 4 1 .
We apply Theorem 5 to M \mathcal{M} M and obtain an axis-aligned rectangle R R R of area O ( log n ) ⋅ O P T + O ( ℓ max h max ) O(\log n) \cdot\mathrm{OPT} + O(\ell_{\max}h_{\max}) O ( log n ) ⋅ OPT + O ( ℓ m a x h m a x ) . Since ℓ max ≤ 1 \ell_{\max} \le1 ℓ m a x ≤ 1 and h max = O ( O P T s t r i p ) h_{\max} = O(\mathrm{OPT}_{\mathrm{strip}}) h m a x = O ( OPT strip ) , we have ∣ R ∣ = O ( log n ) ⋅ O P T s t r i p |R| = O(\log n) \cdot\mathrm{OPT}_{\mathrm{strip}} ∣ R ∣ = O ( log n ) ⋅ OPT strip , and since ℓ max h max ≤ 1 ≤ O P T b i n \ell_{\max}h_{\max} \le1 \le\mathrm{OPT}_{\mathrm{bin}} ℓ m a x h m a x ≤ 1 ≤ OPT bin , we have ∣ R ∣ = O ( log n ) ⋅ O P T b i n |R| = O(\log n) \cdot\mathrm{OPT}_{\mathrm{bin}} ∣ R ∣ = O ( log n ) ⋅ OPT bin . It remains to cut R R R into pieces that fit into the strip or the bins.
Let us first consider strip packing. Let R R R be an a × b a \times b a × b rectangle, and note that ℓ max ≤ a \ell_{\max} \le a ℓ m a x ≤ a and h max ≤ b h_{\max} \le b h m a x ≤ b . If a ≥ 1 2 a \ge\frac{1}{2} a ≥ 2 1 , we cut R R R by vertical lines into ⌈ 2 a ⌉ ≤ 4 a \lceil2a\rceil\le4a ⌈ 2 a ⌉ ≤ 4 a pieces of width at most 1 2 \frac{1}{2} 2 1 and height b b b . If a < 1 2 a < \frac{1}{2} a < 2 1 , we cut R R R by horizontal lines into ⌈ b / h max ⌉ \lceil b/h_{\max}\rceil ⌈ b / h m a x ⌉ pieces of width a a a and height at most h max h_{\max} h m a x . We assign each mini-container to the piece that contains the lower left corner of its axis-aligned bounding box. Then the mini-containers assigned to a piece lie in that piece extended by ℓ max \ell_{\max} ℓ m a x to the right and by h max h_{\max} h m a x upwards.
In the first case (a ≥ 1 2 a \ge\frac{1}{2} a ≥ 2 1 ), each extended piece has width at most 1 2 + ℓ max < 1 \frac{1}{2} + \ell_{\max} < 1 2 1 + ℓ m a x < 1 and height at most b + h max ≤ 2 b b + h_{\max} \le2b b + h m a x ≤ 2 b . We place the extended pieces on top of each other, which gives length at most 4 a ⋅ 2 b = 8 a b = O ( ∣ R ∣ ) 4a \cdot2b = 8ab = O(|R|) 4 a ⋅ 2 b = 8 ab = O ( ∣ R ∣ ) .
In the second case (a < 1 2 a < \frac{1}{2} a < 2 1 ), each extended piece has width at most a + ℓ max ≤ 2 a < 1 a + \ell_{\max} \le2a < 1 a + ℓ m a x ≤ 2 a < 1 and height at most 2 h max 2h_{\max} 2 h m a x . We place the extended pieces in rows, with ⌊ 1 / ( 2 a ) ⌋ ≥ 1 / ( 4 a ) \lfloor1/(2a)\rfloor\ge1/(4a) ⌊ 1/ ( 2 a )⌋ ≥ 1/ ( 4 a ) pieces side by side in each row. The number of rows is at most 4 a ⌈ b / h max ⌉ + 1 ≤ 4 a b / h max + 4 a / h max + 1 ≤ 4 a b / h max + 4 a / h max + 2 4a\lceil b/h_{\max}\rceil+ 1 \le4ab/h_{\max} + 4a/h_{\max} + 1 \le4ab/h_{\max} + 4a/h_{\max} + 2 4 a ⌈ b / h m a x ⌉ + 1 ≤ 4 ab / h m a x + 4 a / h m a x + 1 ≤ 4 ab / h m a x + 4 a / h m a x + 2 . Since each row has height at most 2 h max 2h_{\max} 2 h m a x , this gives length at most 8 a b + 6 h max = O ( ∣ R ∣ + h max ) 8ab + 6h_{\max} = O(|R| + h_{\max}) 8 ab + 6 h m a x = O ( ∣ R ∣ + h m a x ) .
In both cases, the length is O ( log n ) ⋅ O P T s t r i p O(\log n) \cdot\mathrm{OPT}_{\mathrm{strip}} O ( log n ) ⋅ OPT strip , since ∣ R ∣ = O ( log n ) ⋅ O P T s t r i p |R| = O(\log n) \cdot\mathrm{OPT}_{\mathrm{strip}} ∣ R ∣ = O ( log n ) ⋅ OPT strip and h max = O ( O P T s t r i p ) h_{\max} = O(\mathrm{OPT}_{\mathrm{strip}}) h m a x = O ( OPT strip ) .
For bin packing, we first construct a strip packing of length L = O ( ∣ R ∣ + h max ) = O ( ∣ R ∣ + 1 ) L = O(|R| + h_{\max}) = O(|R| + 1) L = O ( ∣ R ∣ + h m a x ) = O ( ∣ R ∣ + 1 ) as above. We cut the strip by horizontal lines at distance 1 2 \frac{1}{2} 2 1 and assign each mini-container to the part containing the lower left corner of its bounding box. The mini-containers assigned to a part lie in a rectangle of width 1 1 1 and height at most 1 2 + h max < 1 \frac{1}{2} + h_{\max} < 1 2 1 + h m a x < 1 , which fits into a bin. This gives at most 2 L + 1 = O ( ∣ R ∣ + 1 ) = O ( log n ) ⋅ O P T b i n 2L + 1 = O(|R| + 1) = O(\log n) \cdot\mathrm{OPT}_{\mathrm{bin}} 2 L + 1 = O ( ∣ R ∣ + 1 ) = O ( log n ) ⋅ OPT bin bins, since O P T b i n ≥ 1 \mathrm{OPT}_{\mathrm{bin}} \ge1 OPT bin ≥ 1 .
Proof of thm:general-macc-to-bin
Recall the statement of this theorem.
Theorem 3. For some constants ε , δ ∈ ( 0 , 1 ) \varepsilon,\delta\in(0,1) ε , δ ∈ ( 0 , 1 ) , if there exists a polynomial-time α \alpha α -approximation translational bin packing algorithm for polygons of diameter at most ε \varepsilon ε and convex hull area at least δ ε 2 \delta\varepsilon^2 δ ε 2 , then there exists a polynomial-time O ( α log n ) O(\alpha\log n) O ( α log n ) -approximation algorithm for translational packing of n n n polygons into a minimum-area convex container.
Proof. The proof mostly follows the structure of § 3 . Most of the arguments follow directly from the case of stars, and we will omit repeated details and focus only on necessary modifications for general polygons.
As we did for stars, we divide the input polygons into size classes and then fine types, show that packing each fine type separately will only incur an O ( log n ) O(\log n) O ( log n ) extra factor in the approximation ratio. The mini-packing within each fine type can be simply reduced to a bin-packing problem by an affine transformation. Let P \mathcal{P} P be the set of polygons to be packed.
Parameterize general polygons. Let P P P be an arbitrary polygon. We define a P , b P a_P,b_P a P , b P to be the farthest pair of points in P P P , measured in Euclidean distance. Let c P c_P c P be the farthest point from line a P b P ‾ \overline{a_Pb_P} a P b P in P P P , measured in Euclidean distance as well. If there are multiple candidates for a P , b P a_P,b_P a P , b P and c P c_P c P , we choose the triple that maximizes the lexicographical order of vector ⟨ x ( a P ) , y ( a P ) , x ( b P ) , y ( b P ) , x ( c P ) , y ( c P ) ⟩ \langle x(a_P),y(a_P),x(b_P),y(b_P),x(c_P),y(c_P)\rangle ⟨ x ( a P ) , y ( a P ) , x ( b P ) , y ( b P ) , x ( c P ) , y ( c P )⟩ . Note that segment a P b P ‾ \overline{a_Pb_P} a P b P may not be inside P P P , which is different from the case of radii q Q R Q q_QR_Q q Q R Q for star Q Q Q . We define
Δ P = ∥ a P b P ∥ , w P = dist ( c P , a P b P ‾ ) . \Delta_P=\lVert a_Pb_P\rVert,\qquad w_P=\operatorname{dist}(c_P,\overline{a_Pb_P}). Δ P = ∥ a P b P ∥ , w P = dist ( c P , a P b P ) .
Similar to the use of triangle q Q L Q R Q q_QL_QR_Q q Q L Q R Q for star Q Q Q , triangle a P b P c P a_Pb_Pc_P a P b P c P is also an “approximation” of Conv ( P ) \operatorname{Conv}(P) Conv ( P ) , where Conv ( P ) \operatorname{Conv}(P) Conv ( P ) is the convex hull of set P P P .
Fact 44. Any polygon P P P lies in a rectangle of size Δ P × ( 2 w P ) \Delta_P \times(2w_P) Δ P × ( 2 w P ) .
To obtain the O ( α log n ) O(\alpha\log n) O ( α log n ) -approximation algorithm, we use the same strategy as packing stars. Let Δ max = max P ∈ P Δ P \Delta_{\max}=\max_{P\in\mathcal{P}}\Delta_P Δ m a x = max P ∈ P Δ P and w max = max P ∈ P w P w_{\max}=\max_{P\in\mathcal{P}}w_P w m a x = max P ∈ P w P . Similar to stars, we partition P \mathcal{P} P into dyadic size groups G a , b \mathcal{G}_{a,b} G a , b of scales Δ , w \Delta,w Δ , w that contains all polygons P P P with
Δ P ∈ ( r / 2 , r ] , w P ∈ ( w / 2 , w ] , Δ = Δ max 2 a , w = w max 2 b . \Delta_P\in(r/2,r],\qquad w_P\in(w/2,w],\qquad\Delta=\frac{\Delta_{\max}}{2^a},\qquad w=\frac{w_{\max}}{2^b}. Δ P ∈ ( r /2 , r ] , w P ∈ ( w /2 , w ] , Δ = 2 a Δ m a x , w = 2 b w m a x .
In each size group G a , b \mathcal{G}_{a,b} G a , b , we partition polygons into fine types based on the orientation of the diameter a P b P → \overrightarrow{a_Pb_P} a P b P , where the angular difference in each fine type is at most π w 50 Δ \frac{\pi w}{50\Delta} 50Δ π w . This definition is the same as stars when we replace the role of radii by diameter. For each fine type τ \tau τ , we define d ⃗ τ \vec{d}_{\tau} d τ and u ⃗ τ \vec{u}_{\tau} u τ similarly as we did for stars.
Next, we show a similar structural packing lemma for general polygons.
Lemma 45 (Similar to Theorem 10 ). Let P P P be a set of polygons in one size group with scales Δ , w \Delta,w Δ , w , and let Π \Pi Π be a packing of P P P in a convex container C C C . For any 0 < c < 0.1 0<c<0.1 0 < c < 0.1 and sufficiently small ε > 0 \varepsilon>0 ε > 0 , there exists a partition
P = P 1 ∪ ˙ ⋯ ∪ ˙ P t , \mathcal{P}=\mathcal{P}_1\dot{\cup}\cdots\dot{\cup}\mathcal{P}_t, P = P 1 ∪ ˙ ⋯ ∪ ˙ P t , such that each P j \mathcal{P}_j P j only contains stars of one fine type τ j \tau_j τ j and P j \mathcal{P}_j P j fits into a rectangle of dimensions O ( Δ ) × O ( w ) O(\Delta)\times O(w) O ( Δ ) × O ( w ) aligned with u ⃗ τ \vec{u}_{\tau} u τ and d ⃗ τ \vec{d}_{\tau} d τ .
Proof. The proof follows the test line argument in the proof of Theorem 10 . Let T T T be the enclosing vertical parallelogram of C C C . Treat a P b P a_Pb_P a P b P to be the “radii” of P P P , we can use the same way to partition T T T into vertical strips and take the same set of test lines for each of the vertical strip. See Figure 4 . The only part that does not hold is the counting bound on the number of occupied pairs for each vertical strip.
Let ( a , b ) (a,b) ( a , b ) be an occupied pair that all polygons in it intersects interval s 1 , a s_{1,a} s 1 , a on ℓ 1 : x = x 0 + c Δ \ell_1:x=x_0+c\Delta ℓ 1 : x = x 0 + c Δ and interval s 2 , b s_{2,b} s 2 , b on ℓ 2 : x = x 0 + 2 c Δ \ell_2:x=x_0+2c\Delta ℓ 2 : x = x 0 + 2 c Δ . For each fine type τ \tau τ and all polygons P P P in this occupied pair ( a , b ) (a,b) ( a , b ) that falls into this fine type, there is a bounding box R R R of dimensions ( K ′ Δ ) × ( K ′ w ) (K'\Delta)\times(K'w) ( K ′ Δ ) × ( K ′ w ) for some universal constant. We also know that R R R and its short side is along d ⃗ τ \vec{d}_{\tau} d τ , which is at most 2 degree away from vertical. Let s 1 , a ′ = R ∩ ℓ 1 s'_{1,a}=R\cap\ell_1 s 1 , a ′ = R ∩ ℓ 1 and s 2 , b ′ = R ∩ ℓ 2 s'_{2,b}=R\cap\ell_2 s 2 , b ′ = R ∩ ℓ 2 . We know both s 1 , a ′ s'_{1,a} s 1 , a ′ and s 2 , a ′ s'_{2,a} s 2 , a ′ has length at most K ′ w cos 2 ∘ ≤ 1.01 K ′ w \frac{K'w}{\cos2^\circ}\leq1.01K'w c o s 2 ∘ K ′ w ≤ 1.01 K ′ w . So s 1 , a ′ s'_{1,a} s 1 , a ′ and s 2 , b ′ s'_{2,b} s 2 , b ′ touches at most A = Θ K ′ , ε ( 1 ) A=\Theta_{K',\varepsilon}(1) A = Θ K ′ , ε ( 1 ) intervals on ℓ 1 \ell_1 ℓ 1 and ℓ 2 \ell_2 ℓ 2 separately.
Let P P P be some polygon packed in R R R . Since a P b P a_Pb_P a P b P crosses both ℓ 1 \ell_1 ℓ 1 and ℓ 2 \ell_2 ℓ 2 , without loss of generality, assume a P a_P a P lies to the left of ℓ 1 \ell_1 ℓ 1 and b P b_P b P lies to the right of ℓ 2 \ell_2 ℓ 2 . Then there must be a path π \pi π in P P P that connects a P a_P a P and b P b_P b P . Therefore, there must be a subpath π a , b ′ ⊆ π \pi'_{a,b}\subseteq\pi π a , b ′ ⊆ π in P P P connecting s 1 , a ′ s'_{1,a} s 1 , a ′ and s 2 , b ′ s'_{2,b} s 2 , b ′ between ℓ 1 \ell_1 ℓ 1 and ℓ 2 \ell_2 ℓ 2 . We will call this subpath π a , b ′ \pi'_{a,b} π a , b ′ the induced subpath of occupied group ( a , b ) (a,b) ( a , b ) .
These subpaths have to be crossing free due to the feasibility of this packing. Therefore, for any a 1 ≤ a 2 − 2 A a_1\leq a_2-2A a 1 ≤ a 2 − 2 A and b 1 ≥ b 2 + 2 A b_1\geq b_2+2A b 1 ≥ b 2 + 2 A , ( a 1 , b 1 ) (a_1,b_1) ( a 1 , b 1 ) and ( a 2 , b 2 ) (a_2,b_2) ( a 2 , b 2 ) cannot be both occupied, because otherwise their induced subpath must cross. This suggest that the number of occupied pairs is O ( m ) O(m) O ( m ) .
Combined with all other parts, this lemma holds.
This part of packing into mini-containers can be rephrased into a bin packing problem. For each fine type τ \tau τ , let f τ f_\tau f τ be a linear transformation defined by f ( K Δ u ⃗ τ ) = ( 0 , 1 ) f(K\Delta\vec{u}_\tau)=(0,1) f ( K Δ u τ ) = ( 0 , 1 ) and f ( K w d ⃗ τ ) = ( 1 , 0 ) f(Kw\vec{d}_\tau)=(1,0) f ( K w d τ ) = ( 1 , 0 ) . Let P τ \mathcal{P}_\tau P τ be the set of polygons in fine type τ \tau τ . The algorithmic problem for packing P τ \mathcal{P}_\tau P τ into rectangles of dimensions ( K Δ ) × ( K w ) (K\Delta)\times(Kw) ( K Δ ) × ( K w ) , is equivalent to packing f ( P τ ) f(\mathcal{P}_\tau) f ( P τ ) into minimum number of unit axis-aligned squares. Each polygon after this linear transformation has diameter at most 4 K \frac{4}{K} K 4 and convex hull area at least 1 8 K 2 \frac{1}{8K^2} 8 K 2 1 . Therefore, we can apply the assumed algorithm to obtain an α \alpha α -approximation in polynomial time.
Then we need to generalize the O ( log n ) O(\log n) O ( log n ) analysis of the total optimum size across all size groups.
Lemma 46 (Similar to Corollary 25). For any set of polygons P \mathcal{P} P ,
∑ G : s i z e g r o u p OPT ( G ) = O ( log n ) ⋅ OPT ( P ) . \sum_{G:\ \mathit{size\ group}} \operatorname{OPT}(G)=O(\log n)\cdot\operatorname{OPT}(\mathcal{P}). G : size group ∑ OPT ( G ) = O ( log n ) ⋅ OPT ( P ) .
Proof. This proof follows the structure of § 3.6 . For each polygon P P P , let T P T_P T P be the triangle a P b P c P a_Pb_Pc_P a P b P c P . We define the core of P P P in the same way as we did for stars, where replacing the role of q , L , R q,L,R q , L , R by a , c , b a,c,b a , c , b respectively. Let e ⃗ P \vec{e}_P e P be the unit vector from a P a_P a P to b P b_P b P , v ⃗ P \vec{v}_P v P be the unit vector perpendicular to e ⃗ P \vec{e}_P e P and pointing towards c P c_P c P . Then the core K P K_P K P of P P P is the triangle a P ′ b P ′ c P ′ a'_Pb'_Pc'_P a P ′ b P ′ c P ′ that
a P ′ = ( a P + b P ) / 2 + w P e ⃗ P / 10 , b P ′ = a P ′ + ( b P − a P ) / 10 , c P ′ = a P ′ + ( c P − a P ) / 10. a'_P=(a_P+b_P)/2+w_P\vec{e}_P/10,\qquad b'_P=a'_P+(b_P-a_P)/10,\qquad c'_P=a'_P+(c_P-a_P)/10. a P ′ = ( a P + b P ) /2 + w P e P /10 , b P ′ = a P ′ + ( b P − a P ) /10 , c P ′ = a P ′ + ( c P − a P ) /10.
Similarly, K P ⊂ T P K_P\subset T_P K P ⊂ T P and any point p ∈ K P p\in K_P p ∈ K P is at least w P / 20 w_P/20 w P /20 away from ∂ T P \partial T_P ∂ T P .
First, we show that the cores are disjoint for polygons from some different size groups.
Lemma 47 (Similar to Lemma 22 ). For any two polygons P 1 P_1 P 1 and P 2 P_2 P 2 , if Δ P 1 > 10 Δ P 2 \Delta_{P_1}>10\Delta_{P_2} Δ P 1 > 10 Δ P 2 and w P 2 > 40 w P 2 w_{P_2}>40w_{P_2} w P 2 > 40 w P 2 , then K P 1 ∩ K P 2 = ∅ K_{P_1}\cap K_{P_2}=\varnothing K P 1 ∩ K P 2 = ∅ .
Proof. By contradiction, assume p ∈ K P 1 ∩ K P 2 p\in K_{P_1}\cap K_{P_2} p ∈ K P 1 ∩ K P 2 , r P 1 > 10 r P 2 r_{P_1}>10r_{P_2} r P 1 > 10 r P 2 , and w P 2 > ? w P 2 w_{P_2}>?w_{P_2} w P 2 > ? w P 2 . Without loss of generality, we choose the coordinates such that e ⃗ P 1 \vec{e}_{P_1} e P 1 is horizontal and v ⃗ P 1 \vec{v}_{P_1} v P 1 is vertical, and a P a_{P} a P to be the origin. Then P 1 P_1 P 1 is contained in rectangle R = [ 0 , Δ P 1 ] × [ − w P 1 , w P 1 ] R=[0,\Delta_{P_1}]\times[-w_{P_1},w_{P_1}] R = [ 0 , Δ P 1 ] × [ − w P 1 , w P 1 ] . Let π \pi π be a path in P 1 P_1 P 1 from a P a_P a P to b P b_P b P . See Figure 34 .
Figure 34. Proof of Lemma 47. By contradiction, assume p ∈ K P 1 ∩ K P 2 p \in K_{P_1} \cap K_{P_2} p ∈ K P 1 ∩ K P 2 . Since P 1 ⊆ R P_1 \subseteq R P 1 ⊆ R , and B 2 ⊆ Conv ( P 2 ) ⊆ B 1 B_2 \subseteq\operatorname{Conv}(P_2) \subseteq B_1 B 2 ⊆ Conv ( P 2 ) ⊆ B 1 , P 2 P_2 P 2 must cross π \pi π .
Since p ∈ P 2 p\in P_2 p ∈ P 2 , P 2 P_2 P 2 lies in B 1 = Ball ( p , 2 Δ P 2 ) B_1=\operatorname{Ball}(p,2\Delta_{P_2}) B 1 = Ball ( p , 2 Δ P 2 ) , which lies in the vertical strip x ∈ [ 0.2 Δ P 1 , 0.8 Δ P 2 ] x\in[0.2\Delta_{P_1},0.8\Delta_{P_2}] x ∈ [ 0.2 Δ P 1 , 0.8 Δ P 2 ] . So B 1 B_1 B 1 must be cut by π \pi π into multiple connected components, with at least the upper part and lower part beyond R R R separated. By connectivity of P 2 P_2 P 2 , P 2 P_2 P 2 must be in one of the connected components, so P 2 P_2 P 2 cannot reach both the upper and lower parts beyond R R R . Consider B 2 = Ball ( p , w P 2 / 20 ) B_2=\operatorname{Ball}(p,w_{P_2}/20) B 2 = Ball ( p , w P 2 /20 ) . Since w P 2 > 40 w P 1 w_{P_2}>40w_{P_1} w P 2 > 40 w P 1 , B 2 B_2 B 2 must cross both the upper and lower boundary of R R R . Recall that B 2 ⊂ K P 2 ⊂ Conv ( P 2 ) B_2\subset K_{P_2}\subset\operatorname{Conv}(P_2) B 2 ⊂ K P 2 ⊂ Conv ( P 2 ) , so P 2 P_2 P 2 must simultaneously reach both the upper and lower parts beyond R R R , which leads to a contradiction.
Then we show that all polygons in the same size group touching a core can be bounded into a matching size rectangle.
Lemma 48 (Similar to Lemma 23 ). Let P P P be a polygon in the size group with scales Δ \Delta Δ and w w w . There is an O ( Δ ) × O ( w ) O(\Delta) \times O(w) O ( Δ ) × O ( w ) rectangle that contains all polygons P ′ P' P ′ in the same group such that K P ∩ K P ′ ≠ ∅ K_P \cap K_{P'} \ne\emptyset K P ∩ K P ′ = ∅ .
Proof. Similar to the case of stars, it’s sufficient to show that all P ′ P' P ′ such that K P ∩ K P ′ ≠ ∅ K_P \cap K_{P'} \ne\emptyset K P ∩ K P ′ = ∅ have similar orientation as P P P . Let θ \theta θ be the smaller angle formed by a P b P a_Pb_P a P b P and a P ′ b P ′ a_{P'}b_{P'} a P ′ b P ′ . By contradiction, assume θ > 1000 w / Δ \theta> 1000w/\Delta θ > 1000 w /Δ . Then consider the two bounding rectangles of size Δ × ( 2 w ) \Delta\times(2w) Δ × ( 2 w ) of P P P and P ′ P' P ′ . Without loss of generality, assume a P a_P a P is the origin and a P b P a_Pb_P a P b P is horizontal. See Figure 34 . Since p ∈ K P ′ p \in K_{P'} p ∈ K P ′ , ∣ y ( a P ′ ) ∣ > 0.4 r P ′ sin θ − 2 w > w |y(a_{P'})| > 0.4r_{P'}\sin\theta- 2w > w ∣ y ( a P ′ ) ∣ > 0.4 r P ′ sin θ − 2 w > w and ∣ y ( b P ′ ) ∣ > 0.4 r P ′ sin θ − 2 w > w |y(b_{P'})| > 0.4r_{P'}\sin\theta- 2w > w ∣ y ( b P ′ ) ∣ > 0.4 r P ′ sin θ − 2 w > w , so one of a P ′ a_{P'} a P ′ and b P ′ b_{P'} b P ′ is above y = w y = w y = w , and the other is below y = − w y = -w y = − w . Therefore, for any path π \pi π in P P P connecting a P a_P a P and b P b_P b P and any path π ′ \pi' π ′ in P ′ P' P ′ connecting a P ′ a_{P'} a P ′ and b P ′ b_{P'} b P ′ , π \pi π and π ′ \pi' π ′ must cross. Therefore, θ = O ( w / Δ ) \theta= O(w/\Delta) θ = O ( w /Δ ) , and one can create an axis-aligned bounding O ( Δ ) × O ( w ) O(\Delta) \times O(w) O ( Δ ) × O ( w ) rectangle for all polygons with their core touching K P K_P K P .
Following the same independent set argument, we get a full proof. Repeated details are omitted.
Therefore, we obtain a polynomial time O ( α log n ) O(\alpha\log n) O ( α log n ) -approximation algorithm for packing n n n polygons into MACC.
Figure 35. Proof of Lemma 48 . p ∈ K P ∩ K P ′ p \in K_{P} \cap K'_{P} p ∈ K P ∩ K P ′ and the angle between a P b P ‾ \overline{a_{P}b_{P}} a P b P and a P ′ b P ′ ‾ \overline{a_{P'}b_{P'}} a P ′ b P ′ are larger than 1000 w / Δ 1000w/\Delta 1000 w /Δ , then the two paths π \pi π and π ′ \pi' π ′ in P P P and P ′ P' P ′ connecting the two ends of their diameter must cross.