×

Points and triangles in the plane and halving planes in space. (English) Zbl 0764.68057

Summary: We prove that for any set \(S\) of \(n\) points in the plane and \(n^{3- \alpha}\) triangles spanned by the points in \(S\) there exists a point (not necessarily in \(S\)) contained in at least \(n^{3-3\alpha}/(c\log^ 5n)\) of the triangles. This implies that any set of \(n\) points in three- dimensional space defines at most \(\root 3 \of {(c/2)}n^{8/3}\log^{5/3}n\) halving planes.

MSC:

68Q25 Analysis of algorithms and problem complexity
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
PDFBibTeX XMLCite
Full Text: DOI EuDML

References:

[1] N. Alon and E. Györi. The number of small semispaces of a finite set of points in the plane.J. Combin. Theory Ser. A41 (1986), 154-157. · Zbl 0584.05003 · doi:10.1016/0097-3165(86)90122-6
[2] F. Aurenhammer, Power diagrams: properties, algorithms, and applications,SIAM J. Comput.16 (1987), 78-96. · Zbl 0616.52007 · doi:10.1137/0216006
[3] I. Bárány. A generalization of Carathéodory’s theorem.Discrete Math.40 (1982), 141-152. · Zbl 0492.52005 · doi:10.1016/0012-365X(82)90115-7
[4] I. Bárány, Z. Füredi and L. Lovász. On the number of halving planes. InProc. Fifth Ann. Symp. Comput. Geom., 1989, pp. 140-144. · Zbl 0718.52009
[5] E. Boros and Z. Füredi. The number of triangles covering the center of ann-set.Geom. Dedicata17 (1984), 69-77. · Zbl 0595.52002 · doi:10.1007/BF00181519
[6] B. Chazelle, H. Edelsbrunner, L. J. Guibas, J. Hershberger, R. Seidel, and M. Sharir. Slimming down by adding; selecting heavily covered points. InProc. Sixth Ann. Symp. Comput. Geom., 1990, pp. 116-127. · Zbl 0813.68157
[7] K. L. Clarkson and P. W. Shor. Applications of random sampling in computational geometry, II.Discrete Comput. Geom.4 (1989), 387-421. · Zbl 0681.68060 · doi:10.1007/BF02187740
[8] H. Edelsbrunner.Algorithms in Combinatorial Geometry. Springer-Verlag, Heidelberg, 1987. · Zbl 0634.52001 · doi:10.1007/978-3-642-61568-9
[9] H. Edelsbrunner and E. Welzl. On the number of line separations of a finite set in the plane.J. Combin. Theory Ser. A38 (1985), 15-29. · Zbl 0616.52003 · doi:10.1016/0097-3165(85)90017-2
[10] Erdös, P.; Lovász, L.; Simmons, A.; Strauss, E. G.; Srivastava, J. N. (ed.), Dissection graphs of planar point sets, 139-149 (1973), Amsterdam · Zbl 0258.05112
[11] J.E. Goodman and R. Pollack. On the number ofk-subsets of a set ofn points in the plane.J. Combin. Theory Ser. A36 (1984), 101-104. · Zbl 0523.51003 · doi:10.1016/0097-3165(84)90081-5
[12] J. Pach, W. Steiger, and E. Szemerédi. An upper bound on the number of planark-sets. InProc. 30th ann. IEEE Symp. Found. Comput. Sci., 1989, pp. 72-79.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.