1.6.11 Polygon Partitioning
INPUT OUTPUT
Input Description:
A polygon or polyhedron P.
Problem:
How can P be partitioned into a small number of simple
(typically convex) pieces?
Excerpt from
The Algorithm Design Manual:
Polygon partitioning is an important preprocessing step for many
geometric algorithms, because most geometric problems are simpler
and faster on convex objects than on nonconvex ones.
We are better off whenever we can partition a nonconvex object
into a small number of
convex pieces,
because it is easier to work with the pieces
independently than with the original object.
Recommended Books
Related Problems
This page last modified on 2008-07-10
.
www.algorist.com
Computational Geometry : Algorithms and Applications
Computational Geometry in C
Art Gallery Theorems and Algorithms
