{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,6]],"date-time":"2025-12-06T17:12:46Z","timestamp":1765041166403,"version":"3.37.3"},"reference-count":41,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2021,3,19]],"date-time":"2021-03-19T00:00:00Z","timestamp":1616112000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,3,19]],"date-time":"2021-03-19T00:00:00Z","timestamp":1616112000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100003725","name":"National Research Foundation of Korea","doi-asserted-by":"publisher","award":["2017R1A3B1023591","2016K1A4A3914691"],"award-info":[{"award-number":["2017R1A3B1023591","2016K1A4A3914691"]}],"id":[{"id":"10.13039\/501100003725","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Glob Optim"],"published-print":{"date-parts":[[2021,7]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The minimal convex hulls of disks problem is to find such arrangements of circular disks in the plane that minimize the length of the convex hull boundary. The mixed-integer non-linear programming model, named [17], works only for small to moderate-sized problems. Here we propose a polylithic framework of the problem for big problem instances by combining the following algorithms and models: (i) A fast disk-packing algorithm based on Voronoi diagrams, non-linear programming (NLP) models for packing disks, and an NLP model for minimizing the discretized perimeter of convex hull; (ii) A fast convex-hull algorithm to compute the convex hulls of disk arrangements and their perimeter lengths; (iii) A mixed-integer NLP model taking the output of as its input. We present complete analytic solutions for small problems up to four disks and a semi-analytic mixed-integer linear programming model which yields exact solutions for strip packing problems with up to one thousand congruent disks. It turns out that the proposed polylithic approach works fine for large problem instances containing up to 1,000 disks. Monolithic and polylithic solutions using usually outperform other approaches. The polylithic approach yields better solutions than the results in [17] and provides a benchmark suite for further research.<\/jats:p>","DOI":"10.1007\/s10898-021-01002-5","type":"journal-article","created":{"date-parts":[[2021,3,19]],"date-time":"2021-03-19T10:43:23Z","timestamp":1616150603000},"page":"551-594","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Near optimal minimal convex hulls of disks"],"prefix":"10.1007","volume":"80","author":[{"given":"Josef","family":"Kallrath","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Joonghyun","family":"Ryu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chanyoung","family":"Song","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mokwon","family":"Lee","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7855-2604","authenticated-orcid":false,"given":"Deok-Soo","family":"Kim","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,3,19]]},"reference":[{"key":"1002_CR1","doi-asserted-by":"publisher","DOI":"10.1142\/8685","volume-title":"Voronoi Diagrams and Delaunay Triangulations","author":"F Aurenhammer","year":"2013","unstructured":"Aurenhammer, F., Klein, R., Lee, D.T.: Voronoi Diagrams and Delaunay Triangulations. World Scientific, Singapore (2013)"},{"issue":"2","key":"1002_CR2","doi-asserted-by":"publisher","first-page":"397","DOI":"10.1016\/j.ejor.2006.11.038","volume":"184","author":"JA Bennell","year":"2008","unstructured":"Bennell, J.A., Oliveira, J.F.: The geometry of nesting problems: a tutorial. Eur. J. Oper. Res. 184(2), 397\u2013415 (2008)","journal-title":"Eur. J. Oper. Res."},{"key":"1002_CR3","doi-asserted-by":"crossref","unstructured":"B\u00f6r\u00f6czky\u00a0J.R.K.: Finite Packing and Covering. Cambridge Tracts in Mathematics. Cambridge University Press (2004)","DOI":"10.1017\/CBO9780511546587"},{"key":"1002_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.ejor.2012.12.006","volume":"1","author":"AWG Bortfeldt","year":"2013","unstructured":"Bortfeldt, A.W.G.: Constraints in container loading: a state-of-the-art review. Eur. J. Oper. Res. 1, 1\u201320 (2013)","journal-title":"Eur. J. Oper. Res."},{"issue":"5","key":"1002_CR5","doi-asserted-by":"publisher","first-page":"535","DOI":"10.1016\/j.comgeo.2009.12.003","volume":"43","author":"N Chernov","year":"2010","unstructured":"Chernov, N., Stoyan, Y., Romanova, T.: Mathematical model and efficient algorithms for object packing problem. Comput. Geom. 43(5), 535\u2013553 (2010)","journal-title":"Comput. Geom."},{"issue":"3","key":"1002_CR6","doi-asserted-by":"publisher","first-page":"570","DOI":"10.1016\/j.ejor.2016.03.009","volume":"253","author":"LH Cherri","year":"2016","unstructured":"Cherri, L.H., Mundim, L.R., Andretta, M., Toledo, F.M.B., Oliveira, J., Carravilla, M.A.: Robust mixed-integer linear programming models for the irregular strip packing problem. Eur. J. Oper. Res. 253(3), 570\u2013583 (2016)","journal-title":"Eur. J. Oper. Res."},{"issue":"3","key":"1002_CR7","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1016\/0020-0190(95)00132-V","volume":"56","author":"O Devillers","year":"1995","unstructured":"Devillers, O., Golin, M.J.: Incremental algorithms for finding the convex hulls of circles and the lower envelopes of parabolas. Inform. Process. Lett. 56(3), 157\u2013164 (1995)","journal-title":"Inform. Process. Lett."},{"issue":"3","key":"1002_CR8","doi-asserted-by":"publisher","first-page":"811","DOI":"10.1016\/j.ejor.2004.09.008","volume":"171","author":"AM Gomes","year":"2006","unstructured":"Gomes, A.M., Oliveira, J.F.: Solving irregular strip packing problems by hybridising simulated annealing and linear programming. Eur. J. Oper. Res. 171(3), 811\u2013829 (2006)","journal-title":"Eur. J. Oper. Res."},{"key":"1002_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-54103-9","volume-title":"On the Computational Geometry of Pocket Machining","author":"M Held","year":"1991","unstructured":"Held, M.: On the Computational Geometry of Pocket Machining. Lecture Notes in Computer Science, vol. 500. Springer, New York (1991)"},{"issue":"5","key":"1002_CR10","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1016\/j.cad.2008.08.004","volume":"41","author":"M Held","year":"2009","unstructured":"Held, M., Huber, S.: Topology-oriented incremental computation of Voronoi diagrams of circular arcs and straight-line segments. Comput. Aided Des. 41(5), 327\u2013338 (2009)","journal-title":"Comput. Aided Des."},{"issue":"3","key":"1002_CR11","doi-asserted-by":"publisher","first-page":"1280","DOI":"10.1016\/j.ejor.2005.11.069","volume":"183","author":"M Hifi","year":"2007","unstructured":"Hifi, M., M\u2019Hallah, R.: A dynamic adaptive local search algorithm for the circular packing problem. Eur. J. Oper. Res. 183(3), 1280\u20131294 (2007)","journal-title":"Eur. J. Oper. Res."},{"issue":"3","key":"1002_CR12","doi-asserted-by":"publisher","first-page":"260","DOI":"10.1016\/j.cad.2005.11.001","volume":"38","author":"L Jin","year":"2006","unstructured":"Jin, L., Kim, D., Mu, L., Kim, D.S., Hu, S.M.: A sweepline algorithm for Euclidean Voronoi diagram of circles. Comput. Aided Des. 38(3), 260\u2013272 (2006)","journal-title":"Comput. Aided Des."},{"key":"1002_CR13","first-page":"1983","volume":"33","author":"J Kallrath","year":"2009","unstructured":"Kallrath, J.: Combined strategic design operative planning in the process industry. Comput. Chem. Eng. 33, 1983\u20131993 (2009)","journal-title":"Comput. Chem. Eng."},{"issue":"3","key":"1002_CR14","doi-asserted-by":"publisher","first-page":"453","DOI":"10.1007\/s11590-011-0320-4","volume":"5","author":"J Kallrath","year":"2011","unstructured":"Kallrath, J.: Polylithic modeling and solution approaches using algebraic modeling systems. Optim. Lett. 5(3), 453\u2013466 (2011)","journal-title":"Optim. Lett."},{"key":"1002_CR15","doi-asserted-by":"publisher","unstructured":"Kallrath J., Blackburn R., N\u00e4umann J.: Grid-enhanced polylithic modeling and solution approaches for hard optimization Problems. In: Bock H.G., J\u00e4ger W., Kostina E., Phu H.X. (eds) Modeling, Simulation and Optimization of Complex Processes HPSC 2018, pp.83\u201396, Springer, Cham. (2021). https:\/\/doi.org\/10.1007\/978-3-030-55240-4_4","DOI":"10.1007\/978-3-030-55240-4_4"},{"issue":"4","key":"1002_CR16","doi-asserted-by":"publisher","first-page":"883","DOI":"10.1007\/s10013-018-0317-8","volume":"46","author":"J Kallrath","year":"2018","unstructured":"Kallrath, J., Frey, M.M.: Minimal surface convex hulls of spheres. Vietnam J. Math. 46(4), 883\u2013913 (2018)","journal-title":"Vietnam J. Math."},{"key":"1002_CR17","doi-asserted-by":"publisher","DOI":"10.1007\/s10898-018-0724-0","author":"J Kallrath","year":"2018","unstructured":"Kallrath, J., Frey, M.M.: Packing circles into perimeter-minimizing convex hulls. J. Glob. Optim. (2018). https:\/\/doi.org\/10.1007\/s10898-018-0724-0","journal-title":"J. Glob. Optim."},{"key":"1002_CR18","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1007\/s00454-006-1277-4","volume":"37","author":"KJ B\u00f6r\u00f6czky","year":"2007","unstructured":"B\u00f6r\u00f6czky, K.J., Ruzsa, I.Z.: Note on an inequality of Wegner. Disc. Comput. Geom. 37, 245\u2013249 (2007)","journal-title":"Disc. Comput. Geom."},{"issue":"2","key":"1002_CR19","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1142\/S021819590500166X","volume":"15","author":"D Kim","year":"2005","unstructured":"Kim, D., Kim, D.S., Sugihara, K.: Euclidean Voronoi diagram for circles in a circle. Int. J. Comput. Geom. Appl. 15(2), 209\u2013228 (2005)","journal-title":"Int. J. Comput. Geom. Appl."},{"issue":"14","key":"1002_CR20","doi-asserted-by":"publisher","first-page":"1069","DOI":"10.1016\/S0010-4485(98)00063-3","volume":"30","author":"DS Kim","year":"1998","unstructured":"Kim, D.S.: Polygon offsetting using a Voronoi diagram and two stacks. Comput. Aided Des. 30(14), 1069\u20131076 (1998)","journal-title":"Comput. Aided Des."},{"issue":"8","key":"1002_CR21","doi-asserted-by":"publisher","first-page":"605","DOI":"10.1016\/0010-4485(95)99797-C","volume":"27","author":"DS Kim","year":"1995","unstructured":"Kim, D.S., Hwang, I.K., Park, B.J.: Representing the Voronoi diagram of a simple polygon using rational quadratic B$$\\acute{e}$$zier curves. Comput. Aided Des. 27(8), 605\u2013614 (1995)","journal-title":"Comput. Aided Des."},{"key":"1002_CR22","doi-asserted-by":"publisher","first-page":"541","DOI":"10.1016\/S0167-8396(01)00050-4","volume":"18","author":"DS Kim","year":"2001","unstructured":"Kim, D.S., Kim, D., Sugihara, K.: Voronoi diagram of a circle set from Voronoi diagram of a point set: I. Topology. Comput. Aided Geom. Des. 18, 541\u2013562 (2001)","journal-title":"Comput. Aided Geom. Des."},{"key":"1002_CR23","doi-asserted-by":"publisher","first-page":"563","DOI":"10.1016\/S0167-8396(01)00051-6","volume":"18","author":"DS Kim","year":"2001","unstructured":"Kim, D.S., Kim, D., Sugihara, K.: Voronoi diagram of a circle set from Voronoi diagram of a point set: II. Geometry. Comput. Aided Geom. Des. 18, 563\u2013585 (2001)","journal-title":"Comput. Aided Geom. Des."},{"issue":"1","key":"1002_CR24","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1137\/0210006","volume":"10","author":"DT Lee","year":"1981","unstructured":"Lee, D.T., Drysdale, R.L.: Generalization of Voronoi diagrams in the plane. SIAM J. Comput. 10(1), 73\u201387 (1981)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"1002_CR25","doi-asserted-by":"publisher","first-page":"14:1","DOI":"10.1145\/2939366","volume":"43","author":"M Lee","year":"2016","unstructured":"Lee, M., Sugihara, K., Kim, D.S.: Topology-oriented incremental algorithm for the robust construction of the Voronoi diagrams of disks. ACM Trans. Math. Softw. 43(2), 14:1\u201314:23 (2016)","journal-title":"ACM Trans. Math. Softw."},{"key":"1002_CR26","doi-asserted-by":"crossref","first-page":"124626","DOI":"10.1016\/j.amc.2019.124626","volume":"363","author":"NK Linh","year":"2019","unstructured":"Linh, N.K., Song, C., Ryu, J., An, P.T., Hoang, N.D., Kim, D.S.: Quickhulldisk: a faster convex hull algorithm for disks. Appl. Math. Comput. 363, 124626 (2019)","journal-title":"Appl. Math. Comput."},{"key":"1002_CR27","doi-asserted-by":"crossref","unstructured":"L\u00f3pez, C.O., Beasley, J.E.: A formulation space search heuristic for packing unequal circles in a fixed size circle in a fixed size circular container. Eur. J. Oper. Res. pp. 1\u201310 (2015)","DOI":"10.1016\/j.ejor.2015.10.062"},{"key":"1002_CR28","volume-title":"An Introduction to Solid Modeling","author":"M M\u00e4ntyl\u00e4","year":"1988","unstructured":"M\u00e4ntyl\u00e4, M.: An Introduction to Solid Modeling. W.H. Freeman & Company, New York (1988)"},{"key":"1002_CR29","volume-title":"Spatial Tessellations: Concepts and Applications of Voronoi Diagrams","author":"A Okabe","year":"1999","unstructured":"Okabe, A., Boots, B., Sugihara, K., Chiu, S.N.: Spatial Tessellations: Concepts and Applications of Voronoi Diagrams, 2nd edn. Wiley, Chichester (1999)","edition":"2"},{"issue":"6","key":"1002_CR30","doi-asserted-by":"publisher","first-page":"1182","DOI":"10.1090\/S0002-9904-1978-14553-4","volume":"84","author":"R Osserman","year":"1978","unstructured":"Osserman, R.: The isoperimetric inequality. Bull. Am. Math. Soc. 84(6), 1182\u20131238 (1978)","journal-title":"Bull. Am. Math. Soc."},{"key":"1002_CR31","doi-asserted-by":"publisher","unstructured":"Pankratov, A., Romanova, T., Litvinchev, I.: Packing ellipses in an optimized rectangular container. Wireless Netw. https:\/\/doi.org\/10.1007\/s11276-018-1890-1 (2018)","DOI":"10.1007\/s11276-018-1890-1"},{"key":"1002_CR32","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-1098-6","volume-title":"Computational Geometry: An Introduction","author":"FP Preparata","year":"1985","unstructured":"Preparata, F.P., Shamos, M.I.: Computational Geometry: An Introduction. Springer, New York (1985)"},{"key":"1002_CR33","doi-asserted-by":"crossref","unstructured":"Rappaport, D.: A convex hull algorithm for discs, an application. Comput. Geom. Theory Appl. 3(1), (1992)","DOI":"10.1016\/0925-7721(92)90015-K"},{"key":"1002_CR34","doi-asserted-by":"publisher","unstructured":"Romanova, T., Litvinchev, I., Pankratov, A.: Packing ellipsoids in an optimized cylinder. Eur. J. Oper. Res. https:\/\/doi.org\/10.1016\/j.ejor.2020.01.051 (2020)","DOI":"10.1016\/j.ejor.2020.01.051"},{"key":"1002_CR35","doi-asserted-by":"publisher","first-page":"125076","DOI":"10.1016\/j.amc.2020.125076","volume":"375","author":"J Ryu","year":"2020","unstructured":"Ryu, J., Lee, M., Kim, D., Kallrath, J., Sugihara, K., Kim, D.S.: VOROPACK-D: Real-time disk packing algorithm using Voronoi diagram. Appl. Math. Comput. 375, 125076 (2020). https:\/\/doi.org\/10.1016\/j.amc.2020.125076","journal-title":"Appl. Math. Comput."},{"issue":"2","key":"1002_CR36","doi-asserted-by":"publisher","first-page":"448","DOI":"10.1137\/0214034","volume":"14","author":"M Sharir","year":"1985","unstructured":"Sharir, M.: Intersection and closest-pair problems for a set of planar discs. SIAM J. Comput. 14(2), 448\u2013468 (1985)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"1002_CR37","doi-asserted-by":"publisher","first-page":"283","DOI":"10.1007\/s10898-015-0331-2","volume":"65","author":"Y Stoyan","year":"2016","unstructured":"Stoyan, Y., Pankratov, A., Romanova, T.: Quasi-phi-functions and optimal packing of ellipses. J. Glob. Optim. 65(2), 283\u2013307 (2016)","journal-title":"J. Glob. Optim."},{"issue":"4","key":"1002_CR38","first-page":"380","volume":"12","author":"K Sugihara","year":"1989","unstructured":"Sugihara, K., Iri, M.: A solid modelling system free from topological inconsistency. J. Inf. Process. 12(4), 380\u2013393 (1989)","journal-title":"J. Inf. Process."},{"issue":"3","key":"1002_CR39","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1007\/BF03167582","volume":"21","author":"K Sugihara","year":"2004","unstructured":"Sugihara, K., Sawai, M., Sano, H., Kim, D.S., Kim, D.: Disk packing for the estimation of the size of a wire bundle. Jpn. J. Ind. Appl. Math. 21(3), 259\u2013278 (2004)","journal-title":"Jpn. J. Ind. Appl. Math."},{"key":"1002_CR40","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1007\/BF02187890","volume":"2","author":"CK Yap","year":"1987","unstructured":"Yap, C.K.: An $${O}(n \\log n)$$ algorithm for the Voronoi diagram of a set of simple curve segments. Dis. Comput. Geom. 2, 365\u2013393 (1987)","journal-title":"Dis. Comput. Geom."},{"issue":"2","key":"1002_CR41","doi-asserted-by":"publisher","first-page":"615","DOI":"10.1016\/j.ejor.2015.09.001","volume":"250","author":"Z Zeng","year":"2016","unstructured":"Zeng, Z., Yu, X., He, K., Huang, W., Fu, Z.: Iterated tabu search and variable neighborhood descent for packing unequal circles into a circular container. Eur. J. Oper. Res. 250(2), 615\u2013627 (2016)","journal-title":"Eur. J. Oper. Res."}],"container-title":["Journal of Global Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10898-021-01002-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10898-021-01002-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10898-021-01002-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,31]],"date-time":"2023-10-31T20:12:50Z","timestamp":1698783170000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10898-021-01002-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,3,19]]},"references-count":41,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,7]]}},"alternative-id":["1002"],"URL":"https:\/\/doi.org\/10.1007\/s10898-021-01002-5","relation":{},"ISSN":["0925-5001","1573-2916"],"issn-type":[{"type":"print","value":"0925-5001"},{"type":"electronic","value":"1573-2916"}],"subject":[],"published":{"date-parts":[[2021,3,19]]},"assertion":[{"value":"3 July 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 February 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 March 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}