Re: [sage-support] Re: Checking for convexity of Lattice Polytopes
Am 24.02.2011 19:29, schrieb Dmitri: A chosen set of points is convex if it is equal to its convex hull. as far as I see this is equivalent to, all points are on a facet of the polytope. I think my problem is actually doing the comparison. So I have this chosen set of points which I don't know is convex. I compute its convex hull. Now how do I compare these two objects? Dmitri you can try someting like this: len([i for i in range(foo.npoints()) if any([i in face.points() for face in foo.facets()])]) == foo.npoints() ths is not a nice way to do but it works. maybe it would be nice to put this into a property of a latticepolytope. some littel explanation to the piece of code: we count all points of foo, which lay on some facet of foo. (those points are just numbered and you can get the value of it by foo.point(index) but this doesnt matter here because they are indexed in by the same number in the facets too) and compare them to the total number of points in foo (and on its boundary) As long as my comment above is correct (and as long as I got the point of your problem) this should work. greatz Johannes -- To post to this group, send email to sage-support@googlegroups.com To unsubscribe from this group, send email to sage-support+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-support URL: http://www.sagemath.org
[sage-support] Re: Checking for convexity of Lattice Polytopes
On Mar 1, 2:11 pm, Volker Braun vbraun.n...@gmail.com wrote: I agree with your example, of course. But I interpreted Dmitri's question somewhat differently, that he wants to start with some set of lattice points and find out if they all lattice points of the convex hull. Though thinking about it, your answer is probably what he meant. Can you suggest an answer to the refined question? That is, given a union of convex lattice polytopes, is there a way to check whether that union is itself convex using Sage? What if instead of a union of polytopes we have a list of equations defining the boundary of a region? UAW -- To post to this group, send email to sage-support@googlegroups.com To unsubscribe from this group, send email to sage-support+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-support URL: http://www.sagemath.org
[sage-support] Re: Checking for convexity of Lattice Polytopes
One solution would be to compute the volume of P, Q, and intersect(P,Q). All three are convex, so its easy enough to compute the volumes. Then Vol(union(P,Q)) = Vol(P) + Vol(Q) - Vol(intersect(P,Q)) = Vol(conv(P,Q)) with equality if and only if union(P,Q) is already convex. I don't quite understand the second part, a list of equations is just some hyperplane arrangement. This will have many polyhedral cells... -- To post to this group, send email to sage-support@googlegroups.com To unsubscribe from this group, send email to sage-support+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-support URL: http://www.sagemath.org
[sage-support] Re: Checking for convexity of Lattice Polytopes
On Feb 24, 10:57 am, Volker Braun vbraun.n...@gmail.com wrote: On Thursday, February 24, 2011 6:29:11 PM UTC, Dmitri wrote: I think my problem is actually doing the comparison. So I have this chosen set of points which I don't know is convex. I compute its convex hull. Now how do I compare these two objects? Assuming that we are still talking about lattice polytopes: check that LatticePolytope(points).npoints() is the same as the number of points you started with. This won't always work. Suppose you have a lattice polygon P with vertices (-1, 1), (-1,0), (0,0), and (1,1), and another lattice polygon Q with vertices (-1,0), (-1,-1), (1,-1), and (1,0). Let R be the union of P and Q. Then R is not convex: it looks like a square with a triangle cut out of it. But R and its convex hull contain the same lattice points. UAW -- To post to this group, send email to sage-support@googlegroups.com To unsubscribe from this group, send email to sage-support+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-support URL: http://www.sagemath.org
[sage-support] Re: Checking for convexity of Lattice Polytopes
On Tuesday, March 1, 2011 9:55:01 PM UTC, Ursula Whitcher wrote: This won't always work. I agree with your example, of course. But I interpreted Dmitri's question somewhat differently, that he wants to start with some set of lattice points and find out if they all lattice points of the convex hull. Though thinking about it, your answer is probably what he meant. -- To post to this group, send email to sage-support@googlegroups.com To unsubscribe from this group, send email to sage-support+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-support URL: http://www.sagemath.org
[sage-support] Re: Checking for convexity of Lattice Polytopes
A chosen set of points is convex if it is equal to its convex hull. So all you have to do is compute the hull and compare with it. I think my problem is actually doing the comparison. So I have this chosen set of points which I don't know is convex. I compute its convex hull. Now how do I compare these two objects? Dmitri On Feb 23, 4:29 pm, Volker Braun vbraun.n...@gmail.com wrote: On Thursday, February 24, 2011 12:12:12 AM UTC, Dmitri wrote: [...] The intersection of all these equations forms a lattice polytope (finite and bounded). I want to know if that polytope is convex or not. I'm confused. Intersections of convex sets are convex. [...] One question that I'm interested is what results when we take the union of two tops. One obvious question to ask is whether it's convex or not. A chosen set of points is convex if it is equal to its convex hull. So all you have to do is compute the hull and compare with it. Volker -- To post to this group, send email to sage-support@googlegroups.com To unsubscribe from this group, send email to sage-support+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-support URL: http://www.sagemath.org
[sage-support] Re: Checking for convexity of Lattice Polytopes
On Thursday, February 24, 2011 6:29:11 PM UTC, Dmitri wrote: I think my problem is actually doing the comparison. So I have this chosen set of points which I don't know is convex. I compute its convex hull. Now how do I compare these two objects? Assuming that we are still talking about lattice polytopes: check that LatticePolytope(points).npoints() is the same as the number of points you started with. -- To post to this group, send email to sage-support@googlegroups.com To unsubscribe from this group, send email to sage-support+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-support URL: http://www.sagemath.org
[sage-support] Re: Checking for convexity of Lattice Polytopes
Thanks for the quick response. My question is somewhat different. Specifically, I have a set of equations that define each facet of some polytope. The intersection of all these equations forms a lattice polytope (finite and bounded). I want to know if that polytope is convex or not. If it helps to think of a specific scenario: I'm working with tops of reflexive polytopes. One question that I'm interested is what results when we take the union of two tops. One obvious question to ask is whether it's convex or not. Thanks, Dmitri On Feb 21, 4:48 pm, Volker Braun vbraun.n...@gmail.com wrote: Polyhedron and Polytope (=compact Polyhedron) implies convex. For example: sage: lp = LatticePolytope(matrix([[-1,-1], [-1,0], [0,0], [1,0], [1,-1]]).transpose()) sage: lp.points() [-1 -1 1 1 0 0] [-1 0 0 -1 -1 0] sage: lp.vertices() [-1 -1 1 1] [-1 0 0 -1] -- To post to this group, send email to sage-support@googlegroups.com To unsubscribe from this group, send email to sage-support+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-support URL: http://www.sagemath.org
[sage-support] Re: Checking for convexity of Lattice Polytopes
On Thursday, February 24, 2011 12:12:12 AM UTC, Dmitri wrote: [...] The intersection of all these equations forms a lattice polytope (finite and bounded). I want to know if that polytope is convex or not. I'm confused. Intersections of convex sets are convex. [...] One question that I'm interested is what results when we take the union of two tops. One obvious question to ask is whether it's convex or not. A chosen set of points is convex if it is equal to its convex hull. So all you have to do is compute the hull and compare with it. Volker -- To post to this group, send email to sage-support@googlegroups.com To unsubscribe from this group, send email to sage-support+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-support URL: http://www.sagemath.org
[sage-support] Re: Checking for convexity of Lattice Polytopes
Polyhedron and Polytope (=compact Polyhedron) implies convex. For example: sage: lp = LatticePolytope(matrix([[-1,-1], [-1,0], [0,0], [1,0], [1,-1]]).transpose()) sage: lp.points() [-1 -1 1 1 0 0] [-1 0 0 -1 -1 0] sage: lp.vertices() [-1 -1 1 1] [-1 0 0 -1] -- To post to this group, send email to sage-support@googlegroups.com To unsubscribe from this group, send email to sage-support+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-support URL: http://www.sagemath.org