An Improvement of the Upper Bound for the Number of Halving Lines of Planar Sets

Abstract

In this paper, we provide improvements in the additive constant of the current best asymptotic upper bound for the maximum number of halving lines for planar sets of n points, where n is an even number. We also improve this current best upper bound for small values of n, namely, $106\le n\le 336$. To obtain this enhancements, we provide lower bounds for the sum of the squares of the degrees of the vertices of a graph related to the halving lines.

1. Introduction

A classical problem in discrete geometry is the rectilinear crossing number problem. It aims to find the minimum number of crossings for planar sets of n points when each two points of the set are connected by a segment.

Attempts to find sets minimizing the number of crossings have resulted in interesting conjectures about the properties of these sets. Two of these properties are 3-decomposability and 3-symmetry. This last property involves invariance of the set with respect to rotations of angles $\frac{2}{3}\pi$, $\frac{4}{3}\pi$. The conjecture linking 3-symmetry with the rectilinear crossing number problem is that there are 3-symmetric sets of n points that attain the rectilinear crossing number for every n multiple of 3; see [1,2] for more details. A problem related to the rectilinear crossing number problem is the halving line problem. The objective is to find the maximum number of halving lines for subsets of the plane with n points.

The search for upper and lower bounds on the maximum number of halving lines over sets of n points in the plane ($h_n$) is a challenging task due to the large gap between the best lower and upper asymptotic bounds.

The current best lower bound is $h_n\ge \frac{n}{2}{e}^{0.744\sqrt{log\left(\frac{n}{2}\right)}-2.7}$ (see [3]) and the best upper bound is $O\left(n^{\frac{4}{3}}\right)$ (see [4]).

In addition, efforts have been made to find the exact value of $h_n$ for small values of n. The exact value of $h_n$ is known for $n\le 27$ where $n\in \mathbb{N}$, and there are small gaps between the current best lower bound and the current best upper bound of $h_n$ for $28\le n\le 32$. As an example, in Table 2 of [5] we have $73\le h_{32}\le 79$, improved to $74\le h_{32}\le 79$ by [6]. An improvement of the upper bound of $h_n$ yields an improvement of the lower bound of the rectilinear crossing number for complete graphs of n vertices.

The current best multiplicative constant for the bound of [4] and even values of n is ${\left(\frac{29}{8}\right)}^{\frac{1}{3}}$, namely, $h_n\le {\left(\frac{29}{8}\right)}^{\frac{1}{3}}$n${\left(n-1\right)}^{\frac{1}{3}}$.

The motivation of this paper is to improve the former upper bound for the maximum number of halving lines. Concretely, we obtain $h_n\le {\left(\frac{29}{8}\right)}^{\frac{1}{3}}n$ ${\left(n-1\right)}^{\frac{1}{3}}-k$ n for every $k<\frac{29}{6}\simeq 4.83$ and large enough n where n is an even number. To achieve this, we obtain a lower bound for ${\displaystyle \sum _{i=1}^n}{deg}^2\left(x_i\right)$, where $\left\{x_1,\dots ,x_n\right\}$ is the set of vertices of the halving lines graph (see definition below) of a set P for which $h_n$ is attained. We have the lower bound ${\displaystyle \sum _{i=1}^n}{deg}^2\left(x_i\right)\ge \frac{4h_n^2}{n}$ as a direct consequence of Cauchy–Schwartz inequality. This bound is refined in Section 3 based on an analysis of the patterns of the halving line graphs. This lower bound yields an improvement in the upper bound of $\mathrm{cr}\left(G\right)$ (see notation below) for the halving line graphs, resulting in the desired improvement for the upper bound of $h_n$.

We also sharpen the upper bound of $h_n$ for even values of n in the range $106\le n\le 336$ through a refinement of the achieved lower bound for ${\displaystyle \sum _{i=1}^n}{deg}^2\left(x_i\right)$.

The management of this error term in the upper bound of $\mathrm{cr}\left(G\right)$ (see Equation (1)) is the main novelty of the presented work. This term was not bounded in [7], where only the principal term was considered. Despite the improvement being in the additive constant rather than the multiplicative constant, the aforementioned results contribute to significant reductions in the upper bound of $h_n$ for small values of n.

The outline of the rest of the paper is as follows: in Section 2 we provide some notation and definitions; in Section 3 we improve the asymptotic upper bound of $h_n$ in the additive constant; in Section 4 and Section 5 we obtain improvements of the upper bound for small values of n; and in Section 6 we provide some concluding remarks.

2. Basic Definitions

Definition 1. 

For a set $P=\left\{p_1,\dots ,p_n\right\}$, a $k$-edge of P is a line that joins two points of P and leaves k points of P in one of the half planes, which we call the k-half plane.

Definition 2. 

For a set $P=\left\{p_1,\dots ,p_n\right\}$, a halving line of P is a $⌊\frac{n-2}{2}⌋$-edge of P.

We denote $p_i-p_j$ as the line joining points $p_i$ and $p_j$.

Definition 3. 

The halving lines graph of a set P is a graph $G=\left(V,E\right)$ with $V=P$ and $\left\{p_i,p_j\right\}\in E$ if $p_i-p_j$ is a halving line of P. The degree of a vertex $v\in V$ is the number of edges $e\in E$ containing V.

Definition 4. 

A $(\le k)$-edge of P is a t-edge of P with $t\le k$.

Notation: $\mathrm{cr}\left(G\right)$ is the number of crossings of the graph G (number of intersections out of the vertices of the edges of G in a geometric representation of the graph).

Throughout this paper, we assume that sets are in general position (i.e., no instances of three points in a line).

3. Asymptotic Improvement of the Upper Bound of ${\mathit{h}}_{\mathit{n}}$

Let us see the improvement in the additive constant for the to-date best asymptotic upper bound of $h_n$. First, we need some preliminary results. The fourth result (Proposition 2) improves the multiplicative constant of the condition of Theorem 6 of [7].

Lemma 1. 

For even n, $n>6$, there is a set P attaining $h_n$ such that the graph of the halving lines of P has at least the following: six vertices of degree 1, or five vertices of degree 1 and one vertex of degree 3, or four vertices of degree 1 and two vertices of degree 3, or three vertices of degree 1 and three vertices of degree 3, or five vertices of degree 1 and one vertex of degree 5.

Proof. 

There exists a set P attaining $h_n$ with three points of P, say $p_1$, $p_2$, $p_3$, in the boundary of its convex hull (see [8]); thus, they have degree 1 in the graph of halving lines.

We also have the following: for fixed k, the points of $Q:=P-\left\{p_1,p_2,p_3\right\}$ in the boundary of the convex hull of Q, say, $p_4$, …, $p_i$, with $i\ge 6$ belonging to two k-edges of $Q.$ The halving lines of P with a point included in $\left\{p_4,\dots ,p_i\right\}$ and the other one in Q are equal to the halving lines of Q, leaving exactly two points of $\left\{p_1,p_2,p_3\right\}$ in the $\frac{\left(n-3\right)-3}{2}$-half plane; thus, there are at most two halving lines of P with these properties.

Hence, if the halving lines of P that contains one point from $\left\{p_1,p_2,p_3\right\}$ do not contain a point from $p_4$, …, $p_6$, then these vertices have a degree of at most 2 in the halving lines graph of P; thus, because they must have an odd degree, we find that the vertices $p_4$, …, $p_6$ have degree 1, meaning that the halving lines graph of P has at least six vertices of degree 1.

If there is only a halving line of P that contains one point from $\left\{p_1,p_2,p_3\right\}$ and another point from $\left\{p_4,p_5,p_6\right\}$, say, $p_4$, and if the two halving lines of Q containing $p_4$ leave two points from $\left\{p_1,p_2,p_3\right\}$ in the $\frac{n-6}{2}$-half plane, then $p_4$ has degree 3 in the halving lines graph of P and $p_5,$ $p_6$ has degree 1 in said graph, just as we have seen in the previous case. Thus, the graph of halving lines of P has at least five vertices of degree 1 and one vertex of degree 3.

If there are two halving lines of P that contain one point from $\left\{p_1,p_2,p_3\right\}$ and another point from $\left\{p_4,p_5,p_6\right\}$, say, $p_4$ and $p_5$, and if the two halving lines of Q containing $p_4$ or $p_5$ leave two points from $\left\{p_1,p_2,p_3\right\}$ in the $\frac{n-6}{2}$-half plane, then $p_4,p_5$ have degree 3 in the graph of halving lines of P and $p_6$ has degree 1 in said graph, the same as in the previous cases. Thus, the graph of halving lines of P has at least four vertices of degree 1 and two vertices of degree 3 ($p_4$, $p_5$).

If there are three halving lines of P that contain one point from $\left\{p_1,p_2,p_3\right\}$ and the same point from $\left\{p_4,p_5,p_6\right\}$, say, $p_4$, and if the two halving lines of Q containing $p_4$ leave two points from $\left\{p_1,p_2,p_3\right\}$ in the $\frac{n-6}{2}$-half plane, then $p_4$ has degree 5 in the graph of halving lines of P, while $p_5,$ $p_6$ have degree 1 in said graph, as we have seen in the previous cases. Thus, the graph of the halving lines of P has at least five vertices of degree 1 and one vertex of degree 5 ($p_4$).

If there are three halving lines of P that contains one point from $\left\{p_1,p_2,p_3\right\}$ and one point from $\left\{p_4,p_5,p_6\right\}$ different from each other, say, $p_1-p_4$, $p_2-p_5$, $p_3-p_6$, and if these three halving lines of Q leave two points from $\left\{p_1,p_2,p_3\right\}$ in the $\frac{n-6}{2}$-half plane, then $p_4,$ $p_5,$ $p_6$ have degree 3 in the graph of the halving lines of P. Thus, the graph of the halving lines of P has at least three vertices of degree 1 and three vertices of degree 3 ($p_4,$ $p_5,$ $p_6$), as desired. □

Lemma 2. 

Let G be the graph of the halving lines of a set P in which $h_n$ is attained for even n, $n>6$. Then, it is satisfied that

$\begin{array}{c}\mathrm{cr}\left(G\right)\le {\displaystyle \frac{n^2-n}{8}}\\ -{\displaystyle \frac{1}{8}}min\left\{6+{\displaystyle \frac{{\left(2h_n-6\right)}^2}{n-6}},14+{\displaystyle \frac{{\left(2h_n-8\right)}^2}{n-6}},22+{\displaystyle \frac{{\left(2h_n-10\right)}^2}{n-6}},30+{\displaystyle \frac{{\left(2h_n-12\right)}^2}{n-6}}\right\}.\end{array}$

Proof. 

We have

(1)$\mathrm{cr}\left(G\right)\le {\displaystyle \frac{n^2-n}{8}}-{\displaystyle \frac{1}{8}}\sum _{i=1}^n{deg}^2\left(x_i\right)$

for the graph G of the halving lines of a set P = $\left\{x_1,\dots ,x_n\right\}$, where n is an even number; see [7]. If we are in the first case of Lemma 1 (six vertices of degree one), then, applying Cauchy–Schwartz inequality, for a set P = $\left\{x_1,\dots ,x_n\right\}$ in which $h_n$ is attained we have

$\sum _{i=1}^n{deg}^2\left(x_i\right)=6+\sum _{i=7}^n{deg}^2\left(x_i\right)\ge 6+{\displaystyle \frac{{\left({\displaystyle \sum _{i=7}^n}deg\left(x_i\right)\right)}^2}{n-6}}=6+{\displaystyle \frac{{\left(2h_n-6\right)}^2}{n-6}}.$

We obtain the other lower bounds of ${\displaystyle \sum _{i=1}^n}{deg}^2\left(x_i\right)$ if we are in the other cases of Lemma 1. Concretely, the bound ${\displaystyle \sum _{i=1}^n}{deg}^2\left(x_i\right)\ge 14+\frac{{\left(2h_n-8\right)}^2}{n-6}$ is obtained in the case with five vertices of degree 1 and one vertex of degree 3. The lower bound ${\displaystyle \sum _{i=1}^n}{deg}^2\left(x_i\right)\ge 22+\frac{{\left(2h_n-10\right)}^2}{n-6}$ is obtained for the case with four vertices of degree 1 and two vertices of degree 3, and so forth. Hence,

(2)$\begin{array}{c}\sum _{i=1}^n{deg}^2\left(x_i\right)\ge \\ min\left\{6+{\displaystyle \frac{{\left(2h_n-6\right)}^2}{n-6}},14+{\displaystyle \frac{{\left(2h_n-8\right)}^2}{n-6}},22+{\displaystyle \frac{{\left(2h_n-10\right)}^2}{n-6}}\right.,\\ \left.30+{\displaystyle \frac{{\left(2h_n-12\right)}^2}{n-6}},30+{\displaystyle \frac{{\left(2h_n-10\right)}^2}{n-6}}\right\}\\ =min\left\{6+{\displaystyle \frac{{\left(2h_n-6\right)}^2}{n-6}},14+{\displaystyle \frac{{\left(2h_n-8\right)}^2}{n-6}},22+{\displaystyle \frac{{\left(2h_n-10\right)}^2}{n-6}},30+{\displaystyle \frac{{\left(2h_n-12\right)}^2}{n-6}}\right\},\end{array}$

and we have the desired upper bound of $\mathrm{cr}\left(G\right)$ by substituting (2) in (1). □

Proposition 1.

Let G be the halving lines graph of a set P in which $h_n$ is attained (for even n, $n>6$). Then, it is satisfied that

$\mathrm{cr}\left(G\right)\le {\displaystyle \frac{n^2-n}{8}}-{\displaystyle \frac{1}{8}}\left(30+{\displaystyle \frac{{\left(2h_n-12\right)}^2}{n-6}}\right).$

Proof. 

From Lemma 2, it is enough to prove that

$min\left\{6+{\displaystyle \frac{{\left(2h_n-6\right)}^2}{n-6}},14+{\displaystyle \frac{{\left(2h_n-8\right)}^2}{n-6}},22+{\displaystyle \frac{{\left(2h_n-10\right)}^2}{n-6}},30+{\displaystyle \frac{{\left(2h_n-12\right)}^2}{n-6}}\right\}$

$=30+{\displaystyle \frac{{\left(2h_n-12\right)}^2}{n-6}}.$

We have

$14+{\displaystyle \frac{{\left(2h_n-8\right)}^2}{n-6}}\ge 30+{\displaystyle \frac{{\left(2h_n-12\right)}^2}{n-6}}\iff {\displaystyle \frac{16h_n}{n-6}}\ge 16+{\displaystyle \frac{80}{n-6}}\iff h_n\ge n-1,$

which is true due to the known lower bounds of $h_n$. We can check the other inequalities in the same way. □

Proposition 2.

For a graph $G=\left(V,E\right)$ with $\left|E\right|=m$, $\left|V\right|=n$, if $m>6.85058$ n, then we have $\mathrm{cr}\left(G\right)\ge \frac{1}{29}\frac{m^3}{n^2}$.

Proof. 

We will show that for every $k\in N$, if $m\ge {\beta }_k$ n, then $\mathrm{cr}\left(G\right)\ge \frac{1}{29}\frac{m^3}{n^2}$, where ${\beta }_k$ is the sequence defined as ${\beta }_1=6.95$, ${\beta }_k=\frac{\frac{1}{29}{\beta }_{k-1}^3+\frac{139}{6}}{5}$. For $k=1$, the result is Theorem 6 of [7].

Assuming that the result is true for k, if $\mathrm{cr}\left(G\right)<\frac{1}{29}\frac{m^3}{n^2}$, then we necessarily have $m<{\beta }_k$ n, meaning that $\mathrm{cr}\left(G\right)<\frac{1}{29}\frac{m^3}{n^2}<\frac{1}{29}\frac{{\beta }_k^3{n}^3}{n^2}=\frac{1}{29}$ ${\beta }_k^3$ n. However, we have $\mathrm{cr}\left(G\right)\ge 5$ $m-\frac{139}{6}$ $\left(n-2\right)$ (see [7]), meaning that 5 $m-\frac{139}{6}$ $\left(n-2\right)<\frac{1}{29}$ ${\beta }_k^3$ n. This implies that

$m<{\displaystyle \frac{\frac{1}{29}{\beta }_k^{3}n+\frac{139}{6}\left(n-2\right)}{5}}<{\displaystyle \frac{\frac{1}{29}{\beta }_k^3+\frac{139}{6}}{5}}n={\beta }_{k+1}n.$

In this way, if $m\ge {\beta }_{k+1}$ n, then $\mathrm{cr}\left(G\right)\ge \frac{1}{29}\frac{m^3}{n^2}$, as desired.

Now, we can show that ${\beta }_k$ is a decreasing sequence:

${\beta }_2={\displaystyle \frac{\frac{1}{29}{\beta }_1^3+\frac{139}{6}}{5}}={\displaystyle \frac{\frac{1}{29}{6.95}^3+\frac{139}{6}}{5}}=6.94852<{\beta }_1.$

Assuming that ${\beta }_k<{\beta }_{k-1}$, then ${\beta }_{k+1}=\frac{\frac{1}{29}{\beta }_k^3+\frac{139}{6}}{5}<\frac{\frac{1}{29}{\beta }_{k-1}^3+\frac{139}{6}}{5}={\beta }_k$.

Thus, ${\beta }_k$ has a limit l such that $0\le l<6.95$. Taking limits in the recurrence defining ${\beta }_k$, we can find that l satisfies $l=\frac{\frac{1}{29}{l}^3+\frac{139}{6}}{5}$. The only solution l to this equation with $0\le l<6.95$ is $l\approx 6.85058$.

In this way, if $m>6.85058$ n, then there exists $k\in N$ such that $m\ge {\beta }_k$ n; then, $\mathrm{cr}\left(G\right)\ge \frac{1}{29}\frac{m^3}{n^2}$, as desired. □

Proposition 3.

It is satisfied that $h_n\le ⌊a_n⌋$ for n that is an even number, $n\ge 282$, where $a_n$ is the largest real root of $\frac{1}{29}$ $\frac{x^3}{n^2}+\frac{1}{8}$ $\left(30+\frac{{\left(2x-12\right)}^2}{n-6}\right)-\frac{n^2-n}{8}$.

Proof. 

Combining the lower and upper bounds of Propositions 1 and 2 for $\mathrm{cr}\left(G\right)$, for $h_n\ge 6.85058$ n we obtain

${\displaystyle \frac{1}{29}}{\displaystyle \frac{h_n^3}{n^2}}\le {\displaystyle \frac{n^2-n}{8}}-{\displaystyle \frac{1}{8}}\left(30+{\displaystyle \frac{{\left(2h_n-12\right)}^2}{n-6}}\right)\iff$

${\displaystyle \frac{1}{29}}{\displaystyle \frac{h_n^3}{n^2}}-{\displaystyle \frac{n^2-n}{8}}+{\displaystyle \frac{1}{8}}\left(30+{\displaystyle \frac{{\left(2h_n-12\right)}^2}{n-6}}\right)\le 0.$

This implies that $h_n\le a_n$; as $h_n$ is an integer number, we obtain $h_n\le ⌊a_n⌋$. For $h_n<6.8505$ n, we also have $h_n\le ⌊a_n⌋$ if $n\ge 282$, as $6.8505$ $n\le a_n$ for $n\ge 282$, meaning that $h_n\le ⌊a_n⌋$ for $n\ge 282$, as desired. □

Remark 1.

Comparing with Dey’s bound, it is satisfied that

$\underset{n\to \infty }{lim}{\displaystyle \frac{a_n-{\left(\frac{29}{8}\right)}^{\frac{1}{3}}n{(n-1)}^{\frac{1}{3}}}{n}}=-{\displaystyle \frac{29}{6}}(\simeq -4.83);$

thus, for every $k<\frac{29}{6}$ we obtain

$h_n\le a_n\le {\left({\displaystyle \frac{29}{8}}\right)}^{\frac{1}{3}}n{(n-1)}^{\frac{1}{3}}-kn$

for large enough n.

Remark 2.

This bound is the best upper bound of $h_n$ for $n\ge 338$ where n is an even number.

The asymptotic improvement of the upper bound of $h_n$ yields an improvement of the best asymptotic lower bound of $e_{\left(\le k\right)}\left(n\right)$ when k is close to $\frac{n}{2}$ and where $e_{\left(\le k\right)}\left(n\right)$ is the minimum number of $(\le k)$-edges for sets of n points in the plane. Let us now establish the new bound while assuming that $k=\frac{n-8}{2}$ and that n is a large even number.

Proposition 4.

For n that is an even number with $n\ge 282$, it is satisfied that

(3) $e_{\left(\le \frac{n-8}{2}\right)}\left(n\right)\ge {\displaystyle \frac{n^2-n}{2}}-⌊{\left({\displaystyle \frac{29}{2}}\right)}^{\frac{1}{3}}n{\left(n-4\right)}^{\frac{1}{3}}⌋-⌊{\left({\displaystyle \frac{29}{2}}\right)}^{\frac{1}{3}}n{\left(n-2\right)}^{\frac{1}{3}}⌋-⌊a_n⌋.$

Proof. 

Let P be a set in which $e_{\left(\le \frac{n-8}{2}\right)}\left(n\right)$ is attained; then,

$e_{\left(\le \frac{n-8}{2}\right)}\left(n\right)={\displaystyle \frac{n^2-n}{2}}-e_{\frac{n-6}{2}}\left(P\right)-e_{\frac{n-4}{2}}\left(P\right)-h\left(P\right),$

and the lower bound is a consequence of the upper bound of $e_k\left(P\right)$, $k<\frac{n-2}{2}$ from Dey and the bound of $h_n$ in Proposition 3. □

Remark 3.

The lower bound of $e_{\left(\le \frac{n-8}{2}\right)}\left(n\right)$ included in Lemma 1 of [6] is $\frac{n^2-n}{2}-O\left(n^{\frac{3}{2}}\right)$, being the bound $\left(3\right)$ $\frac{n^2-n}{2}-O\left(n^{\frac{4}{3}}\right)$; thus, $\left(3\right)$ is better than the current best lower bound of $e_{\left(\le \frac{n-8}{2}\right)}\left(n\right)$ for large values of n.

Next, we apply the techniques of [9] to improve the lower bound $\left(3\right)$ by one for some large even values of n.

Proposition 5.

For even n, $n\ge 282$, it is satisfied that

$\begin{array}{c}{e}_{\left(\le \frac{n-8}{2}\right)}\left(n\right)\ge \\ {\displaystyle \frac{n^2-n}{2}}-⌊{\displaystyle \frac{n}{n+1}}⌊{\left({\displaystyle \frac{29}{2}}\right)}^{\frac{1}{3}}\left(n+1\right){\left(n-4\right)}^{\frac{1}{3}}⌋⌋-⌊{\left({\displaystyle \frac{29}{2}}\right)}^{\frac{1}{3}}n{\left(n-2\right)}^{\frac{1}{3}}⌋-⌊a_n⌋.\end{array}$

Proof. 

The proof is analogous to corollary 4 of [9] while updating the upper bound of $h_n$. □

Remark 4.

Proposition 5 improves the lower bound of (3) by one unit for some large even values of n.

4. Improvement of the Upper Bound of ${\mathit{h}}_{\mathit{n}}$ for Small Values of $\mathit{n}$

Now, we obtain an improvement of the current best upper bound of $h_n$ for small values of n by applying linear lower bounds to $\mathrm{cr}\left(G\right)$.

Proposition 6.

It is satisfied that $h_n\le ⌊b_n⌋$ for even n, $n\ge 8$, where $b_n$ is the largest real root of the polynomial $P\left(x\right)=\frac{1}{8}\left(30+\frac{{\left(2x-12\right)}^2}{n-6}\right)+\frac{7}{3}$ $x-\frac{25}{3}\left(n-2\right)-\frac{n^2-n}{8}$.

Proof. 

Combining the lower and upper bounds of [10] and Proposition 1 for $\mathrm{cr}\left(G\right)$, where G is the graph of halving lines for a set P for which $h_n$ is attained, we obtain

$\frac{7}{3}$$h_n-\frac{25}{3}$$\left(n-2\right)\le \frac{n^2-n}{8}-\frac{1}{8}$$\left(30+\frac{{\left(2h_n-12\right)}^2}{n-6}\right)$, which implies the desired upper bound of $h_n$ by solving the two-degree inequality in $h_n$. □

Remark 5.

The former upper bound is equivalent to $\frac{1}{2}$ $n^{\frac{3}{2}}$, meaning that it is asymptotically worse than Dey’s bound. Nonetheless, this bound is the current best upper bound of $h_n$ for small values of n; that is, it is the best upper bound of $h_n$ for even values of n such that $108\le n\le 128$ (the previous best upper bound for these values of n is the bound in [5]).

Remark 6.

It is satisfied that $b_n=20-\frac{7n}{3}+\frac{1}{6}\sqrt{9n^3+733n^2-8376n+21,924}$.

We can use another linear lower bound of $\mathrm{cr}\left(G\right)$ to obtain another upper bound for $h_n$.

Proposition 7.

If n is an even number and $n\ge 8$, then we have $h_n\le ⌊c_n⌋$, where $c_n$ is the largest real root of the polynomial $P\left(x\right)=\frac{1}{8}\left(30+\frac{{\left(2x-12\right)}^2}{n-6}\right)+5$ $x-\frac{139}{6}\left(n-2\right)-\frac{n^2-n}{8}$.

Proof. 

We know that $\mathrm{cr}\left(G\right)\ge 5$ $h_n-\frac{139}{6}$ $\left(n-2\right)$, where G is the halving lines graph for a set P in which $h_n$ is attained; see [7]. We also have the upper bound $\mathrm{cr}\left(G\right)\le \frac{n^2-n}{8}-\frac{1}{8}\left(30+\frac{{\left(2h_n-12\right)}^2}{n-6}\right)$. Putting together the two inequalities, we obtain

$5h_n-{\displaystyle \frac{139}{6}}\left(n-2\right)\le {\displaystyle \frac{n^2-n}{8}}-{\displaystyle \frac{1}{8}}\left(30+{\displaystyle \frac{{\left(2h_n-12\right)}^2}{n-6}}\right)\iff$

(4)$P\left(h_n\right)={\displaystyle \frac{1}{8}}\left(30+{\displaystyle \frac{{\left(2h_n-12\right)}^2}{n-6}}\right)+5h_n-{\displaystyle \frac{n^2-n}{8}}-{\displaystyle \frac{139}{6}}\left(n-2\right)\le 0.$

Because $P\left(x\right)\to \infty$ as $x\to \infty$, we obtain $h_n\le c_n$ and then $h_n\le ⌊c_n⌋$, as $h_n$ is an integer number. □

Remark 7.

$⌊c_n⌋$ is the best upper bound of $h_n$ for even values of n such that $204\le n\le 336$.

Remark 8.

We have $c_n=\frac{1}{6}$ $\left(216-30n+\sqrt{9n^3+2505n^2-26,520n+66,996}\right)$.

For even n in the range $[158,$ $202]$, we can obtain another improvement of these bounds.

Proposition 8.

For even n, $n\ge 4$, it is satisfied that $h_n\le ⌊d_n⌋$, where $d_n$ is the largest root of $R\left(x\right)=\frac{1}{8}\left(30+\frac{{\left(2x-12\right)}^2}{n-6}\right)+4$ $x-\frac{103}{6}\left(n-2\right)-\frac{n^2-n}{8}$,

Proof. 

We have $\mathrm{cr}\left(G\right)\ge 4$ $h_n-\frac{103}{6}$ $\left(n-2\right)$ for the halving lines graph G of a set P for which $h_n$ is attained (see [10]). On the other hand, $\mathrm{cr}\left(G\right)\le \frac{n^2-n}{8}-\frac{1}{8}$ $\left(30+\frac{{\left(2h_n-12\right)}^2}{n-6}\right)$.

Connecting the two inequalities, we obtain

$4h_n-{\displaystyle \frac{103}{6}}\left(n-2\right)\le {\displaystyle \frac{n^2-n}{8}}-{\displaystyle \frac{1}{8}}\left(30+{\displaystyle \frac{{\left(2h_n-12\right)}^2}{n-6}}\right),$

and then

$R\left(h_n\right)={\displaystyle \frac{1}{8}}\left(30+{\displaystyle \frac{{\left(2h_n-12\right)}^2}{n-6}}\right)+4h_n-{\displaystyle \frac{103}{6}}\left(n-2\right)\le 0.$

This inequality, together with

${lim}_{x\to \infty }R\left(x\right)=\infty$, implies that $h_n\le d_n$. Because $h_n$ is an integer number, we obtain $h_n\le ⌊d_n⌋$, as desired. □

Remark 9.

This bound is better than the aforementioned upper bounds of $h_n$ for even values of n such that $158\le n\le 202$.

Remark 10.

We have $d_n=\frac{1}{6}$ $\left(180-24n+\sqrt{9n^3+1749n^2-18,744n+47,556}\right)$.

This bound (and the previous ones) can be improved for some values of n.

Proposition 9.

For even n such that $128\le n\le 156$, it is satisfied that $h_n\le ⌊e_n⌋$, where $e_n$ is the largest root of $S\left(x\right)=\frac{1}{8}\left(30+\frac{{\left(2x-12\right)}^2}{n-6}\right)+3$ $x-\frac{35}{3}\left(n-2\right)-\frac{n^2-n}{8}$.

Proof. 

First, we can see that if n is an even number such that $n<158$, then $h_n\le 5.5$ $\left(n-2\right)$. Supposing that $h_n>5.5$ $\left(n-2\right)$, we have $5.5$ $\left(n-2\right)<h_n\le b_n$, so $5.5$ $\left(n-2\right)\le b_n$, implying that $n\ge 158$, which is a contradiction.

Now, if n is an even number such that $n<158$ and $h_n\ge 5$ $\left(n-2\right)$, because 5 $\left(n-2\right)\le h_n\le 5.5$ $\left(n-2\right)$, we have $\mathrm{cr}\left(G\right)\ge 3$ $h_n-\frac{35}{3}\left(n-2\right)$, with G being the halving lines graph of a set P for which $h_n$ is attained (see [10]). Thus, 3 $h_n-\frac{35}{3}\left(n-2\right)\le$ $\mathrm{cr}\left(G\right)\le \frac{n^2-n}{8}-\frac{1}{8}$ $\left(30+\frac{{\left(2h_n-12\right)}^2}{n-6}\right)$. Connecting the two inequalities, we obtain the following:

$3h_n-{\displaystyle \frac{35}{3}}\left(n-2\right)\le {\displaystyle \frac{n^2-n}{8}}-{\displaystyle \frac{1}{8}}\left(30+{\displaystyle \frac{{\left(2h_n-12\right)}^2}{n-6}}\right)\iff$

$S\left(h_n\right)={\displaystyle \frac{1}{8}}\left(30+{\displaystyle \frac{{\left(2h_n-12\right)}^2}{n-6}}\right)+3h_n-{\displaystyle \frac{35}{3}}\left(n-2\right)-{\displaystyle \frac{n^2-n}{8}}\le 0.$

Because $S\left(x\right)\to \infty$, as $x\to \infty$, this implies that $h_n\le$ $e_n$.

If n is an even number such that $n<158$ and $h_n\le 5$ $\left(n-2\right)$, because 5 $\left(n-2\right)\le e_n$ for $n\ge 128$, we have $h_n\le$ $e_n$ if $128\le n<158$ in any case. As we have $h_n\in \mathbb{N}$, this implies that $h_n\le ⌊e_n⌋$, as desired. □

Remark 11.

This bound is better than the aforementioned upper bounds of $h_n$ for even values of n such that $130\le n\le 156$.

Remark 12.

Here, we have $e_n=\frac{1}{6}$ $\left(144-18n+\sqrt{9n^3+1101n^2-12,120n+31,140}\right)$.

In addition, the improvement of the upper bound of $h_n$ yields an improvement of the current best lower bound of $\mathrm{cr}\left(n\right)$. We illustrate said improvement below with an example.

Example 1. 

For $n=132$, $⌊e_n⌋$ improves the current best upper bound of $h_n$ by 10. Applying the lower bound of [5,11] for $\mathrm{cr}\left(n\right)$, we obtain an improvement of 10 in the to-date best lower bound of $\mathrm{cr}\left(132\right)$. Concretely, we have $\mathrm{cr}\left(132\right)\ge 4525247$. This reduces the gap with the best current upper bound of $\mathrm{cr}\left(132\right)$ (see Theorem 4 of [1]): $\mathrm{cr}\left(132\right)\le 4534047$.

5. Better Improvements of the Upper Bound of ${\mathit{h}}_{\mathit{n}}$

In the previous sections, we have improved the upper bound of $h_n$ for $n\ge 108$ when n is an even number. We can improve this upper bound for a smaller even value of n, namely, $n=106$, by refining the lower bound of ${\displaystyle \sum _{i=1}^n}{deg}^2\left(x_i\right)$. For this purpose, we next obtain $min\left\{{\displaystyle \sum _{i=1}^n}{deg}^2\left(x_i\right)\right\}$ for graphs where $h_n$ is attained.

Proposition 10.

Let n be an even number, $n\ge 8$, $t_n\in \mathbb{N}$, and let $m_n$ be defined by $m_n=min\left\{{\displaystyle \sum _{i=7}^n}{y}_i^2/y_7\le \dots \le y_n,y_i\mathit{are}\mathit{odd}\mathit{numbers},y_7+\dots +y_n=t_n\right\}$:

• If $⌊\frac{t_n}{n-6}⌋$ is an odd number and $n-6$ does not divide to $t_n$, then $m_n$ is attained when $y_i$ is one of the two odd numbers that are closest to $\frac{t_n}{n-6}$ for $i=7,$ $\dots ,$ n.

• If $⌊\frac{t_n}{n-6}⌋$ is an odd number and $n-6$ divides to $t_n$, then $m_n$ is attained when $y_i=\frac{t_n}{n-6}$ for $i=7,$ $\dots ,$ n.

Proof. 

Obtaining $m_n$ is equivalent to minimizing $d^2\left(\left(y_7,\dots ,y_n\right),\left(\frac{t_n}{n-6},\dots ,\frac{t_n}{n-6}\right)\right)$ for $y_7,\dots ,$ $y_n$, satisfying the given conditions. Indeed,

$d^2\left(\left(y_7,\dots ,y_n\right),\left({\displaystyle \frac{t_n}{n-6}},\dots ,{\displaystyle \frac{t_n}{n-6}}\right)\right)={\left(y_7-{\displaystyle \frac{t_n}{n-6}}\right)}^2+\dots +{\left(y_n-{\displaystyle \frac{t_n}{n-6}}\right)}^2$

$=y_7^2+\dots +y_n^2-2{\displaystyle \frac{t_n}{n-6}}\left(y_7+\dots +y_n\right)+\left(n-6\right){\displaystyle \frac{t_n^2}{{\left(n-6\right)}^2}}$

$=y_7^2+\dots +y_n^2-2{\displaystyle \frac{t_n}{n-6}}{t}_n+{\displaystyle \frac{t_n^2}{n-6}}$

$=y_7^2+\dots +y_n^2-{\displaystyle \frac{t_n^2}{n-6}}.$

First, we note that if $n-6$ does not divide to $t_n$ and if $⌊\frac{t_n}{n-6}⌋$ is an odd number, then there is always a unique solution of $y_7+\dots +y_n=t_n$ with $y_i=⌊\frac{t_n}{n-6}⌋$ or $y_i=⌊\frac{t_n}{n-6}⌋+2$ for $i=7,$ $\dots ,$ n (the odd numbers that are closest to $\frac{t_n}{n-6}$). We have the following:

$a⌊{\displaystyle \frac{t_n}{n-6}}⌋+\left(n-6-a\right)\left(⌊{\displaystyle \frac{t_n}{n-6}}⌋+2\right)=t_n⟺$

$a={\displaystyle \frac{\left(n-6\right)\left(⌊\frac{t_n}{n-6}⌋+2\right)-t_n}{2}}.$

Because n is an even number and $y_i$ are odd numbers, $\left(n-6\right)$ $\left(⌊\frac{t_n}{n-6}⌋+2\right)$, $t_n$ are even numbers, meaning that a is an integer number. We also have

${\displaystyle \frac{\left(n-6\right)\left(⌊\frac{t_n}{n-6}⌋+2\right)-t_n}{2}}\ge {\displaystyle \frac{\left(n-6\right)\left(\frac{t_n}{n-6}+1\right)-t_n}{2}}={\displaystyle \frac{n-6}{2}}>0\mathrm{for}n>6,$

meaning that $a\in \mathbb{N}$. Moreover,

$a={\displaystyle \frac{\left(n-6\right)\left(⌊\frac{t_n}{n-6}⌋+2\right)-t_n}{2}}\le {\displaystyle \frac{\left(n-6\right)\left(\frac{t_n}{n-6}+2\right)-t_n}{2}}=n-6,$

meaning that $n-6-a$ is a non-negative integer number, as desired.

Now, if $n-6$ divides to $t_n,$ then $⌊\frac{t_n}{n-6}⌋=\frac{t_n}{n-6}$ is an odd number, meaning that $\left(y_7,\dots ,y_n\right)=\left(\frac{t_n}{n-6},\dots ,\frac{t_n}{n-6}\right)$ satisfies $y_7+\dots +y_n=t_n$ and minimizes

$d^2\left(\left(y_7,\dots ,y_n\right),\left({\displaystyle \frac{t_n}{n-6}},\dots ,{\displaystyle \frac{t_n}{n-6}}\right)\right),$

as desired, since $d^2\left(\left(y_7,\dots ,y_n\right),\left(\frac{t_n}{n-6},\dots ,\frac{t_n}{n-6}\right)\right)=0$.

If $n-6$ does not divide to $t_n$ and if we have a solution $\left(x_7,\dots ,x_n\right)$ with less than a values $x_i=⌊\frac{t_n}{n-6}⌋$, we can see that

$d^2\left(\left(x_7,\dots ,x_n\right),\left({\displaystyle \frac{t_n}{n-6}},\dots ,{\displaystyle \frac{t_n}{n-6}}\right)\right)>d^2\left(\left(y_7,\dots ,y_n\right),\left({\displaystyle \frac{t_n}{n-6}},\dots ,{\displaystyle \frac{t_n}{n-6}}\right)\right).$

If there are j values of i such that $x_i=⌊\frac{t_n}{n-6}⌋$ with $j<a$, then the other $a-j$ values $x_i$ satisfy $\frac{t_n}{n-6}-x_i>\frac{t_n}{n-6}-⌊\frac{t_n}{n-6}⌋$, as $⌊\frac{t_n}{n-6}⌋$ is the odd integer closest to $\frac{t_n}{n-6}$. The other $n-6-a$ values $x_i$ are not equal to $⌊\frac{t_n}{n-6}⌋$, meaning that they satisfy $x_i-\frac{t_n}{n-6}\ge ⌊\frac{t_n}{n-6}⌋+2-\frac{t_n}{n-6}$, as $⌊\frac{t_n}{n-6}⌋+2$ is the second integer that is closest to $\frac{t_n}{n-6}$. Thus, we have

$\begin{array}{c}{d}^2\left(\left(x_7,\dots ,x_{a-j},⌊{\displaystyle \frac{t_n}{n-6}}⌋,\stackrel{j)}{\dots },⌊{\displaystyle \frac{t_n}{n-6}}⌋,x_{a+1},\dots ,x_n\right),\left({\displaystyle \frac{t_n}{n-6}},\dots ,{\displaystyle \frac{t_n}{n-6}}\right)\right)\\ =\sum _{k=7}^{a-j}{\left({\displaystyle \frac{t_n}{n-6}}-x_k\right)}^2+j{\left({\displaystyle \frac{t_n}{n-6}}-⌊{\displaystyle \frac{t_n}{n-6}}⌋\right)}^2+\sum _{k=a+1}^n{\left(x_k-{\displaystyle \frac{t_n}{n-6}}\right)}^2\\ >a{\left({\displaystyle \frac{t_n}{n-6}}-⌊{\displaystyle \frac{t_n}{n-6}}⌋\right)}^2+\left(n-3-a\right){\left(⌊{\displaystyle \frac{t_n}{n-6}}⌋+2-{\displaystyle \frac{t_n}{n-6}}\right)}^2\\ =d^2\left(\left(y_7,\dots ,y_n\right),\left({\displaystyle \frac{t_n}{n-6}},\dots ,{\displaystyle \frac{t_n}{n-6}}\right)\right),\end{array}$

as desired.

If there are j values of i such that $x_i=⌊\frac{t_n}{n-6}⌋$ with $j>a$, then the $j-a$ values $x_i=⌊\frac{t_n}{n-6}⌋$ with $i\in \left\{a+1,\dots ,n\right\}$ satisfy

$\frac{t_n}{n-6}-x_i=\frac{t_n}{n-6}-⌊\frac{t_n}{n-6}⌋<⌊\frac{t_n}{n-6}⌋+2-\frac{t_n}{n-6}\le y_i-\frac{t_n}{n-6}$, as the strict inequality is equivalent to $\frac{t_n}{n-6}<⌊\frac{t_n}{n-6}⌋+1$. However, because $x_7+\dots +x_n=y_7+\dots +y_n=t_n$, there must be $s\le j-a$ values of i among the last $n-6-j$ indices such that $x_i\ge ⌊\frac{t_n}{n-6}⌋+4$, which is to say that $x_{j+1}=y_{j+1}+a_{j+1}$, …, $x_{j+s}=y_{j+s}+a_{j+s}$ with $a_{j+1}\ge 2$, …, $a_{j+s}\ge 2$ and $a_{j+1}+\dots +a_{j+s}=2$ $\left(j-a\right)$. We also have $x_{a+1}=y_{a+1}-2$, …, $x_j=y_j-2$.

Now, for the values of i such that $x_i\ne y_i$ ($i=a+1,$ $\dots ,$ $j+s$), it is satisfied that

$\begin{array}{c}{x}_{a+1}^2+\dots +x_{j+s}^2\\ ={\left(y_{a+1}-2\right)}^2+\dots +{\left(y_j-2\right)}^2+{\left(y_{j+1}+a_{j+1}\right)}^2+\dots +{\left(y_{j+s}+a_{j+s}\right)}^2\\ =y_{a+1}^2+\dots +y_{j+s}^2-4\left(y_{a+1}+\dots +y_j\right)\\ +4\left(j-a\right)+2a_{j+1}{y}_{j+1}+\dots +2a_{j+s}{y}_{j+s}+a_{j+1}^2+\dots +a_{j+s}^2\\ \ge y_{a+1}^2+\dots +y_{j+s}^2\iff \end{array}$

$-4\left(y_{a+1}+\dots +y_j\right)+4\left(j-a\right)+2a_{j+1}{y}_{j+1}+\dots +2a_{j+s}{y}_{j+s}+a_{j+1}^2+\dots +a_{j+s}^2\ge 0.$

However, as we have $y_{a+1}=\dots =y_{j+s}=⌊\frac{t_n}{n-6}⌋+2$, we need to prove that

$-4\left(j-a\right)y_{a+1}+4\left(j-a\right)+2y_{a+1}\left(a_{j+1}+\dots +a_{j+s}\right)+a_{j+1}^2+\dots +a_{j+s}^2$

$=-4\left(j-a\right)y_{a+1}+4\left(j-a\right)+4\left(j-a\right)y_{a+1}+a_{j+1}^2+\dots +a_{j+s}^2$

$=4\left(j-a\right)+a_{j+1}^2+\dots +a_{j+s}^2\ge 0$

and this inequality is trivially true. This implies that $x_7^2+\dots +x_n^2\ge y_7^2+\dots +y_n^2$ in this case as well.

If there are j values of i such that $x_i=⌊\frac{t_n}{n-6}⌋$ with $j=a$, then because $\left(x_7,\dots ,x_n\right)\ne \left(y_7,\dots ,y_n\right)$, there is at least one value of $i>a$ such that

${\left(x_i-{\displaystyle \frac{t_n}{n-6}}\right)}^2>{\left(y_i-{\displaystyle \frac{t_n}{n-6}}\right)}^2,$

being ${\left(x_i-\frac{t_n}{n-6}\right)}^2\ge {\left(y_i-\frac{t_n}{n-6}\right)}^2$ for the rest of values $i>a$, as $⌊\frac{t_n}{n-6}⌋+2$ is the second odd integer closest to $\frac{t_n}{n-6}$. Thus, we also have

$d^2\left(\left(x_7,\dots ,x_n\right),\left({\displaystyle \frac{t_n}{n-6}},\dots ,{\displaystyle \frac{t_n}{n-6}}\right)\right)>d^2\left(\left(y_7,\dots ,y_n\right),\left({\displaystyle \frac{t_n}{n-6}},\dots ,{\displaystyle \frac{t_n}{n-6}}\right)\right)$

in this case, as desired. □

Corollary 1.

In the assumptions of Proposition 10, it is satisfied that if $n-6$ does not divide to $t_n$, then

$\begin{array}{c}{m}_n=\\ {\displaystyle \frac{\left(n-6\right)\left(⌊\frac{t_n}{n-6}⌋+2\right)-t_n}{2}}{⌊{\displaystyle \frac{t_n}{n-6}}⌋}^2+\\ \left(n-6-{\displaystyle \frac{\left(n-6\right)\left(⌊\frac{t_n}{n-6}⌋+2\right)-t_n}{2}}\right){\left(⌊{\displaystyle \frac{t_n}{n-6}}⌋+2\right)}^2.\end{array}$

Proposition 11.

Let n be an even number, $n>6$, $t_n\in \mathbb{N}$, and $m_n$ defined as in Proposition 10. Then, if $⌊\frac{t_n}{n-6}⌋$ is an even number, $m_n$ is attained when

$y_i=⌊\frac{t_n}{n-6}⌋$$-1$ or $y_i=⌊\frac{t_n}{n-6}⌋+1$ for $i=7,$ $\dots ,$ n ($m_n$ is attained when $y_i$ is one of the two odd numbers that are closest to $\frac{t_n}{n-6}$ for $i=7,$ $\dots ,$ n).

Proof. 

As in Proposition 10, there is a unique vector $\left(y_7,\dots ,y_n\right)$ satisfying the conditions of Proposition 11:

$a\left(⌊{\displaystyle \frac{t_n}{n-6}}⌋-1\right)+\left(n-6-a\right)\left(⌊{\displaystyle \frac{t_n}{n-6}}⌋+1\right)=$

$-2a+\left(n-6\right)\left(⌊{\displaystyle \frac{t_n}{n-6}}⌋+1\right)=t_n⟺a={\displaystyle \frac{\left(n-6\right)\left(⌊\frac{t_n}{n-6}⌋+1\right)-t_n}{2}}.$

Because n is an even number, $\left(n-6\right)$ $\left(⌊\frac{t_n}{n-6}⌋+1\right)$, $t_n$ are even numbers as well; thus, a is an integer number. We also have

${\displaystyle \frac{\left(n-6\right)\left(⌊\frac{t_n}{n-6}⌋+1\right)-t_n}{2}}>{\displaystyle \frac{\left(n-6\right)\frac{t_n}{n-6}-t_n}{2}}=0,$

meaning that $a\in \mathbb{N}$. Moreover,

$a={\displaystyle \frac{\left(n-6\right)\left(⌊\frac{t_n}{n-3}⌋+1\right)-t_n}{2}}\le {\displaystyle \frac{\left(n-6\right)\left(\frac{t_n}{n-6}+1\right)-t_n}{2}}={\displaystyle \frac{n-6}{2}},$

meaning that $n-6-a$ is a positive integer number, as desired.

For solutions $\left(x_7,\dots ,x_n\right)$ with $j<n-6-a$ values of i such that $x_i=⌊\frac{t_n}{n-6}⌋+1$, we assume without loss of generality that these values of i are in $\left\{a+1,\dots ,n-6\right\}$; as $⌊\frac{t_n}{n-6}⌋+1$ is the odd number closest to $\frac{t_n}{n-6}$ ($⌊\frac{t_n}{n-6}⌋$ being an even number), for the other $n-6-a-j$ values of i in $\left\{a+1,\dots ,n-6\right\}$ we have

$x_i-{\displaystyle \frac{t_n}{n-6}}>⌊{\displaystyle \frac{t_n}{n-6}}⌋+1-{\displaystyle \frac{t_n}{n-6}}=y_i-{\displaystyle \frac{t_n}{n-6}},$

while for the rest of the values i in $\left\{a+1,\dots ,n-6\right\}$ we have

$x_i-{\displaystyle \frac{t_n}{n-6}}=⌊{\displaystyle \frac{t_n}{n-6}}⌋+1-{\displaystyle \frac{t_n}{n-6}}=y_i-{\displaystyle \frac{t_n}{n-6}}.$

Moreover, for the a first values of i, because $⌊\frac{t_n}{n-6}⌋-1$ attains the second minimum distance of an odd integer to $\frac{t_n}{n-6}$, we have

${\displaystyle \frac{t_n}{n-6}}-x_i\ge {\displaystyle \frac{t_n}{n-6}}-\left(⌊{\displaystyle \frac{t_n}{n-6}}⌋-1\right)={\displaystyle \frac{t_n}{n-6}}-y_i,$

then

$d\left(\left(x_7,\dots ,x_n\right),\left({\displaystyle \frac{t_n}{n-6}},\dots ,{\displaystyle \frac{t_n}{n-6}}\right)\right)>d\left(\left(y_7,\dots ,y_n\right),\left({\displaystyle \frac{t_n}{n-6}},\dots ,{\displaystyle \frac{t_n}{n-6}}\right)\right),$

as desired.

If there are j values of i such that $x_i=⌊\frac{t_n}{n-6}⌋+1$ with $j=n-6-a$, then, because $\left(x_7,\dots ,x_n\right)\ne \left(y_7,\dots ,y_n\right)$, there is at least one value of $i<a$ such that

${\left(x_i-{\displaystyle \frac{t_n}{n-6}}\right)}^2>{\left(y_i-{\displaystyle \frac{t_n}{n-6}}\right)}^2,$

with ${\left(x_i-\frac{t_n}{n-6}\right)}^2\ge {\left(y_i-\frac{t_n}{n-6}\right)}^2$ for the rest of values $i>a$, as $⌊\frac{t_n}{n-6}⌋-1$ is the second odd integer closest to $\frac{t_n}{n-6}$. Thus, we have

$d^2\left(\left(x_7,\dots ,x_n\right),\left({\displaystyle \frac{t_n}{n-6}},\dots ,{\displaystyle \frac{t_n}{n-6}}\right)\right)>d^2\left(\left(y_7,\dots ,y_n\right),\left({\displaystyle \frac{t_n}{n-6}},\dots ,{\displaystyle \frac{t_n}{n-6}}\right)\right)$

in this case as well, as desired.

If there are j values of i such that $x_i=⌊\frac{t_n}{n-6}⌋+1$ with $j>n-6-a$, then the $j-\left(n-6-a\right)$ values $x_i$ with $x_i=⌊\frac{t_n}{n-6}⌋+1,i\in \left\{1,\dots ,a\right\}$ satisfy

${\displaystyle \frac{t_n}{n-6}}-x_i={\displaystyle \frac{t_n}{n-6}}-⌊{\displaystyle \frac{t_n}{n-6}}⌋<⌊{\displaystyle \frac{t_n}{n-6}}⌋+2-{\displaystyle \frac{t_n}{n-6}}\le y_i-{\displaystyle \frac{t_n}{n-6}},$

as the inequality is equivalent to $\frac{t_n}{n-6}<⌊\frac{t_n}{n-6}⌋+1$. However, because

$x_7 +\dots + x_n=y_7+\dots +y_n=t_n,$

there must be $s\le j-a$ values of i among the last $n-6-j$ indices such that

$x_i\ge ⌊{\displaystyle \frac{t_n}{n-6}}⌋+4,$

that is to say,

$x_{j+1}=y_{j+1}+a_{j+1},\dots ,x_{j+s}=y_{j+s}+a_{j+s}$

with

$a_{j+1}\ge 2,\dots ,a_{j+s}\ge 2$

and

$a_{j+1}+\dots +a_{j+s}=2\left(j-a\right).$

We also have

$x_{a+1}=y_{a+1}-2,\dots ,x_j=y_j-2.$

Now, for the values of i such that $x_i\ne y_i$ ($i=a+1,$ $\dots ,$ $j+s)$, it is satisfied that

$\begin{array}{c}{x}_{a+1}^2+\dots +x_{j+s}^2\\ ={\left(y_{a+1}-2\right)}^2+\dots +{\left(y_j-2\right)}^2+{\left(y_{j+1}+a_{j+1}\right)}^2+\dots +{\left(y_{j+s}+a_{j+s}\right)}^2\\ =y_{a+1}^2+\dots +y_{j+s}^2-4\left(y_{a+1}+\dots +y_j\right)+4\left(j-a\right)\\ +2a_{j+1}{y}_{j+1}+\dots +2a_{j+s}{y}_{j+s}+a_{j+1}^2+\dots +a_{j+s}^2\\ \ge y_{a+1}^2+\dots +y_{j+s}^2\iff \end{array}$

$-4\left(y_{a+1}+\dots +y_j\right)+4\left(j-a\right)+2a_{j+1}{y}_{j+1}+\dots +2a_{j+s}{y}_{j+s}+a_{j+1}^2+\dots +a_{j+s}^2\ge 0.$

However, as we have $y_{a+1}=\dots =y_{j+s}=⌊\frac{t_n}{n-6}⌋+2$, we need to prove that

$-4\left(j-a\right)y_{a+1}+4\left(j-a\right)+2y_{a+1}\left(a_{j+1}+\dots +a_{j+s}\right)+a_{j+1}^2+\dots +a_{j+s}^2=$

$-4\left(j-a\right)y_{a+1}+4\left(j-a\right)+4\left(j-a\right)y_{a+1}+a_{j+1}^2+\dots +a_{j+s}^2=$

$4\left(j-a\right)+a_{j+1}^2+\dots +a_{j+s}^2\ge 0$

and this inequality is trivially true. This implies that $x_7^2+\dots +x_n^2\ge y_7^2+\dots +y_n^2$ in this case as well. Then, the minimum is attained in the vector with $\frac{\left(n-6\right)\left(⌊\frac{t_n}{n-6}⌋+1\right)-t_n}{2}$ coordinates with value $⌊\frac{t_n}{n-6}⌋$ $-1$ and $n-6-$ $\frac{\left(n-6\right)\left(⌊\frac{t_n}{n-6}⌋+1\right)-t_n}{2}$ coordinates with value $⌊\frac{t_n}{n-6}⌋$ $+1$, as desired. □

Now, we are ready to improve the upper bound.

Proposition 12.

It is satisfied that $h_{106}\le 480$.

Proof. 

The bound of [5] provides $h_{106}\le 481$. Assuming that $h_{106}=481$ and that $P=\left\{p_1,\dots ,p_{106}\right\}$ is a set attaining $h_{106}$ such that the graph G of the halving lines of P has three vertices of degree 1 ($p_1,\dots ,p_3$) and three vertices of degree 3 ($p_4,$ $\dots ,$ $p_6$), $p_7,$ $\dots ,$ $p_{106}$ satisfy $deg\left(p_7\right)+\dots +deg\left(p_{106}\right)=2\times 481-12$, meaning we are in the case of Proposition 10 with $n=106$, $t_{106}=2\times 481-12$, where 9 and 11 are the two odd numbers closest to $\frac{t_{106}}{106-6}=9.5$. Following Proposition 10, this implies that

$de{g}^2\left(p_7\right)+\dots +de{g}^2\left(p_{106}\right)\ge m_{106}=75\times 9^2+\left(100-75\right){11}^2=9100,$

and then

$\sum _{i=1}^{106}de{g}^2\left(p_i\right)\ge 9130.$

Thus, from (1) we have $\mathrm{cr}\left(G\right)\le 250$.

However, the lower bound of the proof of Proposition 6 provides

$\mathrm{cr}\left(G\right)\ge {\displaystyle \frac{7}{3}}{h}_n-{\displaystyle \frac{25}{3}}\left(n-2\right)={\displaystyle \frac{7}{3}}481-{\displaystyle \frac{25}{3}}\left(106-2\right)=255.667,$

which is a contradiction. For the other possible combinations of degrees of the six vertices provided by Lemma 1, we arrive at contradictions in a similar way. In this way, $h_{106}\le 480$, as desired. □

Remark 13.

The argument of the proof of Proposition 12 is not sufficient to obtain the reduction $h_{106}\le 479$.

6. Conclusions

In the additive constant, we have improved the asymptotic upper bound on the maximum number of halving lines for sets of points in the plane with an even number of points. To accomplish this, we have applied known lower and upper bounds for the rectilinear crossing number of a graph combined with obtained lower bounds on the degrees of the vertices of the halving line graphs. In addition, for sets with a small number of points, we have improved the to-date best upper bounds for the maximum number of halving lines. The improvement was achieved for sets of n points with $n\ge 106$. This yields an improvement of the rectilinear crossing number for complete graphs with n vertices. A future challenge is to expand the developed techniques for sets with $n\le 104$ points, for which the upper bound of [5] for the maximum number of halving lines remains the best upper bound. For this purpose, it is necessary to obtain lower bounds for ${\displaystyle \sum _{i=1}^n}de{g}^2\left(p_i\right)$ adapted to these small values of n. For these values, the achieved lower bound is insufficient to obtain a contradiction.

Author Contributions

All three authors have made significant contributions to the creation of this paper. Conceptualization, M.L. and J.R.; methodology, M.L. and J.R.; formal analysis, all authors; investigation, all authors; writing—original draft preparation, all authors; writing—review and editing, J.R. and E.A.; supervision, all authors. All authors have read and agreed to the published version of the manuscript.

Data Availability Statement

Data are contained within the article.

Conflicts of Interest

The authors declare no conflicts of interest.

Footnotes

Disclaimer/Publisher’s Note: The statements, opinions and data contained in all publications are solely those of the individual author(s) and contributor(s) and not of MDPI and/or the editor(s). MDPI and/or the editor(s) disclaim responsibility for any injury to people or property resulting from any ideas, methods, instructions or products referred to in the content.

References

1. Ábrego, B.M.; Cetina, M.; Fernández-Merchant, S.; Leaños, J.; Salazar, G. 3-symmetric and 3-decomposable geometric drawings of K_n. Discret. Appl. Math.; 2010; 158, pp. 1240-1258. [DOI: https://dx.doi.org/10.1016/j.dam.2009.09.020]

2. Espinoza-Valdez, A.; Leaños, J.; Ndjatchi, C.; Ríos-Castro, L.M. An Upper Bound Asymptotically Tight for the Connectivity of the Disjointness Graph of Segments in the Plane. Symmetry; 2021; 13, 1050. [DOI: https://dx.doi.org/10.3390/sym13061050]

3. Tóth, G. Point sets with many k-sets. Discret. Comput. Geom.; 2001; 26, pp. 187-194. [DOI: https://dx.doi.org/10.1007/s004540010022]

4. Dey, T.K. Improved bounds for planar k-sets and related problems. Discret. Comput. Geom.; 1998; 19, pp. 373-382. [DOI: https://dx.doi.org/10.1007/PL00009354]

5. Ábrego, B.M.; Cetina, M.; Fernández-Merchant, S.; Leaños, J.; Salazar, G. On (≤k)-edges, crossings, and halving lines of geometric drawings of K_n. Discret. Comput. Geom.; 2012; 48, pp. 192-215. [DOI: https://dx.doi.org/10.1007/s00454-012-9403-y]

6. Rodrigo, J.; López, M.D. An improvement of the lower bound on the maximum number of halving lines in planar sets with 32 points. Electron. Notes Discret. Math.; 2018; 68, pp. 305-310. [DOI: https://dx.doi.org/10.1016/j.endm.2018.06.052]

7. Ackerman, E. On topological graphs with at most four crossings per edge. Comput. Geom.; 2019; 85, 101574. [DOI: https://dx.doi.org/10.1016/j.comgeo.2019.101574]

8. Aichholzer, O.; García, J.; Orden, D.; Ramos, P. New lower bounds for the number of ≤k-edges and the rectilinear crossing number of K_n. Discret. Comput. Geom.; 2007; 38, pp. 1-14. [DOI: https://dx.doi.org/10.1007/s00454-007-1325-8]

9. Rodrigo, J.; Merchán, S.; Magistrali, D.; López, M.D. An Improvement of the Lower Bound on the Minimum Number of ≤k-Edges. Mathematics; 2021; 9, 525. [DOI: https://dx.doi.org/10.3390/math9050525]

10. Pach, J.; Radoicic, R.; Tardos, G.; Toth, G. Improving the Crossing Lemma by Finding More Crossings in Sparse Graphs. Discret. Comput. Geom.; 2006; 36, pp. 527-552. [DOI: https://dx.doi.org/10.1007/s00454-006-1264-9]

11. Lovasz, L.; Vesztergombi, K.; Warner, U.; Welzl, E. Convex Quadrilaterals and k-sets. Contemp. Math.; 2004; 342, pp. 139-148.