Choose points to maximize volume of convex hull

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?