Article

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

Authors:

Adrian Dumitrescu,

Csaba D. TóthAuthors Info & Claims

SODA '07: Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms

Pages 1114 - 1123

Published: 07 January 2007 Publication History

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]

R. Apfelbaum and M. Sharir, Repeated angles in three and four dimensions, SIAM J. Discrete Math. 19 (2005), 294--300.

Digital Library

[4]

B. Aronov, V. Koltun, and M. Sharir, Incidences between points and circles in three and higher dimensions, Discrete Comput. Geom. 33 (2005), 185--206.

Digital Library

[5]

B. Aronov, J. Pach, M. Sharir, and G. Tardos, Distinct distances in three and higher dimensions, Comb. Probab. Comput. 13 (2004), 283--293.

Digital Library

[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]

P. Braß and C. Knauer, On counting point-hyperplane incidences, Comput. Geom. 25 (2003), 13--20.

Digital Library

[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]

B. Chazelle, L. Guibas, and D. T. Lee, The power of geometric duality, BIT 25 (1985), 76--90.

Digital Library

[12]

K. L. Clarkson, H. Edelsbrunner, L. G. Guibas, M. Sharir, and E. Welzl, Combinatorial complexity bounds for arrangements of curves and spheres, Discrete Comput. Geom. 5 (1990), 99--160.

[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]

H. Edelsbrunner, Algorithms in Combinatorial Geometry, Springer-Verlag, Heidelberg, 1987.

Digital Library

[17]

H. Edelsbrunner and L. J. Guibas, Topologically sweeping an arrangement, J. Comput. Syst. Sci. 38 (1989), 165--194. Corrigendum: Topologically sweeping an arrangement, J. Comput. Syst. Sci. 42 (1991), 249--251.

Digital Library

[18]

H. Edelsbrunner, J. O'Rourke, and R. Seidel, Constructing arrangements of lines and hyperplanes with applications, SIAM J. Comput. 15 (1986), 341--363.

Digital Library

[19]

H. Edelsbrunner, R. Seidel, and M. Sharir, On the zone theorem for hyperplane arrangements, SIAM J. Comput. 22 (1993), 418--429.

Digital Library

[20]

Gy. Elekes and Cs. D. Tóth, Incidences of not-too-degenerate hyperplanes, in Proc. 21st ACM Sympos. Comput. Geom., ACM Press, 2005, 16--21.

Digital Library

[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]

S. Feldman and M. Sharir, An improved bound for joints in arrangements of lines in space, Discrete Comput. Geom. 33 (2005), 307--320.

Digital Library

[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. Pach, R. Pinchasi, and M. Sharir, On the number of directions determined by a three-dimensional points set, J. Comb. Theory, Ser. A 108 (2004), 1--16.

Digital Library

[29]

J. Pach, R. Radoičić, G. Tardos, and G. Tóth, Improving the Crossing Lemma by finding more crossings in sparse graphs, in Proc. 20th SoCG, ACM Press, 2004, pp. 68--75.

Digital Library

[30]

J. Pach and M. Sharir, Repeated angles in the plane and related problems, J. Combin. Theory Ser. A 59 (1992), 12--22.

Digital Library

[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]

M. Sharir and E. Welzl, Point-line incidences in space, Comb. Probab. Comput. 13 (2004), 203--220.

Digital Library

[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.

Cited By

Dumitrescu ATóth C(2007)Distinct Triangle Areas in a Planar Point SetProceedings of the 12th international conference on Integer Programming and Combinatorial Optimization10.1007/978-3-540-72792-7_10(119-129)Online publication date: 25-Jun-2007
https://dl.acm.org/doi/10.1007/978-3-540-72792-7_10

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

Recommendations

On the number of tetrahedra with minimum, unit, and distinct volumes in three-space
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.
- <label>(i)</label>The number of tetrahedra of minimum (non-zero) volume spanned by n ...
On the union of fat tetrahedra in three dimensions

We show that the combinatorial complexity of the union of n “fat” tetrahedra in 3-space (i.e., tetrahedra all of whose solid angles are at least some fixed constant) of arbitrary sizes, is O(n^2+ε), for any ε > 0;the bound is almost tight in the worst ...
Algorithms for three-dimensional space tetrahedralization: an experimental study

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SODA '07: Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms

January 2007

1322 pages

ISBN:9780898716245

Conference Chair:
Harold Gabow
University of Colorado, Boulder

Sponsors

SIAM Activity Group on Discrete Mathematics
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 07 January 2007

Check for updates

Qualifiers

Article

Acceptance Rates

SODA '07 Paper Acceptance Rate 139 of 382 submissions, 36%;

Overall Acceptance Rate 411 of 1,322 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
149
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)0

Reflects downloads up to 23 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Dumitrescu ATóth C(2007)Distinct Triangle Areas in a Planar Point SetProceedings of the 12th international conference on Integer Programming and Combinatorial Optimization10.1007/978-3-540-72792-7_10(119-129)Online publication date: 25-Jun-2007
https://dl.acm.org/doi/10.1007/978-3-540-72792-7_10

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents