Space partitioning: optimal plane between two points. Plane must pass through origin.

Question

I am working on an LSH tree, where I need to select 2 random points (A and B), then draw a plane between them.

The plane must pass through origin, and through midpoint M = (A-B)*0.5

Issue:

I need to pick a normal, so that the distance from $A$ towards the plane and the distance from $B$ towards the plane are maximized.

My approach is to get such an 'optimal' normal as follows:

1. Normalize A, Normalize M
2. Compute angle $\theta$ between them (requires dot product)
3. Find the scalar magnitude: $h = \frac{1}{arcsin(\theta)}$
4. Find point $H = h \cdot A_{normalized}$
5. Get the "optimal" normal as: $\vec{N} = H-M$

The cool thing about this is that normal is already unit-length, so step 5 is very cheap.

However, to compute $\theta$ I am doing 2 normalizations (during step 1), which harms the performance a lot.

Is there an easier way to obtain such an "optimal" normal? Or would I still require something as expensive as cross-product?

---

Here the plane cuts through the screen, and we see its crossection. This means distances from A and B to plane are maximized and the normal is "optimal". Any other normal would cause the plane to be "shallow" towards A and B.

Answer 1

If $A, B$, and the origin are not collinear, then we can write the normal vector $n$ as a combination of $A$ and $B$, that is, $n = c_1 A + c_2 B$ (and if they are collinear, then the distances are always zero).

The condition that the plane goes through $0$ and $M$, means that $n \cdot M = 0$.

Now, $n \cdot M = (c_1 A + c_2 B) \cdot M = c_1 (A \cdot M) + c_2 (B \cdot M) = 0$, which gives us the ratio of $c_1$ to $c_2$

$$\frac{c_1}{c_2} = - \frac{B \cdot M}{A \cdot M}$$

Therefore, $$n = (B \cdot M) A - (A \cdot M)B$$

(You can then normalize $n$ if you want)