Bundling Three Convex Polygons to Minimize Area or Perimeter

摘要

Given a set P = {P_0, ..., P_(k-1)} of k convex polygons having n vertices in total in the plane, we consider the problem of finding k translations T_0, ..., T_(k-1) of P_0,..., P_(k-1) such that the translated copies T_iP_i are pairwise disjoint and the area or the perimeter of the convex hull of U_(i=0)~(k-1) T_iP_i is minimized. When k = 2, the problem can be solved in linear time but no previous work is known for larger k except a hardness result: it is NP-hard if k is part of input. We show that for k = 3 the translation space of P_1 and P_2 can be decomposed into O(n~2) cells in each of which the combinatorial structure of the convex hull remains the same and the area or perimeter function can be fully described with O(1) complexity. Based on this decomposition, we present a first O(n~2 )-time algorithm that returns an optimal pair of translations minimizing the area or the perimeter of the corresponding convex hull.