On the number of tetrahedra with minimum, unit, and distinct volumes in three-space

Abstract

We formulate and give partial answers to several combinatorial problems on volumes of simplices determined by $n$ points in 3-space, and in general in $d$ dimensions. (i) The number of tetrahedra of minimum (nonzero) volume spanned by $n$ points in $\RR^3$ is at most $2/3n^3-O(n^2)$, and there are point sets for which this number is $3/16n^3-O(n^2)$. We also present an $O(n^3)$ time algorithm for reporting all tetrahedra of minimum nonzero volume, and thereby extend an algorithm of Edelsbrunner, O'Rourke, and Seidel. In general, for every $k,d\in \NN$, $1\le k\le d$, the maximum number of $k$-dimensional simplices of minimum (nonzero) volume spanned by $n$ points in $\RR^d$ is $\Theta (n^k)$. (ii) The number of unit-volume tetrahedra determined by $n$ points in $\RR^3$ is $O(n^{7/2})$, and there are point sets for which this number is $\Omega (n^3\log \log n)$. (iii) For every $d\in \NN$, the minimum number of distinct volumes of all full-dimensional simplices determined by $n$ points in $\RR^d$, not all on a hyperplane, is $\Theta (n)$.

arXiv comment19 pages, 3 figures, a preliminary version has appeard in proceedings of the ACM-SIAM Symposium on Discrete Algorithms, 2007

Cited by in corpus (1)

• Extremal problems on triangle areas in two and three dimensions