Journal article
OPTIMAL POLYGON COVER PROBLEMS AND APPLICATIONS
International journal of computational geometry & applications, Vol.12(4), pp.309-338
08/2002
DOI: 10.1142/S0218195902000918
Abstract
Polygon cover problems are important in several applied areas, such as material layout, layered manufacturing, radiation therapy and radiosurgery, etc. In this paper, we study three optimal polygon cover problems: monotone polygon cover among obstacles, star-shaped polygon cover among obstacles, and strip cover for trapezoidalized polygons. Based on some interesting geometric observations, we develop efficient algorithms for solving these problems. The complexity bounds of our monotone cover and star-shaped cover algorithms are comparable to those of the previously best known algorithms for simpler cases of the problems without considering obstacles. Our strip cover algorithm improves the quality of the previously best known solutions.
Details
- Title: Subtitle
- OPTIMAL POLYGON COVER PROBLEMS AND APPLICATIONS
- Creators
- DANNY Z Chen - University of Notre DameXIAOBO S HU - University of Notre DameXIAODONG WU - University of Texas–Pan American
- Resource Type
- Journal article
- Publication Details
- International journal of computational geometry & applications, Vol.12(4), pp.309-338
- DOI
- 10.1142/S0218195902000918
- ISSN
- 0218-1959
- eISSN
- 1793-6357
- Language
- English
- Date published
- 08/2002
- Academic Unit
- Electrical and Computer Engineering; Radiation Oncology; The Iowa Institute for Biomedical Imaging
- Record Identifier
- 9984197458002771
Metrics
10 Record Views