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

Noga Alon; E. Györi

doi:10.1016/0097-3165(86)90122-6

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

Noga Alon, E. Györi

Research output: Contribution to journal › Article › peer-review

61 Scopus citations

Abstract

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

Original language	English (US)
Pages (from-to)	154-157
Number of pages	4
Journal	Journal of Combinatorial Theory, Series A
Volume	41
Issue number	1
DOIs	https://doi.org/10.1016/0097-3165(86)90122-6
State	Published - Jan 1986
Externally published	Yes

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Access to Document

10.1016/0097-3165(86)90122-6

Cite this

@article{d3fdf0f6bcbc4db5bf1e8384a87f1e5c,

title = "The number of small semispaces of a finite set of points in the plane",

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.",

author = "Noga Alon and E. Gy{\"o}ri",

year = "1986",

month = jan,

doi = "10.1016/0097-3165(86)90122-6",

language = "English (US)",

volume = "41",

pages = "154--157",

journal = "Journal of Combinatorial Theory, Series A",

issn = "0097-3165",

publisher = "Academic Press Inc.",

number = "1",

}

TY - JOUR

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

AU - Alon, Noga

AU - Györi, E.

PY - 1986/1

Y1 - 1986/1

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

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

UR - http://www.scopus.com/inward/record.url?scp=38249043947&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=38249043947&partnerID=8YFLogxK

U2 - 10.1016/0097-3165(86)90122-6

DO - 10.1016/0097-3165(86)90122-6

M3 - Article

AN - SCOPUS:38249043947

SN - 0097-3165

VL - 41

SP - 154

EP - 157

JO - Journal of Combinatorial Theory, Series A

JF - Journal of Combinatorial Theory, Series A

IS - 1

ER -

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

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this