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

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

    Conference

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

    ASJC Scopus subject areas

    • Engineering(all)

    Cite this

    Aronov, B., Guibas, L. J., Chazelle, B., Sharir, M., Edelsbrunner, H., & Wenger, R. (1990). Points and triangles in the plane and halving planes in space. In Proc Sixth Annu Symp Comput Geom (pp. 112-115). (Proc Sixth Annu Symp Comput Geom). Publ by ACM. https://doi.org/10.1145/98524.98548