This project is directed at developing and implementing algorithms for decomposing polyhedra into simpler parts, the result of which is called a partition. The use of three different algorithmic paradigms is being examined: space sweep, divide-and-conquer, and incremental refinement. In the last paradigm, a sequence of increasingly refined partitions is constructed, in which each partition is based upon its predecessor. Each of the paradigms relies upon being able to query one or more current partitions. These queries are supported by the use of a novel data structure, known as the facet-edge data structure, which previous research suggests is well suited to algorithms for decomposing polyhedra. Implementation of each new algorithm will demonstrate its practicality.
