An upper bound on the number of planarK-sets |
| |
Authors: | János Pach William Steiger Endre Szemerédi |
| |
Affiliation: | (1) Mathematical Institute, Hungarian Academy of Science, H-1364 Budapest, Hungary;(2) Courant Institute, New York University, 10012 New York, NY, USA;(3) Computer Science Department, Rutgers University, 08903 New Brunswick, NJ, USA |
| |
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(nk/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.The research of J. Pach was supported in part by NSF Grant CCR-8901484 and by Grant OTKA-1418 from the Hungarian Foundation for Scientific Research. The research of W. Steiger and E. Szemerédi was supported in part by NSF Grant CCR-8902522. All authors express gratitude to the NSF DIMACS Center at Rutgers. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|