平面上n个general position点的最小stabbing set规模求解问题

让我们来拆解这个平面几何里的戳刺集问题：

先明确核心定义：在平面上放置n个处于一般位置（任意三点不共线）的点，称一个点集S为「stabbing集（戳刺集）」，如果由这n个点构成的每一个三角形的内部都至少包含S中的一个点。我们的目标是，对每个n，找到最小的N，使得无论这n个点怎么摆放（只要满足一般位置），总能存在一个规模为N的stabbing集。

接下来梳理关键分析和结论：

• 凸包的影响：假设这n个点的凸包是一个b边形，对这个点集做任意三角剖分后，会得到 2n - b - 2 个三角形。从基本逻辑来看，每个三角形至少需要一个点来“戳刺”，因此任何stabbing集的规模都至少是这个数值。
• 极端情况验证：当凸包就是n边形（所有点都在凸包上，构成凸多边形）时，代入公式得到 2n - n - 2 = n - 2，而这个数量确实足够——比如在凸多边形内部放置n-2个点，让每个三角剖分出来的三角形内部都有一个点，就能保证所有由凸多边形顶点构成的三角形内部都包含至少一个戳刺点。
• 通用情况推测：综合来看，2n - b - 2这个数值似乎适用于所有情况——不管这n个点的凸包是几边形，我们总能构造出一个规模为这个数的stabbing集，满足所有三角形都被戳刺的要求。

备注：内容来源于stack exchange，提问作者Kangaroo976