Mathematics – Combinatorics
Scientific paper
2007-10-20
Mathematics
Combinatorics
19 pages, 3 figures, a preliminary version has appeard in proceedings of the ACM-SIAM Symposium on Discrete Algorithms, 2007
Scientific paper
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/3}n^3-O(n^2)$, and there are point sets for which this number is ${3/16}n^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\leq k \leq 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)$.
Dumitrescu Adrian
Tóth Csaba D.
No associations
LandOfFree
On the number of tetrahedra with minimum, unit, and distinct volumes in three-space does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with On the number of tetrahedra with minimum, unit, and distinct volumes in three-space, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the number of tetrahedra with minimum, unit, and distinct volumes in three-space will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-477206