The number of small semispaces of a finite set of points in the plane

Noga Alon, E. Györi

Research output: Contribution to journalArticlepeer-review

50 Scopus citations

Abstract

For a configuration S of n points in the plane, let gk(S) denote the number of subsets of cardinality ≤k cut off by a line. Let gk,n = max{gk(S): |S| = n}. Goodman and Pollack (J. Combin. Theory Ser. A 36 (1984), 101-104) showed that if k < n 2 then gk,n ≤ 2nk - 2k2 - k. Here we show that gk,n = k·n for k < n 2.

Original languageEnglish (US)
Pages (from-to)154-157
Number of pages4
JournalJournal of Combinatorial Theory, Series A
Volume41
Issue number1
DOIs
StatePublished - Jan 1986

All Science Journal Classification (ASJC) codes

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

Fingerprint Dive into the research topics of 'The number of small semispaces of a finite set of points in the plane'. Together they form a unique fingerprint.

Cite this