如何从给定的一组点计算同心多边形的最大数量?

How to calculate the maximum number of concentric polygons from a given set of points?

给定一组点,我们必须找到最大数量的简单多边形,这些多边形都位于彼此内部(基本上是同心的)。

而且select所有点都不重要。

为所有点构建凸包。

删除属于船体的点。

重复下一层等("onion peeling"方法)

请注意,有 O(nlogn) 算法用于构建引用的所有凸层 here

Chazelle, Bernard (1985), "On the convex layers of a planar set", IEEE Trans. Inf. Theory, 31 (4): 509–517,