# Simplices in convex polytopes

This question is a direct generalization of:

Counting the (additive) decompositions of a quadratic, symmetric, empty-diagonal and constant-line matrix into permutation matrices

Given a convex polytope $P \in \mathbb{R}^d,$ and a point $p\in P,$ how many simplices $S$ are there such that the $S$ is the convex hull of some $d+1$ vertices of $P$ and such that $p \in S?$

I assume that this is $\#P$-complete...

-
Could you formulate this more precisely as a computational complexity problem? Otherwise, I don't think it's a real question. – Ian Agol Sep 9 '11 at 14:37

There are two ways to state this question, and the answers differ.

1) Let the dimension $d$ is fixed, and the input is via $n$ vertices of the polytopes. In this case the total number of possible simplices is polynomial, and so is the counting problem.

2) If the dimension $d$ is arbitrary, everything falls apart. Think of a simplex with vertices $O=(0,\ldots,0)$ and $(0,\ldots,a,\ldots,0)$, where $a\in$ {$a_1,\ldots,a_m$}. Here $n=dm+1$. Let $z=(c,\ldots,c)$ and consider all (closed) simplices which contain $z$. Check that #simplices containing O is a variation on the #knapsack problem, several versions of which are known to be #P-complete. I omit the details.

-
These are good points, though, in the interest of completeness, there is (at least) one more way to state the question: the polytope may be given by bounding hyperplanes, in which case (correct me if I am wrong), the question is not (obviously) polynomial even in fixed dimension. My guess is that is sharp-P complete then. – Igor Rivin Oct 19 '11 at 9:38
No, actually if you have N hyperplanes, you have at most $N^d$ vertices, and thus $N^{d^2}$ possible simplices to check, polynomial again for a fixed $d$. You guess is wrong. Now, where is my "accept"? :) – Igor Pak Oct 20 '11 at 0:47