Hyperplane defined by n points

Question

I've the following problem:

Given n points in a space, I'm searching a hyperplane that goes through them.

The easiest example of such a problem is two points (x_1=0,x_2=0) and (1,-1) and I would like to get 1*x_1+1*x_2=0 returned.

My points will be n-tuples of 32-bit integers. The coefficients a_i of the desired hyperplane a_1 x_1 + a_2 x_2 + ... = c must be 32-bit integers as well. In case the hyperplane cannot be defined this way, I would like to have this reported.

My project is coded in c++.

I would probably able to code this up by myself but I anticipate that this would be quite a bit of work. Also, my hunch is that this is a problem general enough that there might be an open-source library which would solve my problem. Does anybody know about a library which could solve my problem?

Thanks in advance!

Answer 1

Actually this is not very hard, given that the given points are linear independent.

Let u^i in Z^n be your nodes, then define v^i as (u^i_0, ..., u^i_{n-1},-1).

Now create a matrix A

( v^0_0     v^0_1 ...     v^0_n     )
( v^1_0     v^1_1 ...     v^1_n     )
    .         .             .
    .         .             .
    .         .             .
( v^{n-2}_0 v^{n-2}_1 ... v^{n-2}_n )

What you have to solve is A * x == 0.

Now go ahead and perform the Gaussian elimination. Make sure that you still let the coefficients to be integers. So instead of doing r_k -= r_ki * r_i / r_ii, you'll have to do r_k = r_ki * r_i - r_ii * r_k. After each step, divide the processed row by its greatest common divisor. This usually avoids overflow. If you experience overflows, just use a larger type for the matrix operations itself.

In the end, you'll have a matrix in which there are at most two columns that have more than one entry. Your solution will depend on the choice of values of these two rows only, e.g. it will look something like

1 1 1 0 0 0
2 0 0 1 0 0
0 1 0 0 1 0
1 1 0 0 0 1

assign any values to x_0 and x_1 (in this example) and you're done. The last value of x will be your right hand side of the hyperplane equality.