×

More on k-sets of finite sets in the plane. (English) Zbl 0598.52007

Für eine Menge S mit \(| S| =n\) in der Euklidischen Ebene \(E^ 2\) wird eine Untermenge S’ von S als eine k-Menge von S, \(1\leq k\leq n-1,\) bezeichnet, wenn S’ aus genau k Punkten besteht und wenn sie von S durch eine Gerade (disjunkt zu S) abgeschnitten werden kann. Es bezeichne \(f_ k(S)\) die Anzahl der k-Mengen, die aus S erhalten werden können, und es sei weiter \(f_ k(n)=\max \{f_ k(T)| \quad T\subset E^ 2,\quad | T| =n\}\) für \(1\leq k\leq n-1.\) Zur Bestimmung von \(f_ k(n)\) kann man sich wegen \(f_ k(n)=f_{n-k}(n)\) auf die Werte \(k: 1\leq k\leq [n]\) beschränken. \(f_ k(n)\) ist nur für \(k=1:\) \(f_ 1(n)=n\) und \(k=2:\) \(f_ 2(n)=[3n/2]\) genau bekannt. Für beliebige k existieren lediglich untere und obere Schranken für \(f_ k(n).\)
Für die Mengen S und \(K\subseteq \{1,2,...,[n]\}\) bezeichne \(f_ K(S)=\sum_{k\in K}f_ k(S)\) und \(f_ K(n)=\max \{f_ K(T)| \quad T\subset E^ 2,\quad | T| =n\}.\) Der Verf. zeigt dann, daß für jede natürliche Zahl n und für \(K\neq \emptyset\) gilt: \(f_ K(n)\leq 2^{3/2} n(\sum_{k\in K}k)^{1/2},\) woraus leicht die weitere Abschätzung folgt: \(f_ K(n)\leq cn^{3/2} | K|^{1/2},\) in der c eine Konstante bezeichnet. Darüberhinaus leitet der Autor noch weitere interessante Ungleichungen für eine mit \(f_ k(S)\) eng verwandte geometrische Größe her.
Reviewer: F.J.Schnitzer

MSC:

52A40 Inequalities and extremum problems involving convexity in convex geometry
52A37 Other problems of combinatorial convexity
05A05 Permutations, words, matrices
05A20 Combinatorial inequalities
PDFBibTeX XMLCite
Full Text: DOI EuDML

References:

[1] N. Alon and E. Győri, The number of small semispaces of a finite set of points in the plane, J. Combin Theory Ser. A, to appear. · Zbl 0584.05003
[2] H. Edelsbrunner, Arrangements and Geometric Computation, forthcoming book.
[3] H. Edelsbrunner and G. Stőckl, The number of extreme pairs of finite point-sets in Euclidean spaces, Institutes for Information Processing, Technical University of Graz, Austria, Report F142 (1984). · Zbl 0611.51002
[4] H. Edelsbrunner and E. Welzl, On the number of line separations of a finite set in the plane, J. Combin. Theory Ser. A 38 (1985) 15-29. · Zbl 0616.52003 · doi:10.1016/0097-3165(85)90017-2
[5] H. Edelsbrunner and E. Welzl, Constructing belts in two-dimensional arrangements with applications, SIAM J. Comput., to appear. · Zbl 0613.68043
[6] Erdős, P.; Lovász, L.; Simmons, A.; Straus, E. G.; Strivastava, J. N. (ed.); etal., Dissection graphs of planar point sets (1973), Amsterdam
[7] J. E. Goodman and R. Pollack, On the combinatorial classification of nondegenerate configurations in the plane, J. Combin. Theory Ser. A 29 (1980) 220-235. · Zbl 0448.05016 · doi:10.1016/0097-3165(80)90011-4
[8] J. E. Goodman and R. Pollack, On the number ofk-subsets of a set ofn points in the plane, J. Combin. Theory Ser. A 36 (1984) 101-104. · Zbl 0699.06010 · doi:10.1016/0097-3165(84)90081-5
[9] G. Stőckl, Gesammelte und neue Ergebnisse über extremek-Mengen für ebene Punktmengen, Diplomarbeit, Institutes for Information Processing, Technical University of Graz (1984).
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.