3
$\begingroup$

Given three points in some Euclidean space, $\mathbf{r}, \mathbf{g}, \mathbf{b} \in \mathbb{R}^d$, I know via the triangle inequality that:

$$\|\mathbf{r} - \mathbf{b}\| \leq \|\mathbf{r} - \mathbf{g}\| +\|\mathbf{g} - \mathbf{b}\|.$$

In the figure below, suppose we only know how to measure distance between the red and green points and between the green and blue points. Using the triangle inequality, we can put an upper bound on distance the between the red and blue points:

triangle inequality in the plane

So far, just elementary geometry. However, now I'd like to do some computation with my points using "rational coordinates:" $\mathbf{r}, \mathbf{g}, \mathbf{b} \in \mathbb{Q}^d$, for example using gmp or cgal exact arithmetic types. It is easy to verify that the squared distance is also a rational: $\|\mathbf{r} - \mathbf{b}\|^2 = (\mathbf{r}-\mathbf{b})\cdot(\mathbf{r}-\mathbf{b}) \in \mathbb{Q}$. But the distance, $\|\mathbf{r}-\mathbf{b}\| = \sqrt{(\mathbf{r}-\mathbf{b})\cdot(\mathbf{r}-\mathbf{b})}$ may be irrational.

Clearly, the triangle inequality does not hold for squared Euclidean distances. The best upper bound I can come up with is rather loose:

$$\|\mathbf{r} - \mathbf{b}\|^2 \leq \left(\|\mathbf{r} - \mathbf{g}\| +\|\mathbf{g} - \mathbf{b}\|\right)^2,\\ \|\mathbf{r} - \mathbf{b}\|^2 \leq \|\mathbf{r} - \mathbf{g}\|^2 +\|\mathbf{g} - \mathbf{b}\|^2 + 2 \|\mathbf{r} - \mathbf{g}\| \|\mathbf{g} - \mathbf{b}\|,\\ \|\mathbf{r} - \mathbf{b}\|^2 \leq \|\mathbf{r} - \mathbf{g}\|^2 +\|\mathbf{g} - \mathbf{b}\|^2 + 2\max\left( \|\mathbf{r} - \mathbf{g}\|, \|\mathbf{g} - \mathbf{b}\|\right),\\\|\mathbf{r} - \mathbf{b}\|^2 \leq \min\left( \|\mathbf{r} - \mathbf{g}\|, \|\mathbf{g} - \mathbf{b}\|\right) + 3\max\left( \|\mathbf{r} - \mathbf{g}\|, \|\mathbf{g} - \mathbf{b}\|\right).\\ $$

Concretely, is there a tighter upper bound on the squared distance between two points using squared distances to an third, intermediary point?

More generally, is there a standard way/trick to work with the triangle inequality using just squared distances? Or using some other feature of rational coordinates?

$\endgroup$

migrated from mathoverflow.net Dec 13 '16 at 18:19

This question came from our site for professional mathematicians.

1
$\begingroup$

The bound for the triangle inequality is, and always is, the sum of the two euclidean distances. However, the question is how to represent this sum, and how to do calculations with it.

Let's say you have $A = |r - g|^2$ and $B = |g - b|^2$, which are rational numbers. Then the bound you want is simply $x = \sqrt{A} + \sqrt{B}$.

In general, the number $x$ generates a quadric extension of $\mathbb{Q}$, hence one has to work in this big number field.

The usual trick is then to write down a minimal polynomial for $x$, which is: $$F(X)=(X - \sqrt{A} - \sqrt{B})(X - \sqrt{A} + \sqrt{B})(X + \sqrt{A} - \sqrt{B})(X + \sqrt{A} + \sqrt{B})\\ = X^4 - 2(A + B) X^2 + (A - B)^2$$

Since the polynomial has four real roots, the inequality $X > x$ is not equivalent to $F(X) > 0$. But if $X$ is bigger than $\max(\sqrt{A}, \sqrt{B})$, then it is clear that $X > x$ if and only if $F(X) > 0$.

I summarize all these in the following algorithm.


Input: positive rational numbers $A$, $B$ and $X$.

Output: true or false, indicating whether $X$ is bigger than $\sqrt{A} + \sqrt{B}$.

  1. if $X^2 \leq A$ or $X^2 \leq B$, return false;

  2. if $X^4 - 2(A + B) X^2 + (A - B)^2 > 0$, return true; otherwise return false.


Note that the input $X$ need not be rational, it can be any real number (e.g. float types). But in view of your application, you would probably only use the case where $X$ is rational.

$\endgroup$
0
$\begingroup$

The set of triangles, when parametrized by squares of distances, is a convex cone, because the gram matrix of the inner products is positive definite (see my antique preprint ), so in this case, the triangle inequality reduces to determinant inequalities (in higher dimensions, triangle inequalities are only a part of the story, but the positive definiteness of the gram matrix is still necessary and sufficient).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.