TransWikia.com

Choose points to maximize volume of convex hull

Data Science Asked by BenDundee on August 30, 2021

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?

One Answer

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".

Answered by Erwan on August 30, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP