Triangle Inequality

Inequality about Triangles

Let a, b, and c be positive numbers. The necessary and sufficient condition for a triangle with sides a, b, and c to exist is that the following inequalities hold:

$$ a < b + c $$

$$ b < c + a $$

$$ c < a + b $$

Let us reformat this inequality a bit.

Reorganizing the Conditions for a Single Variable

Let us organize the above inequality with respect to $b$.

In the second equation, moving $c$ from the right side to the left side gives:

$$ a - c < b $$

In the third equation, moving $a$ from the right side to the left side gives:

$$ c - a < b $$

Since $a - c = -(c - a)$, the fact that both of these equations hold means that we can write:

$$ |c - a| < b $$

Combined with the second equation, we can write:

$$ |c - a| < b < c + a $$

a, b, c are Positive

Since the absolute value is non-negative, we have:

$$ 0 \le |c - a| < b $$

Therefore, $b$ is positive. Similarly, $a$ and $c$ are also positive.

In other words, for the triangle inequality to hold, it is necessary that $a$, $b$, and $c$ are positive. At the beginning, we gave the condition that $a$, $b$, $c$ are positive numbers, but since the validity of the triangle inequality includes this condition, this assumption is actually not necessary.

When we assume a size relationship between a, b, c

Now suppose the size relationship $0 < a \le b \le c$. Then we have:

$$ 0 < a $$

and

$$ b \le c $$

Adding both sides gives us:

$$ b < a + c $$

This is the latter part of the triangle inequality organized with respect to $b$.

In other words, if we assume the size relationship $0 < a \le b \le c$, the latter part is already satisfied at the moment we assume the size relationship.

On the other hand, considering the first part, since:

$$ a \le c $$

we have:

$$ c - a \ge 0 $$

Therefore:

$$ |c - a| = c - a $$

Consequently, under this assumption of size relationship, the triangle inequality is equivalent to:

$$ c - a < b $$

When b is Fixed

Again, suppose the size relationship $0 < a \le b \le c$, and let $b$ be fixed while $a$ and $c$ vary. According to what we found above:

The closer both $a$ and $c$ are to $b$, the easier it is for the triangle inequality to hold. Conversely, the farther $a$ and $c$ are from $b$, the harder it is for the triangle inequality to hold.

When we represent this relationship in an a-c graph, it looks like the following:

The red shaded area in the figure represents the region where the triangle inequality holds (points on the line $c = a + b$ are not included).

This figure is somewhat interesting: each point in this region corresponds to the “shape” of one triangle. For example, the lower right vertex $(a, c) = (b, b)$ corresponds to the shape of an equilateral triangle.

Example Problem (Codility)

There is a coding test platform called Codility, which has a practice problem called Triangle.

The problem is as follows:

Given an array A consisting of N integers, write a function that determines whether there exists a pair in A that satisfies the triangle inequality.

From the analysis we have done so far, the following example solution can be considered:

#include <algorithm>

int solution(vector<int> &A) {
    // Sort array A
    std::sort(A.begin(), A.end());

    // Size of array A
    int size = A.size();

    // Advance the index until we reach positive values
    int i = 0;
    while (i < size && A[i] <= 0) {
        ++i;
    }

    // Check the triples in order and see if the triangle inequality holds
    for (; i < size - 2; ++i) {
        if (A[i + 2] - A[i] < A[i + 1]) {
            return 1;
        }
    }

    // If we reach the end of the loop, it means the inequality did not hold
    return 0;
}

The key insight is: “Look at values that are as close as possible to each other and check whether the triangle inequality holds.”