Polygon scheduling


Hurink, J.L. (1996) Polygon scheduling. Discrete Applied Mathematics, 70 (1). pp. 37-55. ISSN 0166-218X

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.
Item Type:Article
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:http://purl.utwente.nl/publications/66532
Official URL:http://dx.doi.org/10.1016/0166-218X(95)00100-6
Export this item as:BibTeX
HTML Citation
Reference Manager


Repository Staff Only: item control page