# 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

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.
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