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


    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
    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

    ASJC Scopus subject areas

    • General Engineering

    Cite this