由n点定义的超平面

Question

我有以下问题：

给定一个空间中的n个点，我正在搜索穿过它们的超平面。

此类问题的最简单示例是两个点（x_1 = 0，x_2 = 0）和（1，-1），我想返回1 * x_1 + 1 * x_2 = 0。

我的观点将是32位整数的n元组。所需超平面a_1 x_1 + a_2 x_2 + ... = c的系数a_i也必须是32位整数。如果无法以这种方式定义超平面，我希望对此进行报告。

我的项目是用C ++编写的。

我可能可以自己编写代码，但是我希望这会花很多时间。另外，我的直觉是，这是一个足够普遍的问题，可能会有一个开源库可以解决我的问题。有人知道图书馆可以解决我的问题吗？

提前致谢！

Answer 1

实际上这并不难，因为给定的点是线性无关的。

设 Z^n 中的 u^i 为节点，然后将 v^i 定义为 (u^i_0, ..., u^i_{n-1},-1)。

现在创建一个矩阵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 )

你需要解决的是 A * x == 0。

现在继续执行高斯消除。确保仍然让系数为整数。因此，您不必执行 r_k -= r_ki * r_i / r_ii ，而是必须执行 r_k = r_ki * r_i - r_ii * r_k 。每一步之后，将处理后的行除以其最大公约数。这通常可以避免溢出。如果遇到溢出，只需为矩阵运算本身使用更大的类型即可。

最后，您将得到一个矩阵，其中最多有两列具有多个条目。您的解决方案将仅取决于这两行值的选择，例如它看起来像

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

为 x_0 和 x_1 分配任意值（在本例中），就完成了。x 的最后一个值将是超平面等式的右侧。