Do computational geometers use Lagrange multipliers?

Question

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.

Answer 1

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

Answer 2

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.

---

         
          ^{(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.