Optimal Translation Covers for Colored Line Segments

We study a variant of the translation cover problem for colored line segments in the plane. For each color i∈{1,…,k}, we are given a set Si of n line segments, and the goal is to choose one segment from each color class so that the selected segments have the smallest possible translation cover area. Equivalently, the selected segments may be translated independently, and we minimize the area of the convex hull of their translated copies. We give algorithms for every fixed number k>1 of colors. For k=2, we obtain an O(nlogn)-time algorithm using O(n) space. For k=3, we obtain a deterministic O(n2logn)-time algorithm and a randomized algorithm with expected O(n2) running time; both use O(n) space. For k=4, we obtain an O(n4)-time algorithm using O(n) space. For every fixed k>4, we obtain an O(n4logn)-time algorithm using O(n2polylogn) space, thereby avoiding the enumeration of all nk colorful selections.