Necessary Criteria for the Least Convexity of a Point System
Abstract Generated abstract
This paper derives necessary conditions for a planar point system to be minimally, or least, convex, using orientation functions and pair indices that count points on either side of directed pairs. By adjoining or replacing points and comparing the resulting numbers of convex quadruples, it obtains inequalities that must hold for every pair of points in a least convex system. The main results are three criteria expressed first through signed sums over separating pairs and then through the difference between the numbers of nonconvex and convex quadruples containing a fixed pair. These formulas provide testable constraints on candidate minimally convex configurations.
Full Text
Necessary Criteria for the Minimum Convexity of a Point System
G. G. Pestov
(Presented by the Department of Engineering and Computational Mathematics)
Let \(S_n\) be a least convex point system [1], \(a,b\in S_n\). Introduce the system \(S' = S_n \cup \{b_1\}\):
\[ \xi'(x,y,z)= \begin{cases} \xi(x,y,z), & \text{if } x,y,z\ne b_1,\\ \xi(x,y,b), & \text{if } x,y\ne b,\ z=b_1,\\ \xi(a,b,x), & \text{if } x=b_1,\ y=b,\\ +1, & \text{if } x=a,\ y=b,\ z=b_1. \end{cases} \]
Denote by \(\gamma_{ij}, \gamma'_{ij}\) the index of the pair \(x_i,x_j\) in the systems \(S\) and \(S'\):
\[ \gamma_{ij}=|L(x_i,x_j)|-|R(x_i,x_j)|,\qquad \gamma'_{ij}=|L'(x_i,x_j)|-|R'(x_i,x_j)|. \]
Introduce the system \(S''\) in the following way: \(S''=(S_n\setminus\{a\})\cup\{b_2\}\). Let \(d\) be such that
\[ L(d,b)=\left[\frac{n-1}{2}\right]. \]
Set:
\[ \xi''(x,y,z)= \begin{cases} \xi(x,y,z), & \text{if } x,y,z\ne b_2,\\ \xi(x,y,b), & \text{if } x,y\ne b,\ z=b_2,\\ \xi(d,b,x), & \text{if } x=b_2,\ y=b,\\ +1, & \text{if } x=a,\ y=b,\ z=b_2. \end{cases} \]
a)
\[ C(S'\setminus\{a\})-C(S'\setminus\{b_1\})= \]
\[ =\sum_{\substack{i<j\\ x_i,x_j\,|\,\xi'(x_i,x_j,a)\xi'(x_i,x_j,b)<0}} \gamma'_{ij}\,\xi'(b_1,x_i,x_j)\xi'(a,b_1,x_i)\xi'(a,b_1,x_j) \]
\[ \tag{1} =\sum_{\substack{i<j\\ x_i,x_j\,|\,\xi(x_i,x_j,a)\xi(x_i,x_j,b)<0}} \gamma'_{ij}\,\xi(b,x_i,x_j)\xi(a,b,x_i)\xi(a,b,x_j) \qquad(\text{see }[2]). \]
Further, for \(x_i,x_j\in S_n\):
\[ \gamma'_{ij}=\sum_{z\in S'}\xi'(x_i,x_j,z) =\sum_{z\in S_n}\xi(x_i,x_j,z)+\xi'(x_i,y_j,b_1)= \]
\[ = \sum_{z \in S_n} \zeta(x_i,x_j,z) + \zeta(x_i,x_j,b) = \gamma_{ij} + \zeta(x_i,x_j,b). \]
Thus,
\[ \tag{II} \gamma'_{ij}=\gamma_{ij}+\zeta(x_i,x_j,b). \]
From (I) and (II) we obtain:
\[ C(S'/\{a\})-C(S'/\{b_1\})= \]
\[ = \sum_{\substack{i<j\\ x_i,x_j:\ \zeta(x_i,x_j,a)\zeta(x_i,x_j,b)<0}} \left[\gamma_{ij}\zeta(b,x_i,x_j)\zeta(a,b,x_i)\zeta(a,b,x_j)+\right. \]
\[ \left. +\zeta(x_i,x_j,b)\zeta(b,x_i,x_j)\zeta(a,b,x_i)\zeta(a,b,x_j)\right]= \]
\[ \tag{III} = \sum_{\substack{i<j\\ x_i,x_j:\ \zeta(x_i,x_j,a)\zeta(x_i,x_j,b)<0}} \left[\gamma_{ij}\zeta(b,x_i,x_j)\zeta(a,b,x_i)\zeta(a,b,x_j)+\right. \]
\[ \left. +\zeta(a,b,x_i)\zeta(a,b,x_j)\right]. \]
c) Compute the difference:
\[ C(S'')-C(S'\setminus\{a'\}). \]
Denote by \(C_0(S'')\) and \(C_0(S'\setminus\{a\})\) the number of convex quadruples in \(S''\) and \(S'\setminus\{a\}\) that do not contain \(b_1\) and \(b_2\); by \(C_{b_2}(S'')\) and \(C_{b_1}(S'\setminus\{a\})\), the number of convex quadruples with \(b_2\) and \(b_1\) and without the point \(b\); by \(C_{bb_2}(S'')\) and \(C_{bb_1}(S'\setminus\{a\})\), the number of convex quadruples with \(\{b,b_2\}\) and with \(\{b,b_1\}\).
From the definition of \(S'\) and \(S''\) it follows:
\[ \tag{IV} C_0(S'')=C_0(S'\setminus\{a\}), \]
\[ \tag{V} C_{b_2}(S'')=C_{b_1}(S'\setminus\{a\}). \]
Further,
\[ |L(a,b)|=\frac{n-2+\gamma_{ab}}{2}, \qquad |R(a,b)|=\frac{n-2-\gamma_{ab}}{2}. \]
Therefore, from the definition of \(S'\) and \(S''\) it follows:
\[ C_{bb_1}(S'\setminus\{a\})= C_n^4-\frac{n-2+\gamma_{ab}}{2}\cdot\frac{n-2-\gamma_{ab}}{2}= \]
\[ = C_n^4-\frac{(n-2)^2-\gamma_{ab}^{\,2}}{4}. \]
\[ C_{bb_2}(S'')= C_n^4-\left[\frac{n-2}{2}\right]\cdot \left[\frac{n-1}{2}\right]. \]
Consequently,
\[ C_{bb_2}(S'')-C_{bb_1}(S'\setminus\{a\}) = \frac{(n-2)^2-\gamma_{ab}^{\,2}}{4} -\left[\frac{n-2}{2}\right]\left[\frac{n-1}{2}\right], \]
or
\[ \tag{VI} C_{bb_2}(S'')-C_{bb_1}(S'\setminus\{a\}) = -\frac{\gamma_{ab}^{\,2}}{4} + \frac{1-(-1)^n}{8}. \]
Taking IV, (V), and (VI) into account, we obtain:
\[ \tag{VII} C(S'')-C(S'\setminus\{a\}) = -\frac{\gamma_{ab}^{\,2}}{4} + \frac{1-(-1)^n}{8}. \]
Adding (III) and (VII) term by term, we obtain:
\[ \begin{aligned} \text{(VIII)}\quad C(S'')-C(S'\setminus \{b_1\}) &= \sum_{\substack{i<j\\ x_i,x_j\mid \zeta(x_i,x_j,a)\zeta(x_i,x_j,b)<0}} \{\gamma_{ij}\zeta(b,x_i,x_j)\zeta(a,b,x_i)\zeta(a,b,x_j)\\ &\qquad\qquad\qquad +\zeta(a,b,x_i)\zeta(a,b,x_j)\} -\frac{\gamma_{ab}^{2}}{4}+\frac{1-(-1)^n}{8}. \end{aligned} \]
Taking into account that \(S'\setminus \{b_1\}=S_n\), where \(S_n\) is a least convex system of \(n\) points, we obtain the theorem:
Theorem 1. If \(S_n\) is least convex, then the inequality holds:
\[ \sum_{\substack{i<j\\ x_i,x_j\mid \zeta(x_i,x_j,a)\zeta(x_i,x_j,b)<0}} \{\gamma_{ij}\zeta(b,x_i,x_j)\zeta(a,b,x_i)\zeta(a,b,x_j) +\zeta(a,b,x_i)\zeta(a,b,x_j)\} \ge \]
\[ \ge \frac{\gamma_{ab}^{2}}{4}+\frac{(-1)^n-1}{8}. \]
for all \(a,b\in S_n\).
Starting from the last theorem, we obtain one more necessary criterion for a least convex system. Interchanging the points \(a\) and \(b\) in (VIII), and taking into account that the summation here is over those pairs \(x_i,x_j\) for which
\[ \zeta(x_i,x_j,a)\zeta(x_i,x_j,b)<0, \]
we obtain:
\[ \sum_{\substack{i<j\\ x_i,x_j\mid \zeta(x_i,x_j,a)\zeta(x_i,x_j,b)<0}} \{-\gamma_{ij}\zeta(b,x_i,x_j)\zeta(a,b,x_i)\zeta(a,b,x_j) +\zeta(a,b,x_i)\zeta(a,b,x_j)\} \ge \]
\[ \ge \frac{\gamma_{ab}^{2}}{4}+\frac{(-1)^n-1}{8}. \]
Adding term by term (VIII) and (IX), we obtain:
\[ \sum_{i<j}\zeta(a,b,x_i)\zeta(a,b,x_j) \ge \frac{\gamma_{ab}^{2}}{4}+\frac{(-1)^n-1}{8}. \]
\[ \text{(X)}\qquad x_i,x_j\mid \zeta(x_i,x_j,a)\zeta(x_i,x_j,b)<0 \]
Theorem 2. For the least convexity of a system it is necessary that the inequalities (X) be satisfied for all \(a,b\in S_n\).
We obtain one more modification of the last criterion. (X) can be rewritten as follows:
\[ \frac{1}{2}\sum_{i<j}\{1-\zeta(x_i,x_j,a)\zeta(x_i,x_j,b)\} \zeta(a,b,x_i)\zeta(a,b,x_j) \ge \]
\[ \ge \frac{\gamma_{ab}^{2}}{4}+\frac{(-1)^n-1}{8}. \]
Whence
\[ \sum_{i<j}\{\zeta(a,b,x_i)\zeta(a,b,x_j) -\zeta(a,b,x_i)\zeta(a,b,x_j)\zeta(x_i,x_j,a)\zeta(x_i,x_j,b)\} \ge \]
\[ \text{(XI)}\qquad \ge \frac{\gamma_{ab}^{2}}{2}+\frac{(-1)^n-1}{4}. \]
It is easy to see that
\[ \sum_{i<j} \zeta(a,b,x_i)\zeta(a,b,x_j) = C^2_{\frac{n-2+\gamma}{2}}+C^2_{\frac{n-2-\gamma}{2}} - \frac{n-2+\gamma}{2}\cdot\frac{n-2-\gamma}{2} = \frac{\gamma_{ab}^{2}}{2}-\frac{n-2}{2}, \]
where \(\gamma=\gamma_{ab}\).
Denote the number of convex and nonconvex quadruples involving the pair of points \((a,b)\) by \(C(a,b)\) and \(I(a,b)\).
Then:
\[ \text{(XII)}\quad -\sum_{i<j}\zeta(a,b,x_i)\zeta(a,b,x_j)\zeta(x_i,x_j,a)\zeta(x_i,x_j,b) = I(a,b)-C(a,b). \]
Taking (XII) and (XIII) into account, we rewrite inequality (XI) as follows:
\[ \frac{\gamma_{ab}^{2}}{2}-\frac{n-2}{2}+I(a,b)-C(a,b) \ge \frac{\gamma_{ab}^{2}}{2}+\frac{(-1)^n-1}{4}; \]
\[ -\frac{n-2}{2}+I(a,b)-C(a,b) \ge \frac{(-1)^n-1}{4} \]
or
\[ \text{(XIV)}\quad I(a,b)-C(a,b) \ge \frac{(-1)^n-1}{4}+\frac{n-2}{2}. \]
Theorem 3. For a minimally convex \(S_n\), inequality (XIV) holds for all \(a,b\in S_n\).
References
-
G. G. Pestov. On certain numerical characteristics of point systems. Izvestiya TPI, vol. 134, 1965.
-
G. G. Pestov. On the number of nonconvex and convex quadruples in a planar point system. The present collection.