Suppose I have N points (labeled 1, 2, ..., k, ..., N) in D dimensions. I'd like to choose the order of points such that, after each point, the volume of the convex hull is maximized.

In other words, the volume of the convex hull is a function of the number of points V(k) (V(1) = V(2) = 0), I'd like to choose the sequence of points {k_1, k_2, ..., k_N} such that V(k) is maximized for each value of k.

The two algorithms I've thought of don't seem very efficient:

  • Brute force is O(N!)
  • Divide the space into boxes, bounded by the k points. Pick a point, then look in each of the little boxes, ordered by how far away they are from the box that contains the starting point. If there are multiple points in the box you choose, either randomly pick, or choose the point that's the furthest away. Now compute the centroid of the points you have. Then repeat until all points are consumed. This seems like O(N^p).

Is there a cute, out of the box solution to this problem? Or a paper where someone has solved it already?

  • $\begingroup$ This strikes me as pretty interesting, but I suspect it belongs elsewhere. $\endgroup$ – Ben Reiniger Jun 28 '19 at 20:54

Genetic algorithms are often a good option for optimization problems, assuming it's not a requirement for the solution to be the best one but only to be "close enough".

| improve this answer | |

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.