CGAL users discussion list

[Marc Glisse <>]

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

> Thanks for the fast reply, and sorry for insisting, but I'm really in
> need of the best possible solution and I might be very well missing
> something.
>
> Please correct if I am wrong: the linear programs you mention might
> take time O(n^3), n number of points (let's suppose n ~ d, d is the
> dimension), just to check a single point (so it would take O(n^4) to
> solve the problem I described). On the other hand,
> http://cgm.cs.mcgill.ca/%7Eavis/doc/avis/Av98a.pdf mentions O(n d) <
> O(n^2) for simple polyhedra and O(n^2 d) otherwise, for each extreme
> point. That's mainly because it is like if we executed a single linear
> program run (and doing the reverse search) while keeping the extremes
> that are found while pivoting. Am I missing something?

I never looked into the details, so I may be wrong. Here is a recent 
cgal-related work on the subject:

http://e-collection.library.ethz.ch/view/eth:2225

> I am not sending this email to the list because the question might be
> too detailed, anyway I don't know if that's the proper think to do.

Rule of thumb: never send personal replies.

--
Marc Glisse