ISSN:
1432-0444
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract Given a setS ofn points, a subsetX of sizek is called ak-set if there is a hyperplane Π that separatesX fromS−X. We prove thatO(n√k/log*k) is an upper bound for the number ofk-sets in the plane, thus improving the previous bound of Erdös, Lovász, Simmons, and Strauss by a factor of log*k.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF02187829
Permalink