Paper Info
Title
On Partitioning Rectilinear Polygons into Star-Shaped Polygons
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.
Year
DOI
Venue
1991
10.1007/BF01759071
Algorithmica
Keywords
Field
DocType
star-shaped polygons,polygon decomposition,computational geometry.,computational geometry,time complexity
Discrete mathematics,Polygon,Rectilinear polygon,Combinatorics,Polygon mesh,Boolean operations on polygons,Polygon covering,Smoothing group,Point in polygon,Star-shaped polygon,Mathematics
Journal
Volume
Issue
ISSN
6
6
0178-4617
Citations 
PageRank 
References 
0
0.34
6
Authors
2
Name
Order
Citations
PageRank
Robon Liu100.34
Simeon C. Ntafos259998.18