Polygon scheduling

Research output: Contribution to journalArticleAcademicpeer-review

1 Citation (Scopus)
99 Downloads (Pure)

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 languageEnglish
Pages (from-to)37-55
Number of pages19
JournalDiscrete applied mathematics
Volume70
Issue number1
DOIs
Publication statusPublished - 10 Sept 1996

Fingerprint

Dive into the research topics of 'Polygon scheduling'. Together they form a unique fingerprint.

Cite this