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

الأصل · EN

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 ³ is at most 2/3n³-O(n²), and there are point sets for which this number is 3/16n³-O(n²). We also present an O(n³) 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∈, 1≤ k ≤ d, the maximum number of k-dimensional simplices of minimum (nonzero) volume spanned by n points in ᵈ is Θ(nᵏ). (ii) The number of unit-volume tetrahedra determined by n points in ³ is O(n⁷/²), and there are point sets for which this number is Ω(n³ n). (iii) For every d∈, the minimum number of distinct volumes of all full-dimensional simplices determined by n points in ᵈ, not all on a hyperplane, is Θ(n).