Bundling two simple polygons to minimize their convex hull

Abstract

Given two simple polygons P and Q in the plane, we study the problem of finding a placement ?P of P such that ?P and Q are disjoint in their interiors and the convex hull of their union is minimized. We present exact algorithms for this problem that use much less space than the complexity of the Minkowski sum of P and Q. When the orientation of P is fixed, we find an optimal translation of P in O(n2m2 log n) time using O(nm) space, where n and m (n �� m) denote the number of edges of P and Q, respectively. When we allow reorienting P, we find an optimal rigid motion of P in O(n3m3 log n) time using O(nm) space. In both cases, we find an optimal placement of P using linear space at the expense of slightly increased running time. For two polyhedra in three dimensional space, we find an optimal translation in O(n3m3 log n) time using O(nm) space or in O(n3m3(m + log n)) time using linear space. ? Springer International Publishing AG 2017.