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

1 Scopus citations

Abstract

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
Pages112-115
Number of pages4
ISBN (Print)0897913620, 9780897913621
DOIs
StatePublished - Jan 1 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

Conference

ConferenceProceedings of the Sixth Annual Symposium on Computational Geometry
CityBerkeley, CA, USA
Period6/6/906/8/90

All Science Journal Classification (ASJC) codes

  • Engineering(all)

Cite this