𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On ‘k-sets’ in the plane

✍ Scribed by G.W. Peck

Publisher
Elsevier Science
Year
1985
Tongue
English
Weight
95 KB
Volume
56
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

Given an arrangement of n points in the plane, a k-set in the plane is a k element subset of these that can be separated from the others by a straight line. The question of how many j-sets there are with ] less than k was considered by Pach and by Goodman and Pollack [1], who obtained upper bounds of 2kn, and 2kn-2k2-k, for this number, with k~n/2. Recently Alon and Gyori [2] have obtained proofs of the best possible upper bound for it, namely nk.

It is the purpose of this note to provide another different but very simple proof of this last result.

Theorem. The number of j-sets for j <-k, given n points in the plane is at most kn for all k.

The argument is based on two observations, the first of which is a standard result in this subject. We may assume without loss of generality that no three of our points are on a line, since if we ever have a collection of lines that define our j-sets they will remain so if we move points slightly to avoid three on a line.

📜 SIMILAR VOLUMES

On the distribution of distances in fini
On the distribution of distances in finite sets in the plane
✍ K Vesztergombi 📂 Article 📅 1985 🏛 Elsevier Science 🌐 English ⚖ 894 KB

Let n k denote the number of times the kth largest distance occurs among a set S of n points. We show that if S is the set of vertices of a convex polygone in the euclidean plane, then n1+2n2~3n and n2<~n +n 1. Together with the well-known inequality n~<~n and the trivial inequalities n~>~O and n2>~

On Separation of Plane Convex Sets
On Separation of Plane Convex Sets
✍ Eduardo Rivera-Campo; Jenö Töröcsik 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 77 KB

We show that in any family \(F\) of \(n \geqslant 5\) convex sets in the plane with pairwise disjoint relative interiors, there are two sets \(A\) and \(B\) such that every line that separates them, separates either \(A\) or \(B\) from at least \((n+28) / 30\) sets in \(F\).

On the Cardinality of Intersection Sets
On the Cardinality of Intersection Sets in Inversive Planes
✍ Marcus Greferath; Cornelia Rößing 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 115 KB

Intersection sets and blocking sets play an important role in contemporary finite geometry. There are cryptographic applications depending on their construction and combinatorial properties. This paper contributes to this topic by answering the question: how many circles of an inversive plane will b

Minimal Diameter of Certain Sets in the
Minimal Diameter of Certain Sets in the Plane
✍ András Bezdek; Ferenc Fodor 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 91 KB

We investigate the problem of finding the smallest diameter D(n) of a set of n points such that all the mutual distances between them are at least 1. The asymptotic behaviour of D(n) is known; the exact value of D(n) can be easily found up to 6 points. Bateman and Erdo s proved that D(7)=2. In this

Note on disjoint blocking sets in Galois
Note on disjoint blocking sets in Galois planes
✍ János Barát; Stefano Marcugini; Fernanda Pambianco; Tamás Szőnyi 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 118 KB

## Abstract In this paper, we show that there are at least __cq__ disjoint blocking sets in PG(2,__q__), where __c__ ≈ 1/3. The result also extends to some non‐Desarguesian planes of order __q__. © 2005 Wiley Periodicals, Inc. J Combin Designs 14: 149–158, 2006