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

43 Scopus citations


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

All Science Journal Classification (ASJC) codes

  • 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