×

zbMATH — the first resource for mathematics

Decomposing a polygon into simpler components. (English) Zbl 0575.68077
The problem of decomposing a polygon into simpler components is of interest in fields such as computational geometry, syntactic pattern recognition, and graphics. In this paper we consider decompositions which do not introduce Steiner points. The simpler components we consider are convex polygons, spiral polygons, star-shaped polygons and monotone polygons. We apply a technique for improving the efficiency of dynamic programming algorithms in order to achieve polynomial time algorithms for the problems of decomposing a simple polygon into the minimum number of each of the component types. Using the same technique we are able to exhibit polynomial time algorithms for the problems of decomposing a simple polygon into each of the component types while minimizing the length of the internal edges used to form the decomposition. When the polygons are allowed to contain holes many of the problems become NP- hard.

MSC:
68R99 Discrete mathematics in relation to computer science
68Q25 Analysis of algorithms and problem complexity
90C39 Dynamic programming
PDF BibTeX XML Cite
Full Text: DOI