CGAL users discussion list

["Cassio P. de Campos" <>]

Hi, all.

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. My second question is
about an implementation of that. Is the lrs package from David Avis a
good option? If not, which is it? How does the implementation in cgal
compares to that? I understand that any code for convex hull or for
facets-vertex enumeration can do the job, however most implementations
are not really optimized for the problem, e.g. convex hull codes
generally output facets, vertex enumeration ideas usually assume that
a hyperplane-based representation is given (which I could generate,
but I would lose time and info that I have about the points), etc. So
is there an implementation that does not output unnecessary info and
directly works with points, if that is at all possible?

Many thanks,

cassio.