Hi Nathann, On Wed, Feb 11, 2015 at 11:37:30AM +0100, Nathann Cohen wrote: > I am dealing with a problem for which I need to check quickly whether a set > of points is in convex position [1] in 2D and 3D. Sage seems to be able to > do that with the commands: > > sage: l = [(1,2),(3,4),(2,5)] > sage: p = Polyhedron(l) > sage: len(p.Vrepresentation()) == len(l) > True > > This is, however, very very very very slow. I also suspect that the > creation of a Polyhedron object is far from being cheap.
> > How do you guys think a quick "are_in_convex_position" function should be > written ? Which library should I call ? For 2D and 3D in particular ? one should have quick convex hull routines, I agree. >From it's output are_in_convex_position is trivial, and if we talk about an incremental algorithms (ones I talk below are like this) then it's trivial to have it stop early, if a non-convex-hull point is found. for 2D there are very quick algorithms known, e.g. O(n log n) running time for n points http://en.wikipedia.org/wiki/Graham_scan for 3D one still can be pretty efficient, cf e.g. http://dpd.cs.princeton.edu/Papers/BarberDobkinHuhdanpaa.pdf I don't know if PPL does any of these. If it does not, I'd suggest using CGAL, where these things work quite well, although it's a bit of a pain. (mostly due to its size, and dependence on advanced C++ features). It is, at least the relevant parts for this, under (L)GPL, so this should not be a problem. http://doc.cgal.org/latest/Manual/packages.html Best, Dima > > Thanks, > > Nathann > > P.S.: My points have integer coordinates. I don't know if that matters. > > [1] A set of points is in convex position if none of them is in the convex > hull of the others. -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To post to this group, send email to [email protected]. Visit this group at http://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
