On the Depth of a Point in a Point System
Abstract Generated abstract
The paper introduces the depth of a point in a finite planar point system, defined by the minimum number of system points on either side of a line through that point and another system point. It proves several structural properties of depth, including inequalities for points lying in one section, behavior under convex subsystems, and invariance of depths when points are ordered by nondecreasing depth and higher depth points are removed. Using these results, the paper generalizes Birch’s theorem on partitioning \(3N\) planar points into triangles with a common point: for a point \(q\), the maximum number of vertex-disjoint triangles containing \(q\) is shown to be the minimum of \(\lfloor n/3\rfloor\) and the depth of \(q\) in the remaining point system.
Full Text
ON THE DEPTH OF A POINT IN A POINT SYSTEM
G. G. PESTOV
(Presented by the Department of Engineering and Computational Mathematics)
In the present article the concept of the depth of a point in a point system is introduced; some properties of point systems connected with the concept of depth are studied. Then one result of Birch is generalized.
Definition. Let \(S_n\) be a subsystem of \(S_{n+1}\), \(a \in S_{n+1}\). The quantity
\[ d(a,S_n)=\min_{x\in S_n}\{\overline{R(a,x)}\cap S_n,\ \overline{L(a,x)}\cap S_n\} \]
will be called the depth of the point \(a\) in \(S_n\). Here \(\overline{M}\) denotes the number of elements of the set \(M\).
Apparently, the concept of the depth of a point has not previously been introduced, although there are results concerning depth. Namely, the following is known.
Theorem. In the plane \(n\) points \(a_1,a_2,\ldots,a_n\) are given. There exists a point \(b\) in this plane such that on each side of any line passing through the point \(b\) and not passing through the points \(a_1,a_2,\ldots,a_n\), there are at least
\[ \left[\frac{n}{3}\right] \]
points \([1]\).
Some theorems on depth
Theorem 1. If \(c \in R(a,b)\), then
\[ \overline{R(a,b)} \ge d(c,S_n)+1. \]
Proof. Consider the subsystem \(S_m \in S_n\), consisting of \(L(a,b)\) and the points \(a,b,c\). Sections in the system \(S_n\) will be denoted by \(L(x,y)\) and \(R(x,y)\), and sections in \(S_m\) by \(L'(x,y)\) and \(R'(x,y)\). We have \(R'(a,b)=c\), that is, \(L'(b,a)=c\). Then, by the lemma on an exterior point \([3]\), the point \(c\) is an exterior point in the system \(S_m\); consequently, there is a point \(d\in S_m\), \(d\ne c\), such that
\[ R'(c,d)=0. \]
But since the system \(S_m\) is obtained from \(S_n\) by discarding \(\overline{R(a,b)}-1\) points, in the system \(S_n\)
\[ \overline{R(c,b)}\le \overline{R(a,b)}-1. \]
By the definition of depth, \(\overline{R(c,b)}\ge d(c,S_n)\), that is, \(d(c,S_n)+1\le \overline{R(a,b)}\), which was required to prove.
Definition. We shall call a system \(S\) convex if all points of the system are exterior.
Otherwise, \(S\) is called convex if the filling coefficient [5]
\[ P(S)=0. \]
Theorem 2. Let \(S' \in S\), let \(S'\) be convex, let \(a \in S\), and in the system \(S''=S'\cup a\) let the point \(a\) be interior. Then
\[ d(a,S) \geq 1+\min_{x\in S'} d(x,S). \]
Proof. Since \(a\) is an interior point of \(S''\), by Carathéodory’s lemma [3] there exist three points \(x_1,x_2,x_3\) such that \(a\) lies inside \(\Delta x_1x_2x_3\). Let \(b\in S\). Then in the five-tuple \((a,x_1,x_2,x_3,b)\) the point \(a\) is interior, that is, it is not exterior.
Indeed,
\[ R(a,x_i)\ne \overline{0},\qquad L(a,x_i)\ne \overline{0},\qquad i=1,2,3. \]
Consequently, \(a\) cannot have two adjacent exterior points and therefore is not exterior in the five-tuple \((a,x_1,x_2,x_3,b)\) [3].
Therefore,
\[ R(a,b)\cap S_5\ne \overline{0},\qquad L(a,b)\cap S_5\ne \overline{0}. \]
Let \(x_{i_1}\in R(a,b)\), \(x_{i_2}\in L(a,b)\). Then, on the basis of Theorem 1,
\[ R(a,b)\geq d(x_{i_1},S)+1,\qquad L(a,b)\geq d(x_{i_2},S)+1. \]
Hence
\[ d(a,S)=\min_{b\in S}\{\overline{R(a,b)},\overline{L(a,b)}\}\geq \]
\[ \geq \min_i d(x_i,S)+1 \geq \min_{x\in S'} d(x,S)+1. \]
That is,
\[ d(a,S)\geq \min d(x,S)+1. \]
Theorem 3. Let the points \(x_1,x_2,\ldots,x_n\) of the system \(S_n\) be arranged in nondecreasing order of depth.
Denote by \(S_m\) the subsystem of \(S_n\) consisting of the first \(m\) points \(x_1,x_2,\ldots,x_m\). The equalities
\[ d(x_i,S_m)=d(x_i,S_n),\qquad i=1,2,\ldots,m \]
hold.
Proof. We shall show that
\[ d(x_i,S_{n-1})=d(x_i,S_n),\qquad i=1,2,\ldots,n-1. \]
It is clear that
\[ d(x_i,S_{n-1})\leq d(x_i,S_n). \tag{1} \]
We shall prove the reverse inequality.
For any
\[ y\ne x_n:\quad d(x_i,S_n)\leq R(x_i,y,S_n) \]
and
\[ d(x_i,S_n)\leq L(x_i,y,S_n). \]
Here by \(R(x,y,S)\) and \(L(x,y,S)\) we denote the sections in the system \(S\).
Let \(x_n\in R(x_i,y,S_n)\). Then by Theorem 1:
\[ \overline{R(x_i,y,S_n)}\geq d(x_n,S_n)+1. \]
In the system \(S_{n-1}\),
\[ \overline{R(x_i,y,S_{n-1})}=\overline{R(x_i,y,S_n)}-1. \]
Consequently,
\[ \overline{R(x_i,y,S_{n-1})}\geq d(x_n,S_n) \]
and
\[ \overline{L(x_i,y,S_n)}=\overline{L(x_i,y,S_{n-1})}>d(x_i,S_n). \]
Hence
\[ d(x_i,S_{n-1})=\min\{R(x_i,y,S_{n-1}),\ L(x_i,y,S_{n-1})\}\geq \]
\[ \geq \min\{d(x_n,S_n),\ d(x_i,S_n)\}. \]
Since
\[ d(x_n,S_n)\geq d(x_i,S_n), \]
we have
\[ d(x_i,S_{n-1})\geq d(x_i,S_n); \tag{2} \]
comparing (1) and (2), we find
\[ d(x_i,S_{n-1})=d(x_i,S_n). \]
Applying induction, we obtain
\[ d(x_i,S_m)=d(x_i,S_n),\quad i\leq m<n. \]
Corollary. In the system \(S_{2n+1}\), for two points \(x,y\in S_{2n+1}\), \(x\neq y\), the equality
\[ d(x,S_{2n+1})=d(y,S_{2n+1})=n. \tag{*} \]
cannot hold.
Proof. Suppose that \((*)\) holds. Then, by Theorem 3,
\[ d(x_{2n},S_{2n+1})=d(x_{2n},S_{2n}), \]
that is,
\[ d(x_{2n},S_{2n})=n. \tag{3} \]
But the latter equality is impossible.
Indeed, let \(y\in S_{2n}\) be such that
\[ \overline{R(x_{2n},y)}=n. \]
Define the double cyclic function in \(S_{2n}\) by the condition
\[ N(x_{2n},y,S_{2n})=1. \]
Let \(y_2\) be such that
\[ |N(x_{2n},y_2,S_{2n})|=2, \]
and, for definiteness, let
\[ N(x_{2n},y_2,S_{2n})=2. \]
Then, if \(z\in R(x_{2n},y,S_{2n})\), the order function
\[ \xi(x_{2n},y_1,z)=\operatorname{sgn}\{N(x_{2n},z_1,S_{2n})N(x_{2n},y_1,S_{2n})\times \]
\[ \times [N^2(x_{2n},z,S_{2n})-N^2(x_{2n},y_1,S_{2n})]\} =\operatorname{Sgn}N(x_{2n},z,S_{2n})<0. \]
and
\[ |N(x_{2n},z,S_{2n})|>2. \]
Since
\[ y_2\in R(x_{2n},y_1,S_{2n}), \]
we have
\[ \xi(x_{2n},y_2,z)=\operatorname{Sgn}\{N(x_{2n},z,S_{2n})N(x_{2n},y_2,S_{2n})[N^2(x_{2n}, \]
\[ z,S_{2n})-N^2(x_{2n},y_2,S_{2n})]\} =\operatorname{Sgn}N(x_{2n},z,S_{2n})<0, \]
that is,
\[ z\in R(x_{2n},y_2,S_{2n}). \]
Thus
\[ R(x_{2n},y_1,S_{2n})\subset R(x_{2n},y_2,S_{2n}). \tag{4} \]
Moreover,
\[ y_1\in R(x_{2n},y_1,S_{2n}), \tag{5} \]
and
\[ \xi(x_{2n},y_2,y_1)=\operatorname{Sgn}\{N(x_{2n},y_1,S_{2n})N(x_{2n},y_2,S_{2n})\times \]
\[ \times [N^2(x_{2n},y_1,S_{2n})-N^2(x_{2n},y_2,S_{2n})]\}=-1. \]
Consequently:
\[ y_1\in R(x_{2n},y_2,S_{2n}). \tag{6} \]
From (4), (5), (6)
\[ n=\overline{R(x_{2n},y_1,S_{2n})}<\overline{R(x_{2n},y_2,S_{2n})}. \]
Thus
\[ \overline{L(x_{2n},y_2,S_{2n})}\leqslant n-1. \]
Whence \(d(x_{2n},S_{2n})<n-1\), which contradicts (3); consequently, (3) is impossible.
Toward Birch’s theorem
In Birch’s paper [2] the following is proved.
Theorem. In the plane, given \(3N\) points, they can be divided into \(N\) triples so that \(N\) triangles with vertices at these points have a common point.
Using the notion of the depth of a point in a system, we shall obtain a more general result.
Denote by \(t(q)\) the largest number of triangles without common vertices, with vertices at the points \(S_{n+1}\), that contain the point \(q\in S_{n+1}\).
The following holds.
Theorem 4.
\[ t(q)=\min\left\{\left[\frac{n}{3}\right],\,d(q,S_n)\right\}. \]
Proof. 1. Let the point \(\mu_0\) be such that
\[ L(q,\mu_0)=d,\quad \text{where } d=d(q,S_{n+1}). \]
In the subsystem \(S'=L(q,\mu_0)\cup \mu_0\cup q\) we introduce a double cyclic function by the condition
\[ N(q,\mu_0,S')=1. \]
To each point \(\mu\in L(q,\mu_0)\) assign the number \(m=N(q,\mu,S')-1\), and denote \(\mu\) by \(\mu_m\).
Consider the subsystem \(S''=R(q,\mu_0)\cup q\cup \mu_0\). Introduce in \(S''\) a cyclic function by the condition
\[ N(q,\mu_0,S'')=n-d=p. \]
The point \(\pi\in R(q,\mu_0)\cup\mu_0\) will be denoted by \(\pi_k\), if
\[ N(q,\pi,S'')=k,\quad k=1,2,\ldots,p. \]
2. Lemma 1. If \(p<2d\), then there is a point \(\pi_j\) which, together with \(\mu_1\) and \(\mu_d\), gives a covering triangle.
Proof. Denote
\[ \alpha_i=\overline{L(q,\mu_i)\cap S''}. \]
Here \(L(x,y)\) and \(R(x,y)\) are sections in \(S_{n+1}\).
Then
\[ \text{a)}\quad 1\leqslant \alpha_1\leqslant p-d, \]
\[ \text{b)}\quad d\leqslant \alpha_d \quad [4]. \]
But from \(p<2d\) it follows that
\[ p-d<d,\quad \alpha_1<\alpha_d. \]
Thus
\[ F=\bigl[\{L(q,\mu_1)\cap S''\}\setminus\{L(q,\mu_d)\cap S''\}\bigr]\ne \overline{0}. \]
Let \(\pi_j\in F\). Then \(\Delta_{\mu_1\pi_j\mu_d}\) contains the point \(q\).
- Now discard the points \(\mu_1,\pi_j,\mu_d\) in the system \(S_{n+1}\); we obtain the subsystem \(S_{n-2}\). We shall show that
\[ d(q,S_{n-2})=d-2. \]
In fact,
\[ \overline{L(q,\pi_p,S_{n-2})}=d-2, \]
therefore
\[ d(q,S_{n-2})\le n-2. \]
On the other hand,
\[ d(q,S_{n-2})= \min_{\mu\in S_{n-2}}\{\overline{L(q,\mu,S_{n-2})},\overline{R(q,\mu,S_{n-2})}\}\ge \]
\[ \ge \min\{\overline{L(q,\mu,S_{n+1})}-2,\overline{R(q,\mu,S_{n+1})}-2\} =d(q,S_{n+1})-2. \]
Consequently,
\[ d(q,S_{n-2})\ge d(q,S_{n+1})-2=d-2. \]
Whence
\[ d(q,S_{n-2})=d(q,S_{n+1})-2. \]
- Let \(S_{n+1}\) be such that \(p<2d\), that is,
\[ d(q,S_{n+1})>\left[\frac{n}{3}\right]. \]
Construct the subsystem \(S_{n-2}\) as described in the preceding item; then, starting from \(S_{n-2}\), construct \(S_{n-5}\) in the same way, and so on, until we obtain \(S_{n-3k+1}\), in which for the first time
\[ p_k=p-k\ge 2(d-2k)=2d_k, \]
that is,
\[ d(q,S_{n-3k+1})\le \left[\frac{n-3k}{3}\right]. \]
Thus, if we show that in \(S_{n-3k+1}\) there are exactly \(\left[\frac{n}{3}\right]-k\) covering triangles, then in \(S_{n+1}\) there will be exactly \(\left[\frac{n}{3}\right]\) covering triangles.
- Thus it remains to prove that the following holds.
Lemma 2. If \(d(q,S_{n+1})\le \left[\frac{n}{3}\right]\) and, consequently, \(p\ge 2d\), then
\[ t(q,S_{n+1})=d(q,S_{n+1}). \]
Proof. We carry out induction on the number of points in the system \(S_{m+1}\). For \(m=2,3,4\) Lemma 2 is trivial.
Suppose that for all \(m\le n-3\) Lemma 2 is true. We shall show that it is also true for \(m=n\).
In the system \(S_{n+1}\),
\[ \pi_d\in L(q,\mu_d,S_{n+1}), \]
since \(d\le a_d\).
The point \(\pi_p\in R(q,\mu_d,S_{n+1})\). Consequently, \(\triangle \pi_d\pi_p\mu_d\) contains \(q\).
Consider the subsystem \(S_{n-2}\), obtained from \(S_n\) by discarding the points \(\pi_d,\pi_p,\mu_d\).
We shall show that
\[ d(q,S_{n-2})=d(q,S_{n+1})-1. \]
Let \(y\in S_{n-2}\); estimate
\[ \min\{\overline{R(q,y,S_{n-2})},\overline{L(q,y,S_{n-2})}\}. \]
Three cases are possible:
\[ \text{a)}\qquad \mu_d\in L(q,y,S_{n+1});\quad \pi_p,\pi_d\in R(q,y,S_{n+1}) \]
or
\[ [\mu_d\in R(q,y,S_{n+1});\quad \pi_p,\pi_d\in L(q,y,S_{n+1})]. \]
Then
\[ \overline{L(q,y,S_{n-2})}=\overline{L(q,y,S_{n+1})}\geq d-1, \tag{7} \]
\[ \overline{R(q,y,S_{n-2})}=\overline{R(q,y,S_{n+2})}-2\geq (p-d+1)-2\geq d-1. \]
Here we have used the inequality \(p\leq 2d\). Consequently,
\[ \overline{R(q,y,S_{n-2})}\geq d-1. \tag{8} \]
b) Let
\[ \pi_p\in R(q,y,S_{n+1});\qquad \pi_d,\psi_d\in L(q,y,S_{n+1}) \]
or \(\left[\pi_p\in L(q,y,S_{n+1});\quad \pi_d,\psi_d\in R(q,y,S_{n+1})\right]\).
Then
\[ L(q,y,S_{n-2})=L(q,y,S_{n+1})-2\geq (d+1)-2=d-1. \tag{9} \]
Further,
\[ \overline{R(q,y,S_{n-2})}=\overline{R(q,y,S_{n+1})}-1\geq d-1, \]
\[ \overline{R(q,y,S_{n-2})}\geq d-1. \tag{10} \]
c) Finally, let
\[ \pi_d\in L(q,y,S_{n+1});\qquad \psi_d,\pi_p\in R(q,y,S_{n+1}) \]
or
\[ \left(\pi_d\in R(q,y,S_{n+1});\qquad \psi_d,\pi_p\in L(q,y,S_{n+1})\right). \]
In this case
\[ \overline{R(q,y,S_{n-2})}=\overline{R(q,y,S_{n+1})}-2=(d+1)-2=d-1. \tag{11} \]
On the other hand,
\[ \overline{L(q,y,S_{n-2})}=\overline{L(q,y,S_{n+1})}-1\geq d-1. \tag{12} \]
From (7)—(12) it follows that
\[ d(q,S_{n-2})=d-1. \]
At the same time, \(d_1=d-1,\ p_1=p-2\), and therefore
\[ 2d_1=2d-2\leq p-2=p_1, \]
that is,
\[ 2d_1\leq p_1. \]
- Thus, after discarding one covering triangle \(\Delta\pi_d\pi_p\psi_d\), we have obtained a system \(S_{n-2}\), in which \(p_1\geq 2d_1\).
By assumption, Lemma 2 is true for \(S_{n-2}\). Therefore in \(S_{n-2}\) there exist \(t(q,S_{n-2})=d_1\) covering triangles. Consequently, in \(S_{n+1}\) there exist \(t(q,S_{n+1})=d_1+1=d\) covering triangles. Thus, Lemma 2 is proved. Hence Theorem 4 is proved.
References
- I. M. Yaglom, V. G. Boltyanskii. Convex Figures. 1951.
- B. J. Birch. On \(3N\) points in a plane. Proc. Cambridge Philos. Soc., 55, No. 4, 289—293, 1959.
- G. G. Pestov. Axiomatization of finite systems. Article in the present collection.
- G. G. Pestov. Some extremal problems in the theory of point systems. Article in the present collection.
- G. G. Pestov. On some numerical characteristics of point systems. Article in the present collection.