Abstract
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 should the polygons be arranged relative to each other to minimize some criterion 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 convex is given. An exact description of the local regions and a sharp bound on the number of local regions are derived. For the criterion functions minimizing the maximum weighted distance, maximizing the minimum weighted distance, and minimizing the sum of weighted distances the local optimization problems can be reduced to polynomially solvable network flow problems.
Original language | English |
---|---|
Pages (from-to) | 37-55 |
Number of pages | 19 |
Journal | Discrete applied mathematics |
Volume | 70 |
Issue number | 1 |
DOIs | |
Publication status | Published - 10 Sept 1996 |