Given a polygon $P$ and a set of predefined lines, I am looking for the subset of lines that creates the best fitting convex polygon with respect to $P$. In other words the area of an $\operatorname{XOR}$ operation of $P$ and the new polygon should be as small as possible.
Is there an algorithm to compute this subset in polynomial time without testing every combination?
From the comments:
So far I think I found a solution for a single side of the polygon by simply summing the distance of the associated vertices of this side to each line and choosing the one with the smallest value. But if I do this for each line, will the result be optimal?