\({\varvec{k}}\)-Bisectors of Finite Planar Sets

Let V be a finite set of points in the plane, not all on one line, and let l be a line that contains at least 2 points of V. We say that l is a k -bisector of V if there are at least k points of V on each one of the two open half-planes bounded by l. For \(k \ge 6\) we construct planar sets of \(2k+4\) points having no k-bisector (this might be best possible). Furthermore, we show that if \(|V| > 3 k\), then in every triangulation of convV with vertex set V there is an edge whose loading line is a k-bisector of V. This is best possible for all k.

1. Thus \(\varphi (6) = 16\), a non-trivial byproduct.

2. Note that our “k” is equivalent to \(3k-1\) in l.c., and that the example of \(n=6k+1\) points without a (\(3k-1\))-bisector given there satisfies, in terms of our “k”, \(n=6k+1=2(3k-1)+3=2 \cdot ``k\)”\(+3\).

3. Using again Helly’s Theorem, it is shown there that the value of the function analogous to \(\varphi \) in 3-space, with “k-bisector line” replaced by “k-bisector plane”, is exactly 4k; so the problem is much simpler in 3-space than in the plane.

4. Claim 3.1 remains true when the condition “\(p \in V {\setminus } \cup \mathcal{L}(V)\)” is replaced by the weaker condition “\(p \in V {\setminus } \mathrm{conv}_2 V\)”, where conv\(_2 V\) is the union of all segments with endpoints in V. We do not need this refined result.

Authors and Affiliations

1. Institute of Mathematics, The Hebrew University, Jerusalem, Israel

   Yaakov S. Kupitz & Micha A. Perles

2. Mathematics Faculty, University of Technology, 09107, Chemnitz, Germany

   Horst Martini

Corresponding author

Correspondence to Horst Martini.

Reprints and permissions