1

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 to scale like the number of points to some power.

Is there a cute, out of the box solution to this problem? Or a paper where someone has solved it already? Or (dare I ask) a python package that I can just import?

BenDundee
  • 659
  • 3
  • 8
  • 17
  • You will either need to have $D=2$, or $V(1)=\dots=V(D)=0$, since you need at least $D+1$ points in $D$ dimensions to get a non-degenerate convex hull. – Stephan Kolassa Jun 28 '19 at 15:55
  • Yes, I understand that. Suppose I have 1000 points in 40 dimensions then. – BenDundee Jun 28 '19 at 16:21
  • If you maximize the volume with k points, the convex hull of maximum volume with k+1 points might easily include none of those k – Glen_b Jun 29 '19 at 07:11

0 Answers0