Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I have a set of lattice points S in R^n (listed in memory in a computer for n=8 say). I want to computationally certify that they do not form the lattice points of a convex polytope P in R^n. (Ex. S={-1,1} in R^1.) Is there an easy (and hopefully efficient enough) way to do this?

Remarks:

  • I don't have much feel for the (many) points themselves at the moment. For instance, I don't know what are vertices of the convex hull of S (or how to find that).

  • Assuming I could find a description of the convex hull, I get scared about a solution that says "now figure out what the lattice points are and compare with S", because of efficiency concerns.

Thank you!

share|improve this question
    
the procedure I suggest does not enumerate points, it only counts them. –  Dima Pasechnik Aug 3 '13 at 16:06
add comment

2 Answers

up vote 2 down vote accepted

You can compute the convex hull $P$ of these points, and then apply, say, Barvinok's algorithm for counting $|P\cap\mathbb{Z}^n|$. Comparing the latter with $|S|$ would give you the needed certificate. Although $n=8$ might be a bit too high for an existing implementation (e.g. LattE) to handle.

Another trick might be to compute the volume of $P$ - it will give you some bound on the number of integer vectors in $P$.

On can use Sage to compute the convex hull etc (note that it does not do integer points count efficiently, though). Here is a toy example:

l=LatticePolytope([[2,0],[0,2],[1,1]],compute_vertices=True); l; l.npoints()

A lattice polytope: 1-dimensional, 2 vertices.

3

share|improve this answer
    
Hi (and thanks) -- I was afraid of that answer. Actually, how does one go about actually obtaining a description of the convex hull of S? –  simpleperson Aug 3 '13 at 12:48
    
Two primary options for computing hulls in higher dimensions are Qhull and CGAL. Both require considerable study before you can use them. –  Joseph O'Rourke Aug 3 '13 at 13:03
    
@Joseph O'Rourke -- I looked a little at CGAL's manual which gave an idea. I want to take any two points x and y of S and show that any lattice point on the line xy is in S. This is a horrid, worse than |S| choose 2 algorithm but might be a quick enough (albeit dirty) way to just check (non)convexity. Is there any problem with that? –  simpleperson Aug 3 '13 at 13:53
    
one can use Sage to compute the convex hull. It can even be done online, without installing Sage on a local machine, using e.g. cloud.sagemath.org –  Dima Pasechnik Aug 3 '13 at 16:20
    
e.g. here is a toy example using Sage: l=LatticePolytope([[2,0],[0,2],[1,1]],compute_vertices=True); l; l.npoints() it will output A lattice polytope: 1-dimensional, 2 vertices. 3 –  Dima Pasechnik Aug 3 '13 at 16:34
add comment

To respond to your suggestion in your comment to Dima's answer: This set $S$ of four points in $\mathbb{Z}^2$ does "not form the lattice points of a convex polytope," and yet, for "any two points $x$ and $y$ of $S$," every "lattice point on the line [segment] $xy$ is in $S$":
          Lattice4Pts

share|improve this answer
    
You're right of course. Thank you. –  simpleperson Aug 3 '13 at 14:27
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.