Repository logo
 

Minimum Cost Polygon Overlay With Rectangular Shape Stock Panels

Files

Thesis(1.04 MB)

Date

2007

Authors

Supervisor

Connor, Andrew

Item type

Thesis

Degree name

Master of Computer and Information Sciences

Journal Title

Journal ISSN

Volume Title

Publisher

Auckland University of Technology

Abstract

Minimum Cost Polygon Overlay (MCPO) is a unique two-dimensional optimization problem that involves the task of covering a polygon shaped area with a series of rectangular shaped panels. The challenges in solving MCPO problems are related to the interdependencies that exist among the parameters and constraints that may be applied to the solution. This thesis examines the MCPO problem to construct a model that captures essential parameters to be solved using optimization algorithms. The purpose of the model is to make it possible that a solution for an MCPO problem can be generated automatically. A software application has been developed to provide a framework for validating the model. The development of the software has uncovered a host of geometric operations that are required to enable optimization to take place. Many of these operations are non-trivial, demanding novel, well-constructed algorithms based on careful appreciation of the nature of the problem. For the actual optimization task, three algorithms have been implemented: a greedy search, a Monte Carlo method, and a Genetic Algorithm. The behavior of the completed software is observed through its application on a series of test data. The results are presented to show the effectiveness of the software under various settings. This is followed by critical analysis of various findings of the research. Conclusions are drawn to summarize lessons learned from the research. Important issues about which no satisfactory explanation exists are given as material to be studied by future research.

Description

Keywords

Topology, Tesselations, Tiling (mathematics), Data processing, Optimization algorithms

Source

DOI

Publisher's version

Rights statement

Permanent link

https://hdl.handle.net/10292/161

Collections

Masters Theses