Points and triangles in the plane and halving planes in space

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

    Research output: Contribution to journalArticlepeer-review


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

    Original languageEnglish (US)
    Pages (from-to)435-442
    Number of pages8
    JournalDiscrete & Computational Geometry
    Issue number1
    StatePublished - Dec 1991

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • Geometry and Topology
    • Discrete Mathematics and Combinatorics
    • Computational Theory and Mathematics


    Dive into the research topics of 'Points and triangles in the plane and halving planes in space'. Together they form a unique fingerprint.

    Cite this