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

Given a set of points we have to find the maximum number of simple polygons which all lie inside one another (Basically be kind of concentric) .

And it is not important to select all points.

c++algorithmgeometryconvex-hull


Solution 1:[1]

Build convex hull for all points.

Remove points belonging to the hull.

Repeat for the next layer and so on ("onion peeling" approach)

enter image description here

Note there is O(nlogn) algorithm for building all convex layers cited here

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

Sources

This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.

Source: Stack Overflow

Solution Source
Solution 1 MBo

Related Questions