On triangles being nondegenerate

On triangles being nondegenerate

The (signed) area A of a triangle with vertices $(x_0, y_0), (x_1, y_1), (x_2, y_2)$ satisfies

(0)

$$ \left| \begin{array}{l l l} x _ {0} & y _ {0} & 1 \ x _ {1} & y _ {1} & 1 \ x _ {2} & y _ {2} & 1 \end{array} \right| = 2 A $$

This is a very nice formula. The value of a determinant is not changed when we increase a row (or column) by a multiple of another row (or column respectively). Adding a multiple of the last column to the first (or middle) column corresponds to moving the triangle horizontally (or vertically): translating a triangle through the plane leaves its (signed) area unchanged.

The lengths of its edges are given by

(1) $\sqrt{{\left( {x}{0} - {x}{1}\right) }^{2} + {\left( {y}{0} - {y}{1}\right) }^{2}}$ and cyclically.

(I think this formula much less nice.)

We have now two ways of expressing in terms of the coordinates of the vertices that the triangle is not degenerate:

(i) using (o),we can express that its area differs from 0; (ii) using (1), we can express that all three

triangular inequalities are strict.

The challenge is to design a calculational demonstration that the two boolean expressions created under (i) and (ii) are equivalent.

Because (1) is expressed in terms of coordinate differences, we subtract in (0) one row from the other two, e.g.

$$ \begin{array}{l} 2 A \ = {\mathrm {s u b t r a c t l a s t r o w} } \ \left| \begin{array}{l l l} x _ {0} - x _ {2} & y _ {0} - y _ {2} & 0 \ x _ {1} - x _ {2} & y _ {1} - y _ {2} & 0 \ x _ {2} & y _ {2} & 1 \end{array} \right| \ = {\mathrm {d e v e l o p i n g a l o n g l a s t c o l u m n} } \ \left| \begin{array}{l l} x _ {0} - x _ {2} & y _ {0} - y _ {2} \ x _ {1} - x _ {2} & y _ {1} - y _ {2} \end{array} \right| \ = \begin{array}{l} \left{i n t e r c h a n g i n g r o w s a n d m u l t i p l y i n g o n e r a w \right. \ b y - 1 \end{array} \ \left| \begin{array}{l l} x _ {1} - x _ {2} & y _ {1} - y _ {2} \ x _ {2} - x _ {0} & y _ {2} - y _ {0} \end{array} \right| \ \end{array} $$

Denoting the edges by the vectors $a, b, c$ (with components $a_x, a_y$ , etc.) such that

$$ (2) \quad a + b + c = 0 $$

we have derived

$$ (3) \quad \left| \begin{array}{l l} a _ {x} & a _ {y} \ b _ {x} & b _ {y} \end{array} \right| = 2 A \quad \mathrm {a n d c y c l i c a l l y .} $$

There are two reasons to square both sides of (3). Firstly, $A$ is the signed area, but as far as the area being zero or not is concerned, its sign is irrelevant. Secondly, if we compute the square wisely, we can express it in terms of scalar products. Using that the determinant of a product is the product of the determinants of the factors and that reflection with respect to the main diagonal leaves the determinant unchanged, we derive from (3)

$$ \begin{array}{l} 4 A ^ {2} \ = \left| \begin{array}{l l} a _ {x} & a _ {y} \ b _ {x} & b _ {y} \end{array} \right| x \left| \begin{array}{l l} a _ {x} & b _ {x} \ a _ {y} & b _ {y} \end{array} \right| \ = \left| \begin{array}{l l} a \cdot a & a \cdot b \ b \cdot a & b \cdot b \end{array} \right| \ = (a \cdot a) (b \cdot b) - (a \cdot b) ^ {2} \ \end{array} $$

Hence

$$ (4) \quad A \neq 0 \equiv (a \cdot a) (b \cdot b) > (a \cdot b) ^ {2} a n d c y c l i c a l l y. $$

Having cleaned up the expression under (i), we now turn our attention to the strict triangular inequalities; using (i), we express the lengths of the

edges as

(5) $\sqrt{(a \cdot a)}$ and cyclically

Starting with one of the strict inequalities we observe

$$ \sqrt {(a \cdot a)} + \sqrt {(b \cdot b)} > \sqrt {(c \cdot c)} $$

$\equiv$ {since both sides are nonnegative}

$$ (a \cdot a) + 2 \sqrt {(a \cdot a) (b \cdot b)} + (b \cdot b) > (c \cdot c) $$

$= \left{ {\text{ from }\left( 2\right) : \left( {c - c}\right) = \left( {a \cdot a}\right) + 2\left( {a \cdot b}\right) + \left( {b \cdot b}\right) }\right}$

$$ \sqrt {(a \cdot a) (b \cdot b)} > (a \cdot b) $$

${ \text{since the left side is nonnegative} }$

$$ (a \cdot a) (b \cdot b) > (a \cdot b) ^ {2} \quad \vee (a \cdot b) < 0 $$

（4）

$$ A \neq 0 \quad V (a \cdot b) < 0 $$

and cyclically. The conjunction of the three strict triangular inequalities - v distributes over $\wedge$ - is

(6) $A \neq 0 \vee (a \cdot b < 0 \wedge b \cdot c < 0 \wedge c \cdot a < 0)$ and we have to show that (6) equivales $A \neq 0$ , i.e. our final proof obligation is (7) $a \cdot b < 0 \land b \cdot c < 0 \land c \cdot a < 0 \Rightarrow A \neq 0.$

To this end we observe, starting with the antecedent of (7)

$$ a \cdot b < 0 \wedge b \cdot c < 0 \wedge c \cdot a < 0 $$

{elimination of c by (2)}

$$ a \cdot b < 0 \wedge b \cdot (a + b) > 0 \wedge (a + b) \cdot a > 0 $$

$$ \begin{array}{l} = {\text {a r i t h m e t i c} } \ - a \cdot b > 0 \wedge b \cdot b > - a \cdot b \wedge a \cdot a > - a \cdot b \ \Rightarrow {\mathrm {f o r n o n n e g a t i v e f a c t o r s , m u l t i p l i c a t i o n i s} \ (b \cdot b) (a \cdot a) > (- a \cdot b) ^ {2} \ = {(4) } \ A \neq 0 \ \end{array} $$

Thus our final proof obligation is met.

The above calculation is not laborious, but it is worth noting that the brevity (in particular of the first part) has been obtained by using a number of theorems about determinants. We also used to good advantage the properties of the scalar product. In short: we did not get our brevity for free. The rest of the argument is subtle in that it depends more than once on the limited monotonicity of ordinary multiplication, and, finally, on a destruction of the symmetry so as to exploit $a + b + c = 0$ . I consider the formal exercise nontrivial and am pleased with the result.

Austin, 13 June 1988

prof. dr. Edsger W. Dgikstra

Department of Computer Sciences

The University of Texas at Austin

Austin, TX 78712- 1188 , USA