Points and triangles in the plane and halving planes in space

Boris Aronov, Leonidas J. Guibas, Bernard Chazelle, Micha Sharir, Herbert Edelsbrunner, Rephael Wenger

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Scopus citations


We prove that for any set S of n points in the plane and n3-α triangles spanned by the points of S there exists a point (not necessarily of S) contained in at least n3-3α/(512 log25 n) of the triangles. This implies that any set of n points in three - dimensional space defines at most 6.4n8/3 log5/3 n halving planes.

Original languageEnglish (US)
Title of host publicationProc Sixth Annu Symp Comput Geom
PublisherPubl by ACM
Number of pages4
ISBN (Print)0897913620, 9780897913621
StatePublished - 1990
Externally publishedYes
EventProceedings of the Sixth Annual Symposium on Computational Geometry - Berkeley, CA, USA
Duration: Jun 6 1990Jun 8 1990

Publication series

NameProc Sixth Annu Symp Comput Geom


ConferenceProceedings of the Sixth Annual Symposium on Computational Geometry
CityBerkeley, CA, USA

All Science Journal Classification (ASJC) codes

  • General Engineering

Cite this