Circumcenter of 3D triangle without causing integer overflow

Question

Programming side: Trying to implement a calculation for 3D triangle calculation.

Mathematical side: I need a formula for this that does not use cross product. I have found a formula that uses the vectors of the sides and cross products, but the issue is that My triangles are so large, that i get 64bit integer overflow. Cross product gives a vector so long that its square magnitude is larger than 64 bit integer.

For tetrahedron i solved the issue by switching to the Matrix determinant formula, there the values don't get big enough. But for triangle in 3D i didn't find any matrix solution. Is there a way to calculate circumcenter of a 3D triangle with out using cross product?

The solution should use only integers. or rational numbers.

Answer 1

A cross product free solution:

The following figure depicts the three vertices $A,B,C$ and the corresponding three vectors $a,b$,and $c$:

The task is to determine the perpendicular segment bisectors in the plane of $ABC$. In what follows I will compute the parametric equation of the brown line, the perpendicular bisector of $AC$ in the $ABC$ plane. The same procedure will provide the equation of the perpendicular bisectors to $AC$ or to $CB$.

First, determine the parametric equation of the line through $AB$. The direction vector can be $d=b-a$. So the equation is $$\operatorname{blue}(u)= (b-a)u+a.$$ Take an arbitrary point on the $AB$ line. Taking a specific $u$ the arbitrary point is given.

Second, determine the vector (red) pointing to the middle point of $AC$: $$\operatorname{red}=\frac12(c+a).$$ Third, calculate the brown vector pointing from the midpoint of $AB$ to the blue point on $AB$ belonging to the parameter $u$ chosen:

$$\operatorname{brown}(u)=\operatorname{blue}(u)-\operatorname{red}.$$

Finally, choose $u$ so that the brown vector be perpendicular to $c-a$. For this we have to solve the following equation:

$$\operatorname{brown}(u)\circ(c-a)=0$$ where $\circ$ is the sign of the scalar product. If $u_0$ solves the equation above then the equation of the perpendicular bisector is $$\operatorname{brown(u_0)}t+\operatorname{red}.$$

Repeating this for another segment bisector we'll get another equation of a line in the same plane. The crossing point of these lines will be the circumcenter.

Answer 2

The circumcenter of a tetrahedron is the intersection of three planes. Each plane is defined by two vertices, potentially giving $O(n^4)$ different planes ($n$ is the range of the coordinates).

For a triangle, the supporting plane enters into play. As it is defined by three vertices, the number of distinct possibilities is $O(n^6)$.

This explains why more accuracy is required: there are more possible locations of the center. These are rational numbers, and the denominators need to be larger.

Unfortunately, this is unescapable and you will have to resort to extended arithmetic (or equivalent tricks), or sacrifice accuracy.