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.
%0 Journal Article
%1 gw-dsppt-CGTA08
%A Gerdjikov, Stefan
%A Wolff, Alexander
%D 2008
%J Computational Geometry: Theory and Applications
%K convex_polygons decomposition dynamic_programming myown pseudo-triangles simple_polygon
%N 1--2
%P 21--30
%R 10.1016/j.comgeo.2007.10.005
%T Decomposing a Simple Polygon into Pseudo-Triangles
and Convex Polygons
%V 41
%X 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.
@article{gw-dsppt-CGTA08,
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
\emph{PT-convex}. We are interested in
\emph{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 \emph{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.},
added-at = {2024-07-14T10:03:47.000+0200},
author = {Gerdjikov, Stefan and Wolff, Alexander},
biburl = {https://www.bibsonomy.org/bibtex/209dfbebfdc0ef8bc8cffa30d2a6aadc5/awolff},
cites = {ahkst-dpccp-06, arss-zppt-03, b-eptp-05, cd-ocd-85,
cegghss-rspug-94, fmr-mcpcps-01, gl-mwpt-07,
gn-ppslm-06, gt-drssp-97, k-dpsc-85, kl-qgtam-98,
ks-tbcds-02, ks-aamcp-06, kss-kcdsp-02, mr-mwtnp-06,
pv-tsvcp-96, s-ocpps-05, st-avpgs-05, s-capnc-00,
ZZZ},
doi = {10.1016/j.comgeo.2007.10.005},
interhash = {060524a6faf5ced198ca15bcf3edd6fb},
intrahash = {09dfbebfdc0ef8bc8cffa30d2a6aadc5},
journal = {Computational Geometry: Theory and Applications},
keywords = {convex_polygons decomposition dynamic_programming myown pseudo-triangles simple_polygon},
number = {1--2},
pages = {21--30},
pdf = {http://www1.pub.informatik.uni-wuerzburg.de/pub/wolff/pub/gw-dsppt-08.pdf},
succeeds = {gw-pcdsp-06},
timestamp = {2024-07-14T10:03:47.000+0200},
title = {Decomposing a Simple Polygon into Pseudo-Triangles
and Convex Polygons},
volume = 41,
year = 2008
}