Authors: HeeKap Ahn Otfried Cheong
Publish Date: 2010/11/03
Volume: 62, Issue: 1-2, Pages: 464-479
Abstract
Given two compact convex sets P and Q in the plane we consider the problem of finding a placement ϕ P of P that minimizes the convex hull of ϕ P∪Q We study eight versions of the problem we consider minimizing either the area or the perimeter of the convex hull we either allow ϕ 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 nearlinear time algorithms for all versions of the problem In the case with reorientations we compute a 1+εapproximation in time Oε −1/2log n+ε −3/2log a 1/ε if the two sets are convex polygons with n vertices in total where a∈012 depending on the version of the problemHK Ahn was supported by the National Research Foundation of Korea Grant funded by the Korean Government MEST NRF20090067195 O Cheong was supported by Midcareer Researcher Program through NRF grant funded by the MEST No R012008000116070
Keywords: