betaFeedback

WorksComputer Science

Stacking Stars: Minimum-Area Packing with and without Rotation

Abstract

We study the problem of packing a given set of polygons into a minimum-area convex container, that is, placing them without overlap so as to minimize the area of their convex hull. Every previously known polynomial-time algorithm with a nontrivial approximation guarantee for packing polygons with arbitrary edge orientations required the polygons to be convex. In fact, an algorithm was not even known when every input polygon was a quadrilateral. We obtain such algorithms for the entire class of star-shaped polygons with unrestricted combinatorial complexity. The stars may be just translated or also rotated. In either case, we give an O(log⁡n)O(\log n)-approximation algorithm, where nn is the number of stars. Likewise, we get O(log⁡n)O(\log n)-approximation algorithms for bin and strip packing, assuming that the diameter of the stars is at most some (small) constant. Previous approximation algorithms for polygon packing focused on convex objects, and the analysis always relied on a density argument, i.e., if the area of the packed objects is at least a fraction ρρ of the area of the container, then we have a (1/ρ)(1/ρ)-approximation. However, star-shaped polygons may need an arbitrarily large area to be packed, even when the total area of the stars approaches 00 and each star has bounded diameter. This phenomenon prevents the use of density arguments. We instead establish a strong structural property about any packing: Even though the stars can fit together in complicated ways, we can reorganize them into simple stacks, replace these stacks by rectangles, and consider a packing of these rectangles. The rearrangement costs only a factor of O(log⁡n)O(\log n), which stems from the number of size groups. We complement our algorithms by showing that both the translational and the rotational versions are APX-hard, even for constant complexity stars.

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.

Examples of applications involving irregular packing

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), i.e., better than what is obtained by packing the convex hulls, for packing an arbitrary number nn 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 PP is said to be star-shaped if there is a point q∈Pq \in P that sees all of PP, i.e., for every point p∈Pp \in P, we have qp⊆Pqp \subseteq P. The set of points for which this holds is called the kernel of PP. The radius of PP is the segment from a fixed point qq 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 nn 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)-approximation algorithms for both translational and rotational packing of nn 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)⋅OPTO(\log n) \cdot\mathrm{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 such that, if every polygon has diameter at most δ\delta, there are polynomial-time O(log⁡n)O(\log n)-approximation algorithms for both translational and rotational bin packing and strip packing of nn star-shaped polygons.

For stars of comparable size, the algorithms in fact give 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), 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}, then there exists a polynomial-time O(αlog⁡n)O(\alpha\log n)-approximation algorithm for translational packing of nn 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(Nlog⁡N)O(N \log N)-time algorithm for packing a given set of convex polygons C1,…,CnC_1, \ldots, C_n of total complexity NN into an axis-aligned rectangle RR such that

∣R∣≤c⋅(∑i=1n∣Ci∣+ℓmax⁡hmax⁡)|R| \le c \cdot\left(\sum_{i=1}^{n} |C_i| + \ell_{\max} h_{\max}\right)

where ∣⋅∣|\cdot| denotes area, cc is a constant, and ℓmax⁡\ell_{\max} and hmax⁡h_{\max} are the maximum horizontal and vertical spans of C1,…,CnC_1, \ldots, C_n, respectively.

The goal is to obtain a packing whose convex hull is O(log⁡n)⋅OPTO(\log n) \cdot\mathrm{OPT}, where OPT\mathrm{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)⋅OPTO(\log n) \cdot\mathrm{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⁡hmax⁡=O(OPT)\ell_{\max}h_{\max} = O(\mathrm{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 nn stars P1,…,PnP_1,\ldots,P_n that are all copies of the same star PP. One might ask: For which PP does packing the convex hulls of the PiP_i, instead of the stars themselves, give a good approximation?

The answer is surprisingly nuanced. If PP 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 PP given by the union of the two segments {0}×[−1,1]\{0\} \times[-1,1] and [−1,1]×{0}[-1,1] \times\{0\}, forming a plus. For two copies of PP, no matter how they are arranged, their origins never have ℓ∞\ell_\infty-distance less than 1. One can, in fact, replace PP by the square Q=[−0.5,0.5]×[−0.5,0.5]Q = [-0.5,0.5] \times[-0.5,0.5]: any packing of nn copies of PP is also a packing of nn copies of QQ, and vice versa; see Figure 2 a). The convex hull of PP has twice the area of QQ, so packing the convex hulls of copies of PP is, up to constants, as good as packing the copies of PP.

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 PP to be the union of the two segments {0}×[0,1]\{0\} \times[0,1] and [0,1]×{0}[0,1] \times\{0\}, forming an L, the answer is very different. For any ε>0\varepsilon> 0, one can pack nn copies of PP into the convex container [0,1+ε]×[0,1+ε][0,1+\varepsilon] \times[0,1+\varepsilon] by forming a stack of nested copies of PP (see Figure 2 b)), whereas packing the convex hulls requires a container of area Θ(n)\Theta(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).

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 PP a point qPq_P in its kernel, its reference point. The radius of PP is the segment from qPq_P to a farthest point RPR_P of PP (ties are broken arbitrarily), and rPr_P is its length. The width wPw_P of PP is the largest distance of a point of PP from the line through the radius, and LPL_P is a point attaining it; see Figure 3. Let rmax⁡r_{\max} and wmax⁡w_{\max} be the maximum radius length and width of any input star.

Figure 3. A star PP with reference point qPq_P, radius qPRPq_PR_P of length rPr_P, and width wPw_P attained at LPL_P.

We partition the input stars into size groups Ga,b\mathcal{G}_{a,b}, which contains all stars with radius and width of one dyadic scale, i.e., stars PP such that rP∈(rmax⁡/2a+1,rmax⁡/2a]r_P \in(r_{\max}/2^{a+1}, r_{\max}/2^a] and wP∈(wmax⁡/2b+1,wmax⁡/2b]w_P \in(w_{\max}/2^{b+1}, w_{\max}/2^b]. Polygons with a>log⁡na > \log n or b>log⁡nb > \log n are packed via their convex hulls: each of these hulls has area O(rmax⁡wmax⁡/n)O(r_{\max}w_{\max}/n), so together they need area O(rmax⁡wmax⁡)=O(OPT)O(r_{\max}w_{\max}) = O(\mathrm{OPT}). We are left with polygons in O(log⁡2n)O(\log^2 n) size groups, where the size group of a,ba,b has scales r=rmax⁡/2ar = r_{\max}/2^a and w=wmax⁡/2bw = w_{\max}/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 qPq_P. We split [0,2π)[0,2\pi) into intervals of length Θ(w/r)\Theta(w/r), and the fine type of a star is the interval containing its orientation, together with the side of the radius on which LPL_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 nn nonempty fine types, and bounding the area of each of them independently against OPT could result in a Θ(n)\Theta(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} be a set of star-shaped polygons in one size group with scales r,wr,w, and let Π\Pi be a packing of P\mathcal{P} in a convex container CC. Then P\mathcal{P} can be partitioned into a disjoint union of parts

P=P1∪˙⋯∪˙Pt\mathcal{P} = \mathcal{P}_1 \mathbin{\dot\cup} \cdots\mathbin{\dot\cup} \mathcal{P}_t

such that in every part Pj\mathcal{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 BjB_j of dimensions O(r)×O(w)O(r) \times O(w). Moreover,

∑j=1t∣Bj∣=O(∣C∣),\sum_{j=1}^{t} |B_j| = O(|C|),

where ∣C∣|C| is the area of CC.

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)-radian classes; there are constantly many of these. Within one class, all radii can be considered to be nearly horizontal, and we may take CC to be a parallelogram with vertical sides of length HH and horizontal span WW. Cut CC into vertical strips of width εr\varepsilon r, and consider the stars with reference point in a fixed strip. Each of their radii has length more than r/2r/2 and is nearly horizontal, so it crosses two vertical test lines ℓ1,ℓ2\ell_1,\ell_2 placed Θ(r)\Theta(r) to the right of the strip; see Figure 4. Partition each test line into m=O(H/w)m=O(H/w) intervals of length εw\varepsilon w, and assign each star the pair (a,b)(a,b) of intervals crossed by its radius. Two radii ordered one way on ℓ1\ell_1 and the other way on ℓ2\ell_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 2m=O(H/w)2m=O(H/w) of them rather than m2m^2.

Figure 4. Left: The enclosing parallelogram is cut into vertical strips of width εr\varepsilon r; one strip is shown. Two test lines ℓ1,ℓ2\ell_1,\ell_2 are placed to its right. The reference points and radii assigned to one pair (a,b)(a,b) of intervals are shown. Right: The occupied interval pairs form a monotone sequence in [m]2[m]^2.

The stars assigned the same pair (a,b)(a,b) and of the same fine type form one part Pj\mathcal{P}_j. For stars assigned to the same pair (a,b)(a,b), their reference points lie in a strip of width εr\varepsilon r, and their radii pass through the same two intervals of length εw\varepsilon w at distance Θ(r)\Theta(r), so their orientations differ by 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). There are O(W/r)O(W/r) strips, each with O(H/w)O(H/w) occupied pairs, each contributing area O(rw)O(rw), so the rectangles over all parts have total area O(WH)=O(∣C∣)O(WH)=O(|\mathcal{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 rr and ww, and let dd be a direction, depending only on the fine type, that is nearly perpendicular to all its radii. For a star PP, extend the two segments qPRPq_P R_P and qPLPq_P L_P beyond RPR_P and LPL_P until both endpoints are at height exactly h=Θ(w)h=\Theta(w) above qPq_P in direction dd. The value hh is common for all stars of the same fine type. We call these two extended segments the arms of PP, and the polygon Q(P)Q(P) obtained by adding the arms to PP the bowl of PP; see Figure 5. A bowl (i) extends at most a distance hh below qPq_P in direction dd, (ii) extends exactly a distance hh above qPq_P, and (iii) satisfies

References

  1. [1]Anders Aamand, Mikkel Abrahamsen, Simon Bartlmae, Arindam Khan, Linda Kleist, and Csaba D. Tóth. Online geometric packing through online TSP scheduling. CoRR, abs/2607.22179, 2026. arXiv:2607.22179, doi:10.48550/ARXIV.2607.22179.DOI
  2. [2]Anders Aamand, Mikkel Abrahamsen, Lorenzo Beretta, and Linda Kleist. Online sorting and translational packing of convex polygons. In Symposium on Discrete Algorithms (SODA 2023), pages 1806–1833, 2023. doi:10.1137/1.9781611977554.CH69.DOI
  3. [3]Mikkel Abrahamsen and Lorenzo Beretta. Online packing to minimize area or perimeter. In Symposium on Computational Geometry (SoCG 2021), pages 6:1–6:15, 2021. doi:10.4230/LIPICS.SOCG.2021.6.DOI
  4. [4]Hee-Kap Ahn and Otfried Cheong. Aligning two convex figures to minimize area or perimeter. Algorithmica, 62(1–2):464–479, 2012. doi:10.1007/s00453-010-9466-1.
  5. [5]Helmut Alt, Mark de Berg, and Christian Knauer. Approximating minimum-area rectangular and convex containers for packing convex polygons. Journal on Computational Geometry, 8(1):1–10, 2017. doi:10.20382/jocg.v8i1a1.DOI
  6. [6]Helmut Alt, Mark de Berg, and Christian Knauer. Corrigendum to: Approximating minimum-area rectangular and convex containers for packing convex polygons. JoCG, 11(1):653–655, 2020. doi:10.20382/jocg.v11i1a26.
  7. [7]Helmut Alt and Ferran Hurtado. Packing convex polygons into rectangular boxes. In Japanese Conference on Discrete and Computational Geometry (JCDCG 2000), pages 67–80, 2000. doi:10.1007/3-540-47738-1_5.DOI
  8. [8]Mikkel Abrahamsen, Tillmann Miltzow, and Nadja Seiferth. Framework for ℝ-completeness of two-dimensional packing problems. TheoretiCS, 3, 2024. doi:10.46298/THEORETICS.24.11.DOI
  9. [9]R. Alvarez-Valdes, A. Martinez, and J. M. Tamarit. A branch & bound algorithm for cutting and packing irregularly shaped pieces. International Journal of Production Economics, 145(2):463–477, 2013. doi:10.1016/j.ijpe.2013.04.007.
  10. [10]Jeffrey Bosboom, Erik D. Demaine, Martin L. Demaine, Adam Hesterberg, Pasin Manurangsi, and Anak Yodpinyanee. Even 1 × n edge-matching and jigsaw puzzles are really hard. J. Inf. Process., 25:682–694, 2017. doi:10.2197/IPSJJIP.25.682.DOI
  11. [11]Julia Bennell and Jose Oliveira. The geometry of nesting problems: A tutorial. European Journal of Operational Research, 184(2):397–415, 2008. doi:10.1016/j.ejor.2006.11.038.DOI
  12. [12]Julia Bennell and Jose Oliveira. A tutorial in irregular shape packing problems. Journal of the Operational Research Society, 60:S93–S105, 2009. doi:10.1057/jors.2008.169.DOI
  13. [13]Henrik I. Christensen, Arindam Khan, Sebastian Pokutta, and Prasad Tetali. Approximation and online algorithms for multidimensional bin packing: A survey. Computer Science Review, 24:63–79, 2017. doi:10.1016/j.cosrev.2016.12.001.DOI
  14. [14]Maria Antónia Carravilla, Cristina Ribeiro, and José Fernando Oliveira. Solving nesting problems with non-convex polygons by constraint logic programming. International Transactions in Operational Research, 10(6):651–663, 2003. doi:10.1111/1475–3995.00434.DOI
  15. [15]János Csirik and Gerhard J. Woeginger. On-line packing and covering problems. In Amos Fiat and Gerhard J. Woeginger, editors, Online Algorithms: The State of the Art, pages 147–177. Springer, 1998. doi:10.1007/BFb0029568.DOI
  16. [16]Kathryn A. Dowsland and William B. Dowsland. Solution approaches to irregular nesting problems. European Journal of Operational Research, 84(3):506–521, 1995. Cutting and Packing. doi:10.1016/0377–2217(95)00019–M.DOI
  17. [17]Harald Dyckhoff and Ute Finke. Cutting and packing in production and distribution: A typology and bibliography. Physica Heidelberg, 1992. doi:10.1007/978–3–642–58165–6.
  18. [18]Karen L. Daniels and Victor Milenkovic. Multiple translational containment, part I: an approximate algorithm. Algorithmica, 19(1/2):148–182, 1997. doi:10.1007/PL00014415.
  19. [19]Lucas de Oliveira Silva, Elisa Dell’Arriva, and Flávio Keidi Miyazawa. Geometric bin packing beyond convexity: Approximation schemes without augmentation. arXiv:2611.04829, 2026. doi:10.48550/arXiv.2611.04829.
  20. [20]Sándor P. Fekete and Hella-Franziska Hoffmann. Online square-into-square packing. Algorithmica, 77(3):867–901, 2017. doi:10.1007/S00453–016–0114–2.
  21. [21]Sándor P. Fekete, Phillip Keldenich, Dominik Krupke, and Stefan Schirra. Maximum polygon packing: The CG: SHOP challenge 2024. CoRR, abs/2403.16203, 2024. arXiv:2403.16203, doi:10.48550/ARXIV.2403.16203.arxiv.org/abs/2403.16203
  22. [22]Matteo Fischetti and Ivan Luzzi. Mixed-integer programming models for nesting problems. Journal of Heuristics, 15(3):201–226, 2009. doi:10.1007/s10732-008-9088-9.DOI
  23. [23]Tim Gerlach, Benjamin Hennies, and Linda Kleist. Online packing of orthogonal polygons. In Symposium on Computational Geometry (SoCG 2026), 2026. To appear. arXiv:2603.22098, doi:10.48550/ARXIV.2603.22098.DOI
  24. [24]B. Guo, Y. Zhang, J. Hu, J. Li, F. Wu, Q. Peng, and Q. Zhang. Two-dimensional irregular packing problems: A review. Front. Mech. Eng., 2022. doi:10.3389/fmech.2022.966691.DOI
  25. [25]Eva Hopper and Brian Turton. A review of the application of meta-heuristic algorithms to 2D strip packing problems. Artificial Intelligence Review, 16(4):257–300, 2001. doi:10.1023/A:1012590107280.DOI
  26. [26]Donald R. Jones. A fully general, exact algorithm for nesting irregular shapes. Journal of Global Optimization, 59(2–3):367–404, 2014. doi:10.1007/s10898-013-0129-z.DOI
  27. [27]Adam Kurpisz and Silvan Suter. Improved approximations for translational packing of convex polygons. In European Symposium on Algorithms (ESA 2023), pages 76:1–76:14, 2023. doi:10.4230/LIPIcs.ESA.2023.76.arxiv.org/abs/2308.08523
  28. [29]Victor J. Milenkovic and Karen Daniels. Translational polygon containment and minimal enclosure using mathematical programming. International Transactions in Operational Research, 6(5):525–554, 1999. doi:10.1111/j.1475-3995.1999.tb00171.x.DOI
  29. [30]Victor Milenkovic. Translational polygon containment and minimal enclosure using linear programming based restriction. In Symposium on Theory of Computing (STOC 1996), pages 109–118, 1996. doi:10.1145/237814.237840.DOI
  30. [31]Victor Milenkovic. Multiple translational containment, part II: exact algorithms. Algorithmica, 19(1/2):183–218, 1997. doi:10.1007/PL00014416.DOI
  31. [32]Victor J. Milenkovic. Rotational polygon containment and minimum enclosure using only robust 2D constructions. Computational Geometry, 13(1):3–19, 1999. doi:10.1016/S0925-7721(99)00006-1.DOI
  32. [33]Arturo I. Merino and Andreas Wiese. On the two-dimensional knapsack problem for convex polygons. In International Colloquium on Automata, Languages, and Programming (ICALP 2020), pages 84:1–84:16, 2020. doi:10.4230/LIPIcs.ICALP.2020.84.DOI
  33. [34]Dongwoo Park, Sang Won Bae, Helmut Alt, and Hee-Kap Ahn. Bundling three convex polygons to minimize area or perimeter. Computational Geometry, 51:1–14, 2016. doi:10.1016/j.comgeo.2015.10.003.DOI
  34. [36]Ola Svensson, Jakub Tarnawski, and László A. Végh. A constant-factor approximation algorithm for the asymmetric traveling salesman problem. J. ACM, 67(6):37:1–37:53, 2020. doi:10.1145/3424306.DOI
  35. [37]Vera Traub and Jens Vygen. Approximation Algorithms for Traveling Salesman Problems. Cambridge University Press, 2024. doi:10.1017/9781009445436.DOI
  36. [38]Kai Tang, Charlie C. L. Wang, and Danny Z. Chen. Minimum area convex packing of two convex polygons. International Journal of Computational Geometry and Applications, 16(1):41–74, 2006. doi:10.1142/S0218195906001926.DOI
  37. [39]Rob van Stee. SIGACT news online algorithms column 20: the power of harmony. SIGACT News, 43(2):127–136, 2012. doi:10.1145/2261417.2261440.DOI
  38. [40]Rob van Stee. SIGACT news online algorithms column 26: Bin packing in multiple dimensions. SIGACT News, 46(2):105–112, 2015. doi:10.1145/2789149.2789167.DOI

Paper details

vlnc:W_cqhmtnqp
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 9

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents