Skip to main content
added 62 characters in body; Post Made Community Wiki
Source Link
Günter Rote
  • 1.1k
  • 8
  • 10

Here is a sketch of an answer that involves the squared Euclidean distances between the four points $A,B,C,D$ (and only the squared ones, not a mixture between squared and non-squared distances.)

Suppose $D$ is the origin, and consider the vectors $a=DA, b=DB, c=DC$. From $$AB^2 = \langle a-b,a-b \rangle = DA^2 -2\langle a,b\rangle + DB^2,$$ we get $\langle a,b\rangle$ as a linear expression in terms of the squared distances, and similarly for the other mixed inner products. The inner "self"-products like $\langle a,a\rangle=DA^2$ are directly available anyway. Assuming that $a$ and $b$ are linearly independent, we can write $$c=\lambda a + \mu b.\ \ \ \ \ (1)$$ Then $D$ (the origin) is in the convex hull of $A,B,C$ iff $\lambda\le 0$ and $\mu \le 0$. Multiplying (1) by $a$, $b$, and $c$ gives an overdetermined system of three equations $$\langle a,c\rangle = \lambda\langle a,a\rangle+\mu\langle a,b\rangle,$$ etc. from which an expression (actually, three equivalent expressions) for $\lambda$ and $\mu$ can be derived using Cramer's rule, as a quotient of determinants. Hence, the sign of these determinants tells us if $D$ is a vertex of the convex hull or not.

So in the end it boils down to $2\times 2$ determinants whose entries are linear in the squared distances, i.e., degree-2 polynomials in the squared distances. One would have to work out what these expressions are. Who knows, maybe a clever combination of the various redundant expression gives even linear expressions, or expressions that can be factorized into nice linear terms.

Here is a sketch of an answer that involves the squared Euclidean distances between the four points $A,B,C,D$ (and only the squared ones, not a mixture between squared and non-squared distances.)

Suppose $D$ is the origin, and consider the vectors $a=DA, b=DB, c=DC$. From $$AB^2 = \langle a-b,a-b \rangle = DA^2 -2\langle a,b\rangle + DB^2,$$ we get $\langle a,b\rangle$ as a linear expression in terms of the squared distances, and similarly for the other mixed inner products. The inner "self"-products like $\langle a,a\rangle=DA^2$ are directly available anyway. Assuming that $a$ and $b$ are linearly independent, we can write $$c=\lambda a + \mu b.\ \ \ \ \ (1)$$ Then $D$ (the origin) is in the convex hull of $A,B,C$ iff $\lambda\le 0$ and $\mu \le 0$. Multiplying (1) by $a$, $b$, and $c$ gives an overdetermined system of three equations $$\langle a,c\rangle = \lambda\langle a,a\rangle+\mu\langle a,b\rangle,$$ etc. from which an expression (actually, three equivalent expressions) for $\lambda$ and $\mu$ can be derived using Cramer's rule, as a quotient of determinants. Hence, the sign of these determinants tells us if $D$ is a vertex of the convex hull or not.

So in the end it boils down to $2\times 2$ determinants whose entries are linear in the squared distances, i.e., degree-2 polynomials in the squared distances. One would have to work out what these expressions are. Who knows, maybe a clever combination of the various redundant expression gives even linear expressions.

Here is a sketch of an answer that involves the squared Euclidean distances between the four points $A,B,C,D$ (and only the squared ones, not a mixture between squared and non-squared distances.)

Suppose $D$ is the origin, and consider the vectors $a=DA, b=DB, c=DC$. From $$AB^2 = \langle a-b,a-b \rangle = DA^2 -2\langle a,b\rangle + DB^2,$$ we get $\langle a,b\rangle$ as a linear expression in terms of the squared distances, and similarly for the other mixed inner products. The inner "self"-products like $\langle a,a\rangle=DA^2$ are directly available anyway. Assuming that $a$ and $b$ are linearly independent, we can write $$c=\lambda a + \mu b.\ \ \ \ \ (1)$$ Then $D$ (the origin) is in the convex hull of $A,B,C$ iff $\lambda\le 0$ and $\mu \le 0$. Multiplying (1) by $a$, $b$, and $c$ gives an overdetermined system of three equations $$\langle a,c\rangle = \lambda\langle a,a\rangle+\mu\langle a,b\rangle,$$ etc. from which an expression (actually, three equivalent expressions) for $\lambda$ and $\mu$ can be derived using Cramer's rule, as a quotient of determinants. Hence, the sign of these determinants tells us if $D$ is a vertex of the convex hull or not.

So in the end it boils down to $2\times 2$ determinants whose entries are linear in the squared distances, i.e., degree-2 polynomials in the squared distances. One would have to work out what these expressions are. Who knows, maybe a clever combination of the various redundant expression gives even linear expressions, or expressions that can be factorized into nice linear terms.

Source Link
Günter Rote
  • 1.1k
  • 8
  • 10

Here is a sketch of an answer that involves the squared Euclidean distances between the four points $A,B,C,D$ (and only the squared ones, not a mixture between squared and non-squared distances.)

Suppose $D$ is the origin, and consider the vectors $a=DA, b=DB, c=DC$. From $$AB^2 = \langle a-b,a-b \rangle = DA^2 -2\langle a,b\rangle + DB^2,$$ we get $\langle a,b\rangle$ as a linear expression in terms of the squared distances, and similarly for the other mixed inner products. The inner "self"-products like $\langle a,a\rangle=DA^2$ are directly available anyway. Assuming that $a$ and $b$ are linearly independent, we can write $$c=\lambda a + \mu b.\ \ \ \ \ (1)$$ Then $D$ (the origin) is in the convex hull of $A,B,C$ iff $\lambda\le 0$ and $\mu \le 0$. Multiplying (1) by $a$, $b$, and $c$ gives an overdetermined system of three equations $$\langle a,c\rangle = \lambda\langle a,a\rangle+\mu\langle a,b\rangle,$$ etc. from which an expression (actually, three equivalent expressions) for $\lambda$ and $\mu$ can be derived using Cramer's rule, as a quotient of determinants. Hence, the sign of these determinants tells us if $D$ is a vertex of the convex hull or not.

So in the end it boils down to $2\times 2$ determinants whose entries are linear in the squared distances, i.e., degree-2 polynomials in the squared distances. One would have to work out what these expressions are. Who knows, maybe a clever combination of the various redundant expression gives even linear expressions.