DocumentCode :
2071893
Title :
An upper bound on the number of planar k-sets
Author :
Pach, János ; Steiger, William ; Szemerédi, Endre
Author_Institution :
Math. Inst., Hungarian Acad. of Sci., Budapest, Hungary
fYear :
1989
fDate :
30 Oct-1 Nov 1989
Firstpage :
72
Lastpage :
79
Abstract :
Given a set S of n points, a subset X of size k is called a k-set if there is a hyperplane II that separates X from Xc. It is proved that O(nk/log*k) is an upper bound for the number of k-sets in the plane, thus improving the previous bound of P. Erdos et al. (A Survey of Combinatorial Theory, North-Holland, 1983, p.139-49) by a factor of log *k. The method can be extended to give the bound O(nk/(log k)ε). The proof only establishes the weaker result; it uses the geometry and combinatorics together in a stronger way than in the earlier work
Keywords :
combinatorial mathematics; computational complexity; set theory; combinatorics; geometry; hyperplane II; planar k-sets; points; upper bound; Application software; Computer science; Geometry; Sampling methods; Upper bound;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Foundations of Computer Science, 1989., 30th Annual Symposium on
Conference_Location :
Research Triangle Park, NC
Print_ISBN :
0-8186-1982-1
Type :
conf
DOI :
10.1109/SFCS.1989.63458
Filename :
63458
Link To Document :
بازگشت