Search code examples
complexity-theorytheorylinear-algebra

Complexity class of computing a hyperplane

I am concerned with the following algorithm:

As input, it takes n points in n dimensional space in rectangular coordinates. These n points define an n-1 dimensional hyperplane (we can ignore the infintesimal probability that they don't). As output, I would like the equation of this hyperplane.

Is there a known algorithm - or at least a known complexity class - for this problem?

Thanks in advance.

Solution

  • The equation you're looking for is

    A_1 x_1 + A_2 x_2 + ... + A_n x_n + C = 0

    for some coefficients A_1 and C and for the x_i being the rectangular coordinates of a point on the plane. Substitute in the input points and you've got a set of n simultaneous equations which you can solve (up to a scale factor).