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 four-tuples of n points in three-space. (i) The number of minimum (nonzero) volume tetrahedra spanned by n points in R³ is Θ(n³). (ii) The number of unit-volume tetrahedra determined by n points in R³ is O(n^7/2), and there are point sets for which this number is ω(n³ log log n). (iii) The tetrahedra determined by n points in R³, not all on a plane, have at least ω(n) distinct volumes, and there are point sets for which this number is O(n); this gives a first partial answer for the three-dimensional case to an old question of Erdős, Purdy, and Straus. We also give an O(n³) time algorithm for reporting all tetrahedra of minimum nonzero volume, and thereby extend an early algorithm of Edelsbrunner, O'Rourke, and Seidel.

REFERENCES

• 1: P. K. Agarwal and M. Sharir, Arrangements and their applications, in Handbook of Computational Geometry (J-R. Sack nd J. Urrutia, eds.), chap. 2, Elsevier, 2000, pp. 49--119.
• 2: P. K. Agarwal and M. Sharir, On the number of congruent simplices in a point set, Discrete Comput. Geom. 28 (2002), 123--150.
• 3: Roel Apfelbaum , Micha Sharir, Repeated Angles in Three and Four Dimensions, SIAM Journal on Discrete Mathematics, v.19 n.2, p.294-300, 2005 [doi>10.1137/S0895480104443941]
• 4: Boris Aronov , Vladlen Koltun , Micha Sharir, Incidences between Points and Circles in Three and Higher Dimensions, Discrete & Computational Geometry, v.33 n.2, p.185-206, February 2005 [doi>10.1007/s00454-004-1111-9]
• 5: Boris Aronov , János Pach , Micha Sharir , Gábor Tardos, Distinct Distances in Three and Higher Dimensions, Combinatorics, Probability and Computing, v.13 n.3, p.283-293, May 2004 [doi>10.1017/S0963548304006091]
• 6: J. Beck, On the lattice property of the plane and some problems of Dirac, Motzkin and Erdos in combinatorial geometry, Combinatorica 3 (1983), 281--297.
• 7: Peter Brass , Christian Knauer, On counting point-hyperplane incidences, Computational Geometry: Theory and Applications, v.25 n.1-2, p.13-20, May 2003 [doi>10.1016/S0925-7721(02)00127-X]
• 8: P. Braß, W. Moser, and J. Pach, Research Problems in Discrete Geometry, Springer, New York, 2005.
• 9: P. Braß, G. Rote, and K. J. Swanepoel, Triangles of extremal area or perimeter in a finite planar point set, Discrete Comput. Geom. 26 (2001), 51--58.
• 10: G. R. Burton and G. Purdy, The directions determined by n points in the plane, J. London Math. Soc. 20 (1979), 109--114.
• 11: Bernard Chazelle , Leo J. Guibas , D. T. Lee, The power of geometric duality, BIT, v.25 n.1, p.76-90, 1985 [doi>10.1007/BF01934990]
• 12: Kenneth L. Clarkson , Herbert Edelsbrunner , Leonidas J. Guibas , Micha Sharir , Emo Welzl, Combinatorial complexity bounds for arrangements of curves and spheres, Discrete & Computational Geometry, v.5 n.2, p.99-160, 1990 [doi>10.1007/BF02187783]
• 13: H. T. Croft, K. J. Falconer, and R. K. Guy, Unsolved Problems in Geometry, Springer, New York, 1991.
• 14: A. Dumitrescu and C. D. Tóth, Distinct triangle areas in a planar point set, manuscript 2006.
• 15: A. Dumitrescu and C. D. Tóth, Extremal problems on triangle areas in two and three dimensions, manuscript 2006.
• 16: Herbert Edelsbrunner, Algorithms in combinatorial geometry, Springer-Verlag New York, Inc., New York, NY, 1987
• 17: Herbert Edelsbrunner , Leonidas Guibas, Topologically sweeping an arrangement, Journal of Computer and System Sciences, v.38 n.1, p.165-194, February 1989 [doi>10.1016/0022-0000(89)90038-X]
• 18: H Edelsbrunner , J O'Rouke , R Seidel, Constructing arrangements of lines and hyperplanes with applications, SIAM Journal on Computing, v.15 n.2, p.341-363, May 1986 [doi>10.1137/0215024]
• 19: Herbert Edelsbrunner , Raimund Seidel , Micha Sharir, On the zone theorem for hyperplane arrangements, SIAM Journal on Computing, v.22 n.2, p.418-429, April 1993 [doi>10.1137/0222031]
• 20: György Elekes , Csaba D. Tóth, Incidences of not-too-degenerate hyperplanes, Proceedings of the twenty-first annual symposium on Computational geometry, June 06-08, 2005, Pisa, Italy [doi>10.1145/1064092.1064098]
• 21: P. Erdős, On sets of distances of n points, Amer. Math. Monthly 53 (1946), 248--250.
• 22: P. Erdős and G. Purdy, Some extremal problems in geometry, J. Combin. Theory 10 (1971), 246--252.
• 23: P. Erdős and G. Purdy, Some extremal problems in geometry IV, Congressus Numerantium 17 (Proc. 7th South-Eastern Conf. on Combinatorics, Graph Theory, and Computing), 1976, 307--322.
• 24: P. Erdős, G. Purdy, and E. G. Straus, On a problem in combinatorial geometry, Discrete Math. 40 (1982), 45--52.
• 25: Sharona Feldman , Micha Sharir, An Improved Bound for Joints in Arrangements of Lines in Space, Discrete & Computational Geometry, v.33 n.2, p.307-320, February 2005 [doi>10.1007/s00454-004-1093-7]
• 26: A. Iosevich, S. Konyagin, M. Rudnev, and V. Ten, Combinatorial complexity of convex sequences, Discrete Comput. Geom. 35 (2006), 143--158.
• 27: N. H. Katz and G. Tardos, A new entropy inequality for the Erdős distance problem, in Towards a Theory of Geometric Graphs, vol. 342 of Contemp. Math., AMS, Providence, RI, 2004, 119--126.
• 28: János Pach , Rom Pinchasi , Micha Sharir, On the number of directions determined by a three-dimensional points set, Journal of Combinatorial Theory Series A, v.108 n.1, p.1-16, October 2004 [doi>10.1016/j.jcta.2004.04.010]
• 29: János Pach , Radoš Radoicić , Gábor Tardos , Géza Tóth, Improving the crossing lemma by finding more crossings in sparse graphs: [extended abstract], Proceedings of the twentieth annual symposium on Computational geometry, June 08-11, 2004, Brooklyn, New York, USA [doi>10.1145/997817.997831]
• 30: János Pach , Micha Sharir, Repeated angles in the plane and related problems, Journal of Combinatorial Theory Series A, v.59 n.1, p.12-22, Jan. 1992 [doi>10.1016/0097-3165(92)90094-B]
• 31: J. Pach and M. Sharir, Geometric incidences, in Towards a Theory of Geometric Graphs, vol. 342 of Contemp. Math., AMS, Providence, RI, 2004, pp. 185--223.
• 32: Micha Sharir , Emo Welzl, Point–Line Incidences in Space, Combinatorics, Probability and Computing, v.13 n.2, p.203-220, March 2004 [doi>10.1017/S0963548303005935]
• 33: E. G. Straus, Some extremal problems in combinatorial geometry, in Proc. Conf. Combinatorial Theory, vol. 686 of Lecture Notes in Mathematics, Springer, 1978, pp. 308--312.
• 34: E. Szemerédi and W. T. Trotter, Extremal problems in discrete geometry, Combinatorica 3 (1983), 381--392.
• 35: P. Ungar, 2N noncollinear points determine at least 2N directions, J. Combin. Theory Ser. A 33 (1982), 343--347.