Aligning Two Convex Figures to Minimize Area or Perimeter

Abstract

Given two compact convex sets P and Q in the plane, we consider the problem of finding a placement I center dot P of P that minimizes the convex hull of I center dot Pa(a)Q. We study eight versions of the problem: we consider minimizing either the area or the perimeter of the convex hull; we either allow I center dot P and Q to intersect or we restrict their interiors to remain disjoint; and we either allow reorienting P or require its orientation to be fixed. In the case without reorientations, we achieve exact near-linear time algorithms for all versions of the problem. In the case with reorientations, we compute a (1+epsilon)-approximation in time O(epsilon (-1/2)log n+epsilon (-3/2)log (a) (1/epsilon)) if the two sets are convex polygons with n vertices in total, where aa{0,1,2} depending on the version of the problem.