Title: Arrangements of Circles and Spheres leading to Convex Hulls with Minimal Boundaries
Speaker: Dr Josef Kallrath
Affiliation: Advanced Business Analytics, BASF SE, Germany
Location: 218 Huxley Building
Time: 15:00 – 16:00
Abstract. We present and solve a new computational geometry optimization problem in 2D and 3D and provide theoretical insights. Circles (2D) and Spheres (3D) with given radii should be arranged in such a way that a) they do not overlap and b) the length of the perimeter or surface area, resp., of the boundary ∂S of the convex hull S enclosing the spheres is minimized. An additional constraint could be to fit the spheres into a specified geometry, e.g., a rectangle or a rectangular solid, respectively.
A motivation for the 2D problem is a rope to be minimized, which encloses the circles, where the circles could be the base of cylinders loaded an a truck with rectangular loading area.
In 2D, ∂S is established by line segments and circular arcs. To tackle the problem, we derive a non-convex mixed-integer non-linear programming (MINLP) formulation. We exploited the isoperimetric inequality to get a tighter lower bound for the perimeter than the lower bound obtained by the relaxation of the MINLP. As demonstrated in numerical experiments, problem instances with only congruent circles are computational better tractable than non-congruent instances, as for congruent instances only the line segments have to be minimized. For small instances with up to five non-congruent circles, and minimizing only lL the MINLP problems we obtained gaps smaller than 10−4 with the current state-of-the-art global solvers BARON and LINDO available in GAMS. For larger problems of up to 90 circles, the relative gap between the upper and lower bound provided by the global solvers remains larger than 7 %.
In 3D, ∂S consists of spherical polygons with k vertices formed by k arcs of great circles, triangles and truncated cones. Here, we take a different approach than in the 2D situation. Similarly as in modeling the surface of eclipsing binary stars, we cover the surface of the spheres by a grid of approximately uniformly distributed points using spherical coordinates. We derive closed non-convex NLP models for this sphere arrangement problem.
For two spheres, we prove that the minimal area of ∂S is identical to the sum of the surface areas of the two spheres. For special configurations of spheres we provide theoretical insights and compute analytically minimal area configurations. Numerically, we have solved problems containing up to 200 spheres using a polylithic modeling and solution approach.