Can anyone point me to an example of a problem that (more or less) originated in computational geometry whose solution requires the use of Lagrange multipliers (or Kuhn-Tucker conditions, or dual variables in a linear program, etc.)? I have not been able to find such an example in any of the literature that I own.
2 Answers
A convex optimization method for constructing a set of points in the plane with prescribed (combinatorial) Delaunay triangulation is given in
Euclidean structures on simplicial surfaces and hyperbolic volume I Rivin - Annals of Mathematics, 1994
Two examples, neither a direct hit on what you seek, I think. But maybe they will trigger connections for others to answer better.
(1) Moody T. Chu and Matthew M. Lin. "Low-Dimensional Polytope Approximation and Its Applications to Nonnegative Matrix Factorization." SIAM J. Sci. Comput., 30(3), 1131–1155. (Journal link.)
This paper's focus is approximating a polytope with another with fewer facets. At the heart of their work is a convex-hull fitting problem, for which they use Lagrange multipliers.
![CHFitting](https://i.sstatic.net/UQvop.png)
(Image from Chu PDF presentation.)
(2) Kojima, Masakazu, Nimrod Megiddo, and Shinji Mizuno. "A Lagrangian Relaxation Method for Approximating the Analytic Center of a Polytope." IBM Thomas J. Watson Research Division, 1992.
Whether calculating the analytic center of a polytope "originated in computational geometry" is debatable.
Finally, Lagrange multipliers find use in robotics, again not really originating in computational goemetry.