Given a (convex) lattice polytope, suppose we want to list or count all (convex) lattice polytopes (of the same dimension) contained in it. Are there efficient ways to do this?
$\begingroup$
$\endgroup$
3
-
$\begingroup$ Define efficient. If you start with a simplex of $n$ vertices, then you would have $2^n-1$ subsets of the vertices, that all span different simplices. So listing them will be exponential. $\endgroup$– Per AlexanderssonApr 2, 2014 at 14:05
-
$\begingroup$ This is not exactly what I meant, I am interested in polytopes that are of the same dimension as the containing polytope, so facets do not count. As for efficiency, I meant more in the sense of an algorithm that doesn't just go over all possible subsets of lattice points in the given polytope, and then discards duplicates. This is for the list. For the number of such polytopes, it would be interesting to give some bound on the number of contained polytopes. $\endgroup$– wishcowApr 2, 2014 at 18:18
-
$\begingroup$ It's easy to modify Per Alexandersson's suggestion so that the polytopes are the same dimension. If there are $n$ vertices of a convex hull, and some tetrahedron $T$ contained in the interior, then a subset of the vertices $S$ is determined by the convex hull of $S\cup T$, so there are at least $2^n$. $\endgroup$– Douglas ZareApr 3, 2014 at 1:41
Add a comment
|
1 Answer
$\begingroup$
It seems that it should be possible to enumerate all contained lattice polytopes by systematically peeling away the boundary vertices in this fashion. However, I am not seeing at the moment how to do this in a way that counts each enclosed polytope exactly once each.
$\endgroup$
An observation, and a remark.
For a polytope $P = \mathrm{conv} V$ with vertices $V$, let $S \subset V$ be an independent set of vertices, i.e., independent in the 1-skeleton graph of $P$. Then, if $|S|=k$, one can form $2^k-1$ internal lattice polytopes by removing (or not) each vertex of $S$ from $V$ and finding the convex hull of the remaining vertices of $V$ and the enclosed lattice points. For example, below $\{ v_1, v_2 \}$ forms an independent set.
It seems that it should be possible to enumerate all contained lattice polytopes by systematically peeling away the boundary vertices in this fashion. However, I am not seeing at the moment how to do this in a way that counts each enclosed polytope exactly once each.
answered Apr 3, 2014 at 11:35