CGAL users discussion list

[Marc Glisse <>]

On Tue, 25 Oct 2011, Cassio P. de Campos wrote:

> I am trying to find an algorithm particularly optimized for the
> following problem: given a set of points in R^d, find the extreme
> ones, that is, find the subset of points that cannot be written as a
> convex combination of the others. My first question is if somebody
> knows the fastest available idea (asymptotically speaking, based on
> input and output sizes) to solve the problem.

I believe the fastest ideas are based on linear programming, and testing 
for each point whether it is on the convex hull. There are some 
theoretical results to factor some of the computation between the linear 
programs, but testing each independently should do.

http://www.cgal.org/Manual/latest/doc_html/cgal_manual/QP_solver/Chapter_main.html#sec:QP-iterators

--
Marc Glisse