Name
Abstract | ||
|---|---|---|
In this paper we consider the problem of decomposing a simple polygon into subpolygons that exclusively use vertices of the given polygon. We allow two types of subpolygons: pseudo-triangles and convex polygons. We call the resulting decomposition PT-convex. We are interested in minimum decompositions, i.e., in decomposing the input polygon into the least number of subpolygons. Allowing subpolygons of one of two types has the potential to reduce the complexity of the resulting decomposition considerably. The problem of decomposing a simple polygon into the least number of convex polygons has been considered. We extend a dynamic-programming algorithm of Keil and Snoeyink for that problem to the case that both convex polygons and pseudo-triangles are allowed. Our algorithm determines such a decomposition in O(n^3) time and space, where n is the number of the vertices of the polygon. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1016/j.comgeo.2007.10.005 | Comput. Geom. |
Keywords | Field | DocType |
resulting decomposition,convex polygons,minimum decomposition,decomposition pt-convex,dynamic-programming algorithm,pseudo-triangles,input polygon,convex polygon,decomposition,simple polygon,dynamic programming,dynamic programming algorithm | Discrete mathematics,Rectilinear polygon,Polygon,Combinatorics,Polygon covering,Regular polygon,Point in polygon,Star-shaped polygon,Simple polygon,Mathematics,Polygon triangulation | Journal |
Volume | Issue | ISSN |
41 | 1-2 | Computational Geometry: Theory and Applications |
Citations | PageRank | References |
0 | 0.34 | 15 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Stefan Gerdjikov | 1 | 33 | 6.40 |
| Alexander Wolff | 2 | 222 | 22.66 |