Given N points in a 2D plane, if we start at a given point and start including points in a set ordered by their distance from the starting point. After including every point, we check if there is a convex hull possible, we move all these points to a visited set and continue. Every time we determine a convex hull, we only move the points to the visited set if the so constructed convex hull contains all the points from the visited set.
How can we do count such convex hulls in as efficient manner as possible?

  • $\begingroup$ What do you mean by "check if there is a convex hull possible"? There is always a convex hull of any set of points. Which points are you computing the convex hull of? Can you write concise pseudocode, and elaborate on terms like that? $\endgroup$ – D.W. Jun 7 '20 at 23:52
  • $\begingroup$ Apart from the precise definition, I'm not sure when you'd consider a pair of convex hulls to be 'concentric', given that I'm not sure what 'the' center of a convex hull should be (the centroid? the center of its minimum enclosing disk?). The idea of convex layers seems related, but that is quite different from the procedure you describe here. $\endgroup$ – Discrete lizard Jun 8 '20 at 9:03

It seems you are trying to perform onion peeling(convex layers) from the inside out, which is not possible. A convex hull of given points is a polygon that contains all given points either on itself or inside it. To solve the problem you have described you must generate a convex hull using an algorithm of choice. Now that you have the outer layer, for the inner layer, use the same algorithm and only supply the points inside the convex hull.

The pseudo code would be:
 for given dataset:
   generate a convex hull
   remove the points that make the convex hull from the dataset
   loop until the dataset has no points or more than 2(since a convex hull requires at least 3 points).

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.