6
$\begingroup$

What are efficient methods (polytime) to compute an approximation of the convex hull in high dimension (say, $30000$) for a given set of points?

Edit: I am looking for an algorithm for getting the hyperplanes that define the convex hull, not the extreme points that are the vertices of the convex hull.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
5
$\begingroup$

This recent paper

Sartipizadeh, Hossein, and Tyrone L. Vincent. "Computing the Approximate Convex Hull in High Dimensions." arXiv:1603.04422 (2016).

includes a summary of previous work on approximate convex hulls. The time complexity of their algorithm is independent of the dimension, and quadratic in the number of points. "The proposed algorithm uses a greedy method to attempt to find the best approximation to the convex hull for a given number of vertices."

Improve this answer
$\endgroup$
2

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .