# Lagrange Multiplier

# 2.1 Nearest Point On Perpendicular Bisector

Find the distance $d$ from a given point $X$ to the nearest point $Y$ on the perpendicular bisector of two other given points $A$ and $B$.

(Practical use: drawing Voronoi tesselation using distance estimate, when $A$ and $B$ are the two nearest centers to $X$.)

Let the function to be minimized be $$f(Y) = d^2 = \sum (x_i - y_i)^2$$ then $$(\operatorname{grad} f)_i = -2 (x_i - y_i).$$

Let the midpoint of $A,B$ be $M = (A + B)/2$ and the normal of the bisector be $N = (A - B)/2$. Then let the constraint on $Y$ be $$g(Y) = (Y - M) \cdot N = \sum (y_i - m_i) n_i$$ with $$(\operatorname{grad} g)_i = n_i.$$

By the method of Lagrange multiplier, solve simultaneously $$\operatorname{grad} f = \lambda \operatorname{grad} g \quad\quad g = 0$$ that is $$-2(x_i - y_i) = \lambda n_i\quad\quad\sum(y_i-m_i)n_i = 0.$$

In matrix form using 4D with $\mu = \lambda / 2$, that gives

$$\begin{pmatrix} 1 & & & & -n_1 \\ & 1 & & & -n_2 \\ & & 1 & & -n_3 \\ & & & 1 & -n_4 \\ n_1 & n_2 & n_3 & n_4 & 0 \end{pmatrix} \begin{pmatrix} y_1 \\ y_2 \\ y_3 \\ y_4 \\ \mu \end{pmatrix} = \begin{pmatrix} x_1 \\ x_2 \\ x_3 \\ x_4 \\ N \cdot M \end{pmatrix}$$

Subtracting from the bottom row, $n_1$ times the top row, $n_2$ times the second row, and so on (Gaussian elimination by elementary row operations), gives the equivalent triangular system:

$$\begin{pmatrix} 1 & & & & -n_1 \\ & 1 & & & -n_2 \\ & & 1 & & -n_3 \\ & & & 1 & -n_4 \\ & & & & N \cdot N \\ \end{pmatrix} \begin{pmatrix} y_1 \\ y_2 \\ y_3 \\ y_4 \\ \mu \end{pmatrix} = \begin{pmatrix} x_1 \\ x_2 \\ x_3 \\ x_4 \\ N \cdot (M - X) \end{pmatrix}$$

Solving by back substitution, $$\mu = \frac{N \cdot (M - X)}{N \cdot N}\quad\quad Y = X + \mu N$$

Therefore $$d^2 = |Y - X|^2 = |\mu N|^2 = \mu^2 (N \cdot N) = \frac{(N \cdot (M - X))^2}{N \cdot N}$$

Checking the result, geometric considerations indicate the line $XY$ should be perpendicular to the perpendicular bisector, so vector projection can be used: $$Y = X + \frac{(M - X) \cdot N}{N \cdot N} N$$ This is the same answer, which is good. The dance with Lagrange multipliers may be more useful in other circumstances.