BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Computational Optimisation Group - ECPv6.15.11//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-WR-CALNAME:Computational Optimisation Group
X-ORIGINAL-URL:http://optimisation.doc.ic.ac.uk
X-WR-CALDESC:Events for Computational Optimisation Group
REFRESH-INTERVAL;VALUE=DURATION:PT1H
X-Robots-Tag:noindex
X-PUBLISHED-TTL:PT1H
BEGIN:VTIMEZONE
TZID:UTC
BEGIN:STANDARD
TZOFFSETFROM:+0000
TZOFFSETTO:+0000
TZNAME:UTC
DTSTART:20170101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=UTC:20181116T150000
DTEND;TZID=UTC:20181116T160000
DTSTAMP:20260419T040435
CREATED:20181001T084447Z
LAST-MODIFIED:20181001T084617Z
UID:1158-1542380400-1542384000@optimisation.doc.ic.ac.uk
SUMMARY:Seminar: Arrangements of Circles and Spheres leading to Convex Hulls with Minimal Boundaries
DESCRIPTION:Title: Arrangements of Circles and Spheres leading to Convex Hulls with Minimal Boundaries\nSpeaker: Dr Josef Kallrath\nAffiliation: Advanced Business Analytics\, BASF SE\, Germany\nLocation: 218 Huxley Building\nTime: 15:00 – 16:00 \nAbstract. 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. \nA 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. \nIn 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 %. \nIn 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. \nFor 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.
URL:http://optimisation.doc.ic.ac.uk/event/seminar-arrangements-of-circles-and-spheres-leading-to-convex-hulls-with-minimal-boundaries/
END:VEVENT
END:VCALENDAR