Optimum Turn-­Restricted Paths, Nested Compatibility, and Optimum Convex Polygons

We consider two apparently unrelated classes of combinatorial and geometric optimization problems. First, we give compact extended formulations, i.e., polynomial-size linear programming formulations with integer optima, for optimum path problems with turn restrictions satisfying a nested compatibility condition in acyclic digraphs. We then apply these results to optimum convex polygon problems in the plane, by interpreting certain Dynamic Programming algorithms as sequences of optimum turn-restricted path problems with nested compatibility in acyclic digraphs. As a result, we derive compact extended formulations for these geometric problems as well.