Many combinatorial optimization problems have natural geometric versions, that is, version in which the objects are points or lines in Euclidean space and the cost function is given by a planar metric. For example, a Euclidean Traveling Salesman Problem is specified by giving n points in the plane, and then requiring the construction of a tour with minimum Euclidean (L2) length passing through these points. A problem encountered in VLSI design is that of constructing minimum weight Steiner trees on a set of n points in the plane, for which the edge lengths are given by the Manhattan, or L1, metric. For many such problems there are natural ‘dual’ problems. These are geometric problems, usually involving optimally packing some shape in the plane, with the property that any feasible solution to the dual problem provides a bound on the optimum solution to the original problem. Moreover, in some cases, the ‘best’ such bound is tight; its value equals that of the optimum solution. The authors describe several such optimization problems and their geometric duals. They also discuss the solvability of these problems.
