On the Number of Tetrahedra with Minimum, Unit, and Distinct Volumes in Three-Space

DOI10.1017/S096354830700884XMaRDI QIDQ3512600zbMATH OpenOpenAlexFDO

Authors Adrian Dumitrescu, Csaba D. Tóth

Publication date 21 July 2008

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0710.3810

zbMATH Keywords

Erdős-type problem

Mathematics Subject Classification ID

Erd?s problems and related topics of discrete geometry (52C10)

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 $R{R}^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,dinNN$, $1leqkleqd$, the maximum number of $k$-dimensional simplices of minimum (nonzero) volume spanned by $n$ points in $R{R}^d$ is $Theta(n^k)$. (ii) The number of unit-volume tetrahedra determined by $n$ points in $R{R}^3$ is $O(n^{7/2})$, and there are point sets for which this number is $Omega(n^{3}loglogn)$. (iii) For every $dinNN$, the minimum number of distinct volumes of all full-dimensional simplices determined by $n$ points in $R{R}^d$, not all on a hyperplane, is $Theta(n)$.

Recommendations

• scientific article; zbMATH DE number 6381744
• Tetrahedrizing point sets in three dimensions
• scientific article; zbMATH DE number 3626171
• Large \(k\)-D simplicies in the \(d\)-dimensional unit cube
• On the number of congruent simplices in a point

Cites work

• An improved bound for joints in arrangements of lines in space
• Combinatorial complexity bounds for arrangements of curves and spheres
• Combinatorial complexity of convex sequences
• Constructing Arrangements of Lines and Hyperplanes with Applications
• Distinct Distances in Three and Higher Dimensions
• Extremal problems in discrete geometry
• Improving the crossing lemma by finding more crossings in sparse graphs
• Incidences between points and circles in three and higher dimensions
• On a problem in combinatorial geometry
• On counting point-hyperplane incidences
• On Sets of Distances of n Points
• On the lattice property of the plane and some problems of Dirac, Motzkin and Erdős in combinatorial geometry
• On the number of directions determined by a three-dimensional points set
• On the Zone Theorem for Hyperplane Arrangements
• Point–Line Incidences in Space
• Repeated angles in the plane and related problems
• Repeated Angles in Three and Four Dimensions
• Some extremal problems in geometry
• The Directions Determined by n Points in the Plane
• The power of geometric duality
• Triangles of extremal area or perimeter in a finite planar point set
• Unsolved problems in geometry

Cited in

(8)

• Extremal problems on triangle areas in two and three dimensions
• Counting simplexes in \(\mathbb{R}^3\)
• Tetrahedrizing point sets in three dimensions
• scientific article; zbMATH DE number 6381744 (Why is no real title available?)
• scientific article; zbMATH DE number 3907270 (Why is no real title available?)
• Tetrahedron ABCD of Width 1 with Minimum AB + BC + CD
• Distinct volume subsets
• Zarankiewicz's problem for semi-algebraic hypergraphs

This page was built for publication: On the Number of Tetrahedra with Minimum, Unit, and Distinct Volumes in Three-Space

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3512600)