On partitioning rectilinear polygons into star-shaped polygons |
| |
| Authors: | Robin Liu and Simeon Ntafos |
| |
| Affiliation: | (1) Department of Computer Engineering and Sciences, Yuan-Ze Institute of Technology, Neili, Taiwan, Republic of China;(2) Computer Science Program, University of Texas at Dallas, 75083 Richardson, TX, USA |
| |
| Abstract: | We present an algorithm for finding optimum partitions of simple monotone rectilinear polygons into star-shaped polygons. The algorithm may introduce Steiner points and its time complexity isO(n), wheren is the number of vertices in the polygon. We then use this algorithm to obtain anO(n logn) approximation algorithm for partitioning simple rectilinear polygons into star-shaped polygons with the size of the partition being at most six times the optimum. |
| |
| Keywords: | Polygon decomposition Star-shaped polygons Computational geometry |
| 本文献已被 SpringerLink 等数据库收录！ |
|
