Computing a global optimal solution to a design centering problem

In this paper the authors present a method for solving a special three-dimensional design centering problem arising in diamond manufacturing: Find inside a given (not necessarily convex) polyhedral rough stone the largest diamond of prescribed shape and orientation. This problem can be formulated as the one of finding a global maximum of a difference of two convex functions over ℝ³ and can be solved efficiently by using a global optimization algorithm provided that the objective function of the maximization problem can be easily evaluated. Here the authors prove that with the information available on the rough stone and on the reference diamond, evaluating the objective function at a point x amounts to computing the distance, with respect to a Minkowski gauge, from x to a finite number of planes. They propose a method for finding these planes and report some numerical results.