POLYGON SCHEDULING

Consider a set of circles of the same length and r irregular polygons with vertices on a circle of this length. Each of the polygons has to be arranged on a given subset of all circles and the positions of the polygon on the different circles are depending on each other. How shou ld the polygons be arranged relative to each other to minimize some cr iterion function depending on the distances between adjacent vertices on all circles? A decomposition of the set of all arrangements of the polygons into local regions in which the optimization problem is conve x is given. An exact description of the local regions and a sharp boun d on the number of local regions are derived. For the criterion functi ons minimizing the maximum weighted distance, maximizing the minimum w eighted distance, and minimizing the sum of weighted distances the loc al optimization problems can be reduced to polynomially solvable netwo rk flow problems.