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.

$\endgroup$
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."

$\endgroup$
2

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.