Packing convex polygons in minimum-perimeter convex hulls

被引：3

作者：

Kallrath, Josef ^{[1
]}

Romanova, Tatiana ^{[2
,3
]}

Pankratov, Alexander ^{[2
,3
]}

Litvinchev, Igor ^{[4
]}

Infante, Luis ^{[4
]}

机构：

[1] Univ Florida, Dept Astron, Gainesville, FL 32611 USA

[2] Natl Acad Sci Ukraine, Dept Math Modeling & Optimal Design, Inst Mech Engn Problems, Kharkiv, Ukraine

[3] Kharkiv Natl Univ Radioelect, Kharkiv, Ukraine

[4] Nuevo Leon State Univ UANL, Fac Mech & Elect Engn, Grad Program Syst Engn, Monterrey, Mexico

来源：

JOURNAL OF GLOBAL OPTIMIZATION | 2023年 / 85卷 / 01期

基金：

新加坡国家研究基金会;

关键词：

Global optimization; Non-convex nonlinear programming; Polygon packing problem; Convex hull; Perimeter minimization; Non-overlap constraints; Computational geometry; CIRCLES;

D O I：

10.1007/s10898-022-01194-4

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

The problem of packing a given set of freely translated and rotated convex polygons in a minimum-perimeter convex polygon (in particular the minimum-perimeter convex hull) is introduced. A mathematical model of the problem using the phi-function technique is provided. Problem instances with up to 6 convex polygons are solved by the global NLP solver BARON to get a minimum-perimeter convex hull. Numerical experiments for larger instances are reported using the local NLP solver IPOPT.

引用

页码：39 / 59

页数：21

共 43 条

[1] Aligning Two Convex Figures to Minimize Area or Perimeter
Ahn, Hee-Kap
Cheong, Otfried
[J]. ALGORITHMICA, 2012, 62 (1-2) : 464 - 479
[2] Approximating Minimum-Area Rectangular and Convex Containers for Packing Convex Polygons
Alt, Helmut
de Berg, Mark
Knauer, Christian
[J]. ALGORITHMS - ESA 2015, 2015, 9294 : 25 - 34
[3] Analysis of irregular three-dimensional packing problems in additive manufacturing: a new taxonomy and dataset
Araujo, Luiz J. P.
Ozcan, Ender
Atkin, Jason A. D.
Baumers, Martin
[J]. INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH, 2019, 57 (18) : 5920 - 5934
[4] How good are convex hull algorithms?
Avis, D
Bremner, D
Seidel, R
[J]. COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 1997, 7 (5-6): : 265 - 301
[5] Optimal clustering of a pair of irregular objects
Bennell, J.
Scheithauer, G.
Stoyan, Y.
Romanova, T.
Pankratov, A.
[J]. JOURNAL OF GLOBAL OPTIMIZATION, 2015, 61 (03) : 497 - 524
[6] A tutorial in irregular shape packing problems
Bennell, J. A.
Oliveira, J. F.
[J]. JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, 2009, 60 : S93 - S105
[7] The geometry of nesting problems: A tutorial
Bennell, Julia A.
Oliveira, Jose F.
[J]. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2008, 184 (02) : 397 - 415
[8] Mathematical model and efficient algorithms for object packing problem
Chernov, N.
Stoyan, Yu.
Romanova, T.
[J]. COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 2010, 43 (05): : 535 - 553
[9] Cormen ThomasH., 2001, INTRO ALGORITHMS, VSecond, P947
[10] de Berg Mark, 2008, COMPUTATIONAL GEOMET, DOI DOI 10.1007/978-3-540-77974-2

← 1 2 3 4 5 →