On the Number of Nonconvex and Convex Quadruples in a Planar Point System
Abstract Generated abstract
This paper studies the enumeration of convex and nonconvex quadruples in a finite planar point system using orientation signs of triples of points. It proves a sign criterion distinguishing convex from nonconvex four point subsets, then derives an identity for the change in the number of convex quadruples when one point is replaced by another. The main theorem expresses this difference as a sum over separating pairs of points, weighted by the imbalance of points on the two sides of the corresponding line, and the paper records consequences for sequences of point replacements, including a cancellation identity for closed sequences.
Full Text
On the Number of Nonconvex and Convex Quadruples in a Planar Point System
G. G. Pestov
(Presented by the Department of Engineering and Computational Mathematics)
Lemma 1. Given \(S_4=\{a,b,c,d\}\). The quantity
\[ \xi(a,b,c)\xi(a,b,d)\xi(c,d,a)\xi(c,d,b) \]
is equal to \(+1\) or \(-1\), depending on whether \(C(S_4)=1\) or \(0\).
Proof. Note that the function
\[ \varphi(a,b,c,d)=\xi(a,b,c)\xi(a,b,d)\xi(c,d,a)\xi(c,d,b) \]
does not change under a permutation of the arguments.
Indeed:
\[ \varphi(b,a,c,d)=\xi(b,a,c)\xi(b,a,d)\xi(c,d,b)\xi(c,d,a)= \]
\[ =\xi(a,b,c)\xi(a,b,d)\xi(c,d,a)\xi(c,d,b)=\varphi(a,b,c,d). \]
Likewise,
\[ \varphi(a,c,b,d)=\varphi(a,b,d,c)=\varphi(a,b,c,d). \]
a) Let \(S_4\) be convex. In view of the preceding, we may assume that the points \(a,b,c,d\) are arranged in their natural order [1]. Then
\[ \xi(a,b,c)=\xi(a,b,d)=\xi(c,d,a)=\xi(c,d,b)=+1. \]
Consequently,
\[ \varphi(a,b,c,d)=+1. \]
b) Let \(S_4\) be nonconvex. Let \(a,b,c\) be the exterior points, arranged in their natural order, and let \(d\) be the interior point. Then
\[ \xi(a,b,c)=\xi(a,b,d)=+1, \]
\[ \xi(c,d,a)\xi(c,d,b)=-1. \]
Consequently,
\[ \varphi(a,b,c,d)=-1. \]
Lemma 2. Let \(S_5=\{a,b,x_1,x_2,x_3\}\). Then
\[ C(S_5\setminus\{a\})-C(S_5\setminus\{b\})= \frac{1}{2} \sum_{\substack{x,y,z\in S_5\\ x,y \mid \xi(x,y,a)\xi(x,y,b)<0}} \xi(x,y,z)\xi(x,y,b)\xi(a,b,x)\xi(a,b,y). \]
Proof. By Lemma 1.4 from [2]:
\[ \xi(b,x_1,x_2)\xi(b,x_2,x_3)\xi(b,x_3,x_1) +\xi(b,x_1,x_2)\xi(a,b,x_1)\xi(a,b,x_2)+ \]
\[ \begin{aligned} &+\,\zeta(b,x_2,x_3)\zeta(a,b,x_2)\zeta(a,b,x_3) +\zeta(b,x_3,x_1)\zeta(a,b,x_3)\zeta(a,b,x_1)=\\ &=\zeta(a,x_1,x_2)\zeta(a,x_2,x_3)\zeta(a,x_3,x_1) +\zeta(a,x_1,x_2)\zeta(a,b,x_1)\zeta(a,b,x_2)+\\ &\quad+\zeta(a,x_2,x_3)\zeta(a,b,x_2)\zeta(a,b,x_3) +\zeta(a,x_3,x_1)\zeta(a,b,x_3)\zeta(a,b,x_1). \end{aligned} \]
We regroup the terms:
\[ \begin{aligned} &-\zeta(b,x_1,x_2)\zeta(b,x_2,x_3)\zeta(b,x_3,x_1) +\zeta(a,x_1,x_2)\zeta(a,x_2,x_3)\zeta(a,x_3,x_1)=\\ &=\zeta(b,x_1,x_2)\zeta(a,b,x_1)\zeta(a,b,x_2) -\zeta(a,x_1,x_2)\zeta(a,b,x_1)\zeta(a,b,x_2)+\\ &\quad+\zeta(b,x_2,x_3)\zeta(a,b,x_2)\zeta(a,b,x_3) -\zeta(a,x_2,x_3)\zeta(a,b,x_2)\zeta(a,b,x_3)+\\ &\quad+\zeta(b,x_3,x_1)\zeta(a,b,x_3)\zeta(a,b,x_1) -\zeta(a,x_3,x_1)\zeta(a,b,x_3)\zeta(a,b,x_1). \end{aligned} \]
Multiplying all terms by \(\zeta(x_1,x_2,x_3)\) and making simple transformations:
\[ \begin{aligned} &\zeta(b,x_1,x_2)\zeta(b,x_1,x_3)\zeta(x_2,x_3,b)\zeta(x_2,x_3,x_1)-\\ &\quad-\zeta(a,x_1,x_2)\zeta(a,x_1,x_3)\zeta(x_2,x_3,a)\zeta(x_2,x_3,x_1)=\\ &=[1-\zeta(x_1,x_2,a)\zeta(x_1,x_2,b)]\zeta(x_1,x_2,x_3)\zeta(x_1,x_2,b)\zeta(a,b,x_1)\zeta(a,b,x_2)+\\ &\quad+[1-\zeta(x_2,x_3,a)\zeta(x_2,x_3,b)]\zeta(x_2,x_3,x_1)\zeta(x_2,x_3,b)\zeta(a,b,x_2)\zeta(a,b,x_3)+\\ &\quad+[1-\zeta(x_3,x_1,a)\zeta(x_3,x_1,b)]\zeta(x_3,x_1,x_2)\zeta(x_3,x_1,b)\zeta(a,b,x_3)\zeta(a,b,x_1)=\\ &=\frac12\Big\{ [1-\zeta(x_1,x_2,a)\zeta(x_1,x_2,b)]\zeta(x_1,x_2,x_3)\zeta(x_1,x_2,b)\zeta(a,b,x_1)\zeta(a,b,x_2)+\\ &\quad+[1-\zeta(x_2,x_1,a)\zeta(x_2,x_1,b)]\zeta(x_2,x_1,x_3)\zeta(x_2,x_1,b)\zeta(a,b,x_2)\zeta(a,b,x_1)+\\ &\quad+[1-\zeta(x_2,x_3,a)\zeta(x_2,x_3,b)]\zeta(x_2,x_3,x_1)\zeta(x_2,x_3,b)\zeta(a,b,x_2)\zeta(a,b,x_3)+\\ &\quad+[1-\zeta(x_3,x_2,a)\zeta(x_3,x_2,b)]\zeta(x_3,x_2,x_1)\zeta(x_3,x_2,b)\zeta(a,b,x_3)\zeta(a,b,x_2)+\\ &\quad+[1-\zeta(x_3,x_1,a)\zeta(x_3,x_1,b)]\zeta(x_3,x_1,x_2)\zeta(x_3,x_1,b)\zeta(a,b,x_3)\zeta(a,b,x_1)+\\ &\quad+[1-\zeta(x_1,x_3,a)\zeta(x_1,x_3,b)]\zeta(x_1,x_3,x_2)\zeta(x_1,x_3,b)\zeta(a,b,x_1)\zeta(a,b,x_3)\Big\}=\\ &=\frac12\sum_{x,y,z\in S_5\setminus\{a,b\}} [1-\zeta(x,y,a)\zeta(x,y,b)]\zeta(x,y,z)\zeta(x,y,b)\zeta(a,b,x)\zeta(a,b,y)=\\ &=\sum_{\substack{x,y,z\in S_5\setminus\{a,b\}\\ x,y\mid \zeta(x,y,a)\zeta(x,y,b)<0}} \zeta(x,y,z)\zeta(x,y,b)\zeta(a,b,x)\zeta(a,b,y). \end{aligned} \]
But the expression on the left-hand side of the preceding equality, by Lemma 1, is
\[ 2\,[C(S_5\setminus\{a\})-C(S_5\setminus\{b\})]. \]
Therefore
\[ C(S_5\setminus\{a\})-C(S_5\setminus\{b\}) =\frac12\sum_{\substack{x,y,z\in S_5\\ x,y,z\in S_5}} \zeta(x,y,z)\zeta(x,y,b)\zeta(a,b,x)\zeta(a,b,y), \]
\[ x,y\mid \zeta(x,y,a)\zeta(x,y,b)<0, \]
which was required to be proved.
Theorem 3. Let \(a,b\in S\). Then
\[ C(S\setminus\{a\})-C(S\setminus\{b\}) =\sum_{i<j}\gamma_{ij}\zeta(b,x_i,x_j)\zeta(a,b,x_i)\zeta(a,b,x_j). \]
\[ x_i,x_j\mid \zeta(x_i,x_j,a)\zeta(x_i,x_j,b)<0. \]
Proof:
\[ C(S\setminus\{a\})-C(S\setminus\{b\}) =\sum_{\substack{S_5\subset S\\ a,b\in S_5}} C(S_5\setminus\{a\})-C(S_5\setminus\{b\})= \]
\[ =\frac12 \sum_{\substack{x,y\mid \zeta(x,y,a)\zeta(x,y,b)<0}} \zeta(x,y,z)\zeta(x,y,b)\zeta(a,b,x)\zeta(a,b,y)= \]
\[ =\frac12 \sum_{\substack{x,y\mid \zeta(x,y,a)\zeta(x,y,b)<0}} \zeta(x,y,b)\zeta(a,b,x)\zeta(a,b,y) \sum_{z\ne x,y}\zeta(x,y,z)= \]
\[ =\frac12 \sum_{\substack{x,y\mid \zeta(x,y,a)\zeta(x,y,b)<0}} \gamma_{xy}\zeta(x,y,b)\zeta(a,b,x)\zeta(a,b,y)= \]
\[ =\sum_{i<j}\gamma_{ij}\zeta(x_i,x_j,b)\zeta(a,b,x_i)\zeta(a,b,x_j), \]
\[ x_i,x_j\mid \zeta(x_i,x_j,a)\zeta(x_i,x_j,b)<0, \]
where \(\gamma_{ij}=|L(x_i,x_j)|-|R(x_i,x_j)|\),
as was required to prove.
Some consequences
Let
\[ S_{n+r}\setminus S_n=\{a_1,a_2,\ldots,a_r\}. \]
Then, by Theorem 3:
\[ C(S_n\cup\{a_{i+1}\})-C(S_n\cup\{a_i\})= \]
\[ =\sum_{k<l}\gamma_{kl}\zeta(x_k,x_l,a_{i+1}) \zeta(a_{i+1},a_i,x_k)\zeta(a_{i+1},a_i,x_l). \]
\[ x_k,x_l\mid \zeta(x_k,x_l,a_i)\zeta(x_k,x_l,a_{i+1})<0. \]
Summing over \(i\), we have:
\[ C(S_n\cup\{a_r\})-C(S_n\cup\{a_1\})= \]
\[ =\sum_{i=1}^{r-1} \sum_{\substack{x_k,x_l\mid \zeta(x_k,x_l,a_i)\zeta(x_k,x_l,a_{i+1})<0}} \gamma_{kl}\zeta(x_k,x_l,a_{i+1}) \zeta(a_{i+1},a_i,x_k)\zeta(a_{i+1},a_i,x_l). \]
In particular, if \(a_r=a_1\), we obtain:
\[ \sum_{i=1}^{r-1} \sum_{\substack{x_k,x_l\mid \zeta(x_k,x_l,a_i)\zeta(x_k,x_l,a_{i+1})<0}} \gamma_{kl}\zeta(x_k,x_l,a_{i+1}) \zeta(a_{i+1},a_i,x_k)\zeta(a_{i+1},a_i,x_l)=0. \]
REFERENCES
- G. G. Pestov. Theorems on exterior points and faces of an \(n\)-dimensional point system, Geometric Collection, TSU, 1966.
- G. G. Pestov. \(n\)-dimensional point systems, ibid.