275:) is a problem in which both the sizes and the locations of the input rectangles are fixed, and the goal is to select a largest sum of non-overlapping rectangles. In contrast, in rectangle packing (as in real-life packing problems) the sizes of the rectangles are given, but their locations are flexible. Some papers use the term "packing" even when the locations are fixed.
238:
In this variant, the small rectangles can have varying lengths and widths, and their orientation is fixed (they cannot be rotated). The goal is to pack them in an enclosing rectangle of minimum area, with no boundaries on the enclosing rectangle's width or height. This problem has an important
239:
application in combining images into a single larger image. A web page that loads a single larger image often renders faster in the browser than the same page loading multiple small images, due to the overhead involved in requesting each image from the web server. The problem is
51:). The goal is to pack as many small rectangles as possible into the big rectangle without overlap between any rectangles (small or large). Common constraints of the problem include limiting small rectangle rotation to 90° multiples and requiring that each small rectangle is
26:
where the objective is to determine whether a given set of small rectangles can be placed inside a given large polygon, such that no two small rectangles overlap. Several variants of this problem have been studied.
215:, so they exactly fit into the big rectangle. Conversely, in any packing of the big rectangle, there must be no "holes", so the rectangles must not be rotated. Therefore, the packing must involve exactly
230:. Without this requirement, the small rectangles may be rotated in arbitrary angles. In this more general case, it is not clear if the problem is in NP, since it is much harder to verify a solution.
226:
When there is an additional restriction that the packing must be exact (with no wasted space), the small rectangles may be rotated only by multiples of 90°. In this case, the problem is in
143:
In this variant, the small rectangles can have varying lengths and widths, and they should be packed in a given large rectangle. The decision problem of whether such a packing exists is
310:
Birgin, E G; Lobato, R D; Morabito, R (2010). "An effective recursive partitioning approach for the packing of identical rectangles in a rectangle".
257:
is a variant of rectangle packing, with the additional constraint that the rectangles in the packing should be separable using only
90:, and a set of identical squares, the goal is to find the largest number of non-overlapping squares that can be packed in points of
62:
stowage. As an example result: it is possible to pack 147 small rectangles of size (137,95) in a big rectangle of size (1600,1230).
504:
121:
576:
280:
285:
581:
571:
543:
529:
Chan, T. M. (2003). "Polynomial-time approximation schemes for packing and piercing fat objects".
538:
290:
267:
58:
This problem has some applications such as loading of boxes on pallets and, specifically,
8:
148:
71:
466:
413:
327:
253:
117:
552:
346:
207:. Every solution to the 3-partition instance induces a packing of the rectangles into
486:
405:
366:
362:
417:
331:
548:
476:
397:
358:
319:
144:
131:. Finding a largest square-packing is NP-hard; one may prove this by reducing from
386:"Jigsaw Puzzles, Edge Matching, and Polyomino Packing: Connections and Complexity"
240:
227:
23:
293:: packing congruent rectangular bricks of any dimension into rectangular boxes.
435:
401:
565:
490:
409:
370:
52:
35:
In this variant, there are multiple instances of a single rectangle of size (
385:
345:
Fowler, Robert J.; Paterson, Michael S.; Tanimoto, Steven L. (1981-06-13).
233:
180:
small rectangles, all with a width of 1, such that the length of rectangle
323:
75:
243:
in general, but there are fast algorithms for solving small instances.
219:
rows where each row contains rectangles with a total length of exactly
505:"Fast Optimizing Rectangle Packing Algorithm for Building CSS Sprites"
481:
454:
65:
138:
59:
471:
223:. This corresponds to a solution of the 3-partition instance.
30:
211:
subsets such that the total length in each subset is exactly
455:"Optimal Rectangle Packing: An Absolute Placement Approach"
436:"MIT OpenCourseWare – Hardness made Easy 2 – 3-Partition I"
347:"Optimal packing and covering in the plane are NP-complete"
132:
234:
Packing different rectangles in a minimum-area rectangle
120:
of these squares. A square-packing is equivalent to an
344:
309:
384:Demaine, Erik D.; Demaine, Martin L. (2007-06-01).
66:Packing identical squares in a rectilinear polygon
139:Packing different rectangles in a given rectangle
563:
383:
459:Journal of Artificial Intelligence Research
312:Journal of the Operational Research Society
31:Packing identical rectangles in a rectangle
542:
480:
470:
452:
151:. Given an instance of 3-partition with 3
147:. This can be proved by a reduction from
522:
433:
564:
453:Huang, E.; Korf, R. E. (2013-01-23).
528:
429:
427:
246:
43:), and a bigger rectangle of size (
16:Optimization problem in mathematics
13:
14:
593:
424:
497:
446:
377:
351:Information Processing Letters
338:
303:
195:. The big rectangle has width
105:, we put a square centered at
1:
553:10.1016/s0196-6774(02)00294-8
297:
281:Circle packing in a rectangle
97:Suppose that, for each point
363:10.1016/0020-0190(81)90111-3
7:
10:
598:
286:Square packing in a square
55:to the large rectangle.
402:10.1007/s00373-007-0713-4
390:Graphs and Combinatorics
273:Maximum independent set
434:Demaine, Erik (2015).
172:, with a total sum of
531:Journal of Algorithms
324:10.1057/jors.2008.141
74:(whose sides meet at
577:Geometric algorithms
268:Maximum disjoint set
82:in the plane, a set
509:www.codeproject.com
291:De Bruijn's theorem
155:positive integers:
72:rectilinear polygon
254:Guillotine cutting
118:intersection graph
482:10.1613/jair.3735
20:Rectangle packing
589:
582:NP-hard problems
572:Packing problems
557:
556:
546:
526:
520:
519:
517:
516:
501:
495:
494:
484:
474:
450:
444:
443:
431:
422:
421:
381:
375:
374:
342:
336:
335:
307:
247:Related problems
176:, we construct 3
597:
596:
592:
591:
590:
588:
587:
586:
562:
561:
560:
527:
523:
514:
512:
503:
502:
498:
451:
447:
432:
425:
382:
378:
343:
339:
308:
304:
300:
259:guillotine cuts
249:
236:
189:
171:
161:
141:
130:
122:independent set
115:
68:
33:
24:packing problem
17:
12:
11:
5:
595:
585:
584:
579:
574:
559:
558:
544:10.1.1.21.5344
537:(2): 178–189.
521:
511:. 14 June 2011
496:
445:
423:
396:(1): 195–208.
376:
357:(3): 133–137.
337:
318:(2): 306–320.
301:
299:
296:
295:
294:
288:
283:
277:
276:
263:
262:
248:
245:
235:
232:
187:
166:
159:
140:
137:
128:
113:
67:
64:
32:
29:
15:
9:
6:
4:
3:
2:
594:
583:
580:
578:
575:
573:
570:
569:
567:
554:
550:
545:
540:
536:
532:
525:
510:
506:
500:
492:
488:
483:
478:
473:
468:
464:
460:
456:
449:
441:
437:
430:
428:
419:
415:
411:
407:
403:
399:
395:
391:
387:
380:
372:
368:
364:
360:
356:
352:
348:
341:
333:
329:
325:
321:
317:
313:
306:
302:
292:
289:
287:
284:
282:
279:
278:
274:
270:
269:
265:
264:
260:
256:
255:
251:
250:
244:
242:
231:
229:
224:
222:
218:
214:
210:
206:
202:
198:
194:
190:
183:
179:
175:
170:
165:
158:
154:
150:
146:
136:
134:
127:
123:
119:
112:
108:
104:
100:
95:
93:
89:
86:of points in
85:
81:
77:
73:
63:
61:
56:
54:
50:
46:
42:
38:
28:
25:
21:
534:
530:
524:
513:. Retrieved
508:
499:
462:
458:
448:
439:
393:
389:
379:
354:
350:
340:
315:
311:
305:
272:
266:
258:
252:
237:
225:
220:
216:
212:
208:
204:
200:
196:
192:
185:
181:
177:
173:
168:
163:
156:
152:
142:
125:
110:
106:
102:
98:
96:
91:
87:
83:
79:
76:right angles
69:
57:
48:
44:
40:
36:
34:
19:
18:
241:NP-complete
199:and length
149:3-partition
566:Categories
515:2020-09-09
298:References
53:orthogonal
539:CiteSeerX
491:1076-9757
472:1402.0557
465:: 47–87.
410:1435-5914
371:0020-0190
418:17190810
332:12718141
70:Given a
60:woodpulp
440:Youtube
162:, ...,
145:NP-hard
116:be the
541:
489:
416:
408:
369:
330:
109:. Let
467:arXiv
414:S2CID
328:S2CID
22:is a
487:ISSN
406:ISSN
367:ISSN
271:(or
133:3SAT
549:doi
477:doi
398:doi
359:doi
320:doi
203:+ 3
184:is
174:m T
124:in
101:in
94:.
568::
547:.
535:46
533:.
507:.
485:.
475:.
463:46
461:.
457:.
438:.
426:^
412:.
404:.
394:23
392:.
388:.
365:.
355:12
353:.
349:.
326:.
316:61
314:.
228:NP
191:+
135:.
78:)
555:.
551::
518:.
493:.
479::
469::
442:.
420:.
400::
373:.
361::
334:.
322::
261:.
221:T
217:m
213:T
209:m
205:m
201:T
197:m
193:m
188:i
186:a
182:i
178:m
169:m
167:3
164:a
160:1
157:a
153:m
129:S
126:G
114:S
111:G
107:p
103:S
99:p
92:S
88:R
84:S
80:R
49:W
47:,
45:L
41:w
39:,
37:l
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.