Polygon Optimization Problems (Computational Geometry, Algorithm)

Candidate: Chang,Jyun-Sheng


The thesis examines polygon optimization problems arising from the stockcutting problem. Two types of problems are considered: the inclusion problems and the enclosure problems. The inclusion (enclosure) problems ask for a maximum polygonal subset (minimum polygonal superset) of a given polygon, satisfying certain conditions. Both the area and perimeter metrics on the polygons can be used as the measure of optimality. Various geometric properties and algorithms for these problems are shown. The main results are: (1) An O(n('7)) time (O(n('6)) time) algorithm for finding a maximum area (perimeter) convex subset. (Only exponential time algorithms existed previously for the problem.) (2) An O(n('2) log n log k) time algorithm for finding a minimum area enclosing convex k-gon. (3) An O(n('2)) time algorithm for finding a minimum perimeter enclosing triangle. (4) An O(nk('4)) time algorithm for finding a minimum enclosing k-gon with a fixed shape.