给定周长K，求可包围最多二维点的凸包最优解法探讨

给定包含n个二维点的集合P和长度阈值K，核心需求是找到周长不超过K的多边形，使其能包围点集P中的点数最多。

示例说明 #

以单位正方形的4个顶点构成的点集为例：

• 当K < 2时，无法包围任何点；
• 当2 ≤ K < 2 + √2时，最多可包围2个点；
• 当2 + √2 ≤ K < 4时，最多可包围3个点；
• 当K ≥ 4时，可包围全部4个点。

现有解法分析 #

假设最优包围形状为凸包的前提下，暴力法是最直接的实现方式，但效率极低。目前探索最优解法的过程中存在以下局限：

• 多种基于凸包增量扩展或收缩的贪心策略，均无法证明其最优性；
• 另一种思路是选取三个起始点，每次添加使凸包周长增幅最小的点，但需要遍历所有三点组合，仍带有暴力属性，同样无法证明其最优性。

暴力法实现代码 #

import itertools

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():
        # 假设convex_hull和perimeter是已实现的辅助函数
        if perimeter(convex_hull(C)) <= K:
            return len(C)

    return 0

内容的提问来源于stack exchange，提问作者user21381354