On the number of halving planes

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On the number of halving planes

Full text

Pdf (484 KB)

Source

Annual Symposium on Computational Geometry archive
Proceedings of the fifth annual symposium on Computational geometry table of contents

Saarbruchen, West Germany

Pages: 140 - 144

Year of Publication: 1989

ISBN:0-89791-318-3

Authors

I. Bárány	Mathematical Institute of the Hungarian Academy of Sciences, 1364 Budapest, P. 0. B. 127, Hungary
Z. Füredi	Mathematical Institute of the Hungarian Academy of Sciences, 1364 Budapest, P. 0. B. 127, Hungary
L. Lovász	Department of Computer Science, Eötvös University, 1088 Budapest, Múzeum krt. 6-8., Hungary, and Princeton University, Princeton, NJ

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGGRAPH: ACM Special Interest Group on Computer Graphics and Interactive Techniques

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 12, Citation Count: 4

Additional Information:

abstract references cited by index terms collaborative colleagues peer to peer

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/73833.73849 What is a DOI?

ABSTRACT

Let S ⊂ R3 be an n-set in general position. A plane containing three of the points is called a halving plane if it dissects S into two parts of equal cardinality. It is proved that the number of halving planes is at most &Ogr;(n2.998). As a main tool, for every set Y of n points in the plane a set N of size &Ogr;(n4) is constructed such that the points of N are distributed almost evenly in the triangles determined by Y.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	B	I. BARANY, A generalization of Caratheodory's theorem, Discrete Math. 40 (1982), 141-152.
	BáF	I. BARANY AND Z. FUREDI, Empty simplices in Euclidean space, Canad. Math, Bull. 30 (1987), 436- 445.
	BF	E. BOROS and Z. F~REDI, The number of triangles covering the center of an n-set, Geometn'ae Dedicata, 17 (1984), 69-77.
	Ed	Herbert Edelsbrunner, Algorithms in combinatorial geometry, Springer-Verlag New York, Inc., New York, NY, 1987
	E65	P. ERDBS, On extremal problems of graphs and generalized graphs, Israel J. Math. 2 (1964), 183-190.
	ELSS	P. ERD~S, L. LovAsz, A. SIMMONS AND E. G. STRAUS, Dissection graphs of planar point sets, in A Survey of Combinatorial Theory (J. N. Shrivastava et al., eds.), North-Holland, Amsterdam, (1973), 139-149.
	ES	P. ERD~S AND M. SIMONOVITS, Supersaturated graphs and hypergraphs, Combinatorics 3 (1983), 181- 192.
	FR	P. FRANKL, AND V. R~DL, Hypergraphs do not jump, Combinatorics 4 (1984), 149-159.
	L	L. LOVASZ, On the number of halving lines, Annales Univ. R. Eiitviis 14, 107-108.
	KM	M. KATCHALSKI AND A. MEIR, On empty triangles determined by points in the plane, Acta Math. Hungar. 51 (1988), 323-328.
	R	J. REAY, An extension of Radon's theorem, Illinois J. Math. 12, (1968), 184-189.
	T	H. TVERBERG, A generalization of Radon's theorem, J. London Math. Sot. 41 (1966), 123-128.

CITED BY 4

	Ketan Mulmuley, Dehn-Sommerville relations, upper bound theorem, and levels in arrangements, Proceedings of the ninth annual symposium on Computational geometry, p.240-246, May 18-21, 1993, San Diego, California, United States
	Tamal K. Dey , Herbert Edelsbrunner, Counting triangle crossings and halving planes, Proceedings of the ninth annual symposium on Computational geometry, p.270-273, May 18-21, 1993, San Diego, California, United States
	Boris Aronov , Bernard Chazelle , Herbert Edelsbrunner , Leonidas J. Guibas , Micha Sharir , Rephael Wenger, Points and triangles in the plane and halving planes in space, Proceedings of the sixth annual symposium on Computational geometry, p.112-115, June 07-09, 1990, Berkley, California, United States
	Herbert Edelsbrunner , Pavel Valtr , Emo Welzl, Cutting dense point sets in half, Proceedings of the tenth annual symposium on Computational geometry, p.203-209, June 06-08, 1994, Stony Brook, New York, United States