Given a set P of n 2D points and a length K, what is the maximum number of points we can enclose in a polygon whose perimeter has length less than or equal to K?
For example, if we have a unit square with points on the corners, then:
- For
K < 2, we cannot enclose any points. - For
2 <= K < 2 + sqrt(2), we can enclose at most two points. - For
2 + sqrt(2) <= K < 4, we can enclose three points. - For
K >= 4, we can enclose all four points.
If we assume the optimal shape is a convex hull, we can try brute force. But, that solution is not very efficient. I'm not sure how to go about finding the most optimal correct solution.
def brute_force(P: Set[Tuple[int, int]], K: int) -> int:
def all_subsets():
for n in range(len(P), 0, -1):
for C in itertools.combinations(P, n):
yield C
for C in all_subsets():
if perimeter(convex_hull(C)) <= K:
return len(C)
return 0
There are various greedy approaches that incrementally expand or contract from the convex hull, but it's not clear how to prove optimality or whether these approaches even find the right answers.
One approach would be to choose three starting points and then greedily add points to their convex hull, choosing whichever next point increased the convex hull's perimeter the least. But, I'm not sure how to prove optimality for this approach, or if it's the most efficient. It's also a bit brute force-y because we need to try every combination of three starting points.
