# 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.