Packing circles into perimeter-minimizing convex hulls

Josef Kallrath () and Markus M. Frey ()
Additional contact information
Josef Kallrath: BASF SE, Advanced Business Analytics, G-FSS/OAO-B009
Markus M. Frey: BASF SE, Advanced Business Analytics, G-FSS/OAO-B009

Journal of Global Optimization, 2019, vol. 73, issue 4, No 3, 723-759

Abstract: Abstract We present and solve a new computational geometry optimization problem in which a set of circles with given radii is to be arranged in unspecified area such that the length of the boundary, i.e., the perimeter, of the convex hull enclosing the non-overlapping circles is minimized. The convex hull boundary is established by line segments and circular arcs. To tackle the problem, we derive a non-convex mixed-integer non-linear programming formulation for this circle arrangement or packing problem. Moreover, we present some theoretical insights presenting a relaxed objective function for circles with equal radius leading to the same circle arrangement as for the original objective function. If we minimize only the sum of lengths of the line segments, for selected cases of up to 10 circles we obtain gaps smaller than $$10^{-4}$$ 10 - 4 using BARON or LINDO embedded in GAMS, while for up to 75 circles we are able to approximate the optimal solution with a gap of at most $$14\%$$ 14 % .

Keywords: Global optimization; Non-convex nonlinear programming; Circular packing problem; Convex hull; Perimeter minimization; Non-overlap constraints; Computational geometry; Isoperimetric inequality (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10898-018-0724-0 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jglopt:v:73:y:2019:i:4:d:10.1007_s10898-018-0724-0

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10898

DOI: 10.1007/s10898-018-0724-0

Access Statistics for this article

Journal of Global Optimization is currently edited by Sergiy Butenko

More articles in Journal of Global Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().