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

preprint2007arXivOpen access

Abstract

We formulate and give partial answers to several combinatorial problems on volumes of simplices determined by nn points in 3-space, and in general in dd dimensions. (i) The number of tetrahedra of minimum (nonzero) volume spanned by nn points in $\RR^3$ is at most 2/3n3−O(n2){2/3}n^3-O(n^2), and there are point sets for which this number is 3/16n3−O(n2){3/16}n^3-O(n^2). We also present an O(n3)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≤k≤d1\leq k \leq d, the maximum number of kk-dimensional simplices of minimum (nonzero) volume spanned by nn points in $\RR^d$ is Θ(nk)Θ(n^k). (ii) The number of unit-volume tetrahedra determined by nn points in $\RR^3$ is O(n7/2)O(n^{7/2}), and there are point sets for which this number is Ω(n3log⁡log⁡n)Ω(n^3 \log \log{n}). (iii) For every $d\in \NN$, the minimum number of distinct volumes of all full-dimensional simplices determined by nn points in $\RR^d$, not all on a hyperplane, is Θ(n)Θ(n).

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.