Construct a plane disjoint from a given point set

Question

Suppose we have some points $p_1,\ldots,p_n \in \mathbb R^D$ none of which are the origin. It is intuitively clear there exists a $D-1$ dimensional hyperplane through the origin that does not intersect any of the points.

One nice proof is to define $F_i$ as the collection of vectors $v$ with $v^T p_i \ne 0$. Then show $F_i$ is open and dense hence their shared intersection is nonempty.

However this does not give a formula to write down such a plane. In this case I'm trying to find one such plane so I can use it as a starting point for an iterative algorithm to find the best such plane.

I have a way to do it using row-reduction but this gets quite messy to enact or prove if $p_1,\ldots, p_n$ are linearly dependent.

Could someone suggest a slick way to find one such plane? Bonus points if it is computationally cheap in case $D$ is much larger than $n$.

All I get searching is the Ham Sandwich theorem which is looking to divide the point set in half. I'm just looking to divide the point set in two. So this problem should be simpler.

Answer 1

I don't know what you mean by best, but here is a naive algorithm for a linear hyperplane not through any $p_i$:

• For $D=1$ there is nothing to do.

• Otherwise, choose a direction $v$ not parallel to any $p_i$ and project to $v^\perp\cong\mathbb{R}^{D-1}$.

• Repeat.

Answer 2

Here's a sketch of one idea. Let $o$ be the origin. Find the hyperplane $H$ through $o$ and $\{p_1, p_2, \ldots, p_{D-1} \}$. Now the plan is to rotate it slightly about $o$ so that it detaches from those points but not enough to hit another point.

For each $p_i$, $i \ge D$, compute the rotation angle necessary to rotate $H$ about $o$ to directly hit $p_i$. In other words, if $N$ is the normal vector to $H$, the rotation moves $N$ toward $p_i$. Let the min angle be $\theta$, achieved with $p_j$. Rotating $H$ (and $N$) by $\theta/2$ toward $p_j$ will usually work, unless that direction of rotation keeps some points along the axis of rotation (so they remain on $H$). So one needs to choose a direction to rotate $H$ whose axis does not contain any of the $p_i$.

There are $O(n)$ such axes, and so it shouldn't be difficult to choose a direction of rotation that avoids those axes.