Abstract
LetS ⊂ℝ3 be ann-set in general position. A plane containing three of the points is called a halving plane if it dissectsS into two parts of equal cardinality. It is proved that the number of halving planes is at mostO(n 2.998).
As a main tool, for every setY ofn points in the plane a setN of sizeO(n 4) is constructed such that the points ofN are distributed almost evenly in the triangles determined byY.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
I. Bárány: A generalization of Caratheodory's theorem,Discrete Math.,40 (1982), 141–152.
I. Bárány, andZ. Füredi: Empty simplices in Euclidean space,Canad. Math. Bull.,30 (1987), 436–445.
E. Boros, andZ. Füredi: The number of triangles covering the center of ann-set,Geometriae Dedicata,17 (1984), 69–77.
H. Edelsbrunner:Algorithms in combinatorial geometry, Springer, Berlin Heidelberg, (1987).
P. Erdős: On extremal problems of graphs and generalized graphs,Israel J. Math.,2 (1964), 183–190.
P. Erdős, L. Lovśsz, A. Simmons, andE.G. Straus: Dissection graphs of planar point sets, inA Survey of Combinatorial Theory (J. N. Shrivastava et al., eds.), North-Holland, Amsterdam, (1973), 139–149.
P. Erdős, andM. Simonovits: Supersaturated graphs and hypergraphs,Combinatorica,3 (1983), 181–192.
P. Frankl, andV. Rödl: Hypergraphs do not jump,Combinatorica,4 (1984), 149–159.
L. Lovász: On the number of halving lines,Annales Univ. R. Eötvös,14 (1971), 107–108.
M. Katchalski, andA. Meir: On empty triangles determined by points in the plane,Acta Math. Hungar.,51 (1988), 323–328.
J. Reay: An extension of Radon's theorem,Illinois J. Math.,12 (1968), 184–189.
H. Tverberg: A generalization of Radon's theorem,J. London Math. Soc.,41 (1966), 123–128.
Author information
Authors and Affiliations
Additional information
Research supported partly by the Hungarian National Foundation for Scientific Research grant No. 1812
Rights and permissions
About this article
Cite this article
Bárány, I., Füredi, Z. & Lovász, L. On the number of halving planes. Combinatorica 10, 175–183 (1990). https://doi.org/10.1007/BF02123008
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF02123008