### Abstract

An important direction of research in computational geometry has been to find methods for decomposing complex structures into simpler components. In this paper, we examine the problem of decomposing a threedimensional polyhedron P into a minimal number of convex pieces. Letting n be the number of vertices in P and N the number of edges which exhibit a reflex angle (i.e. the notches of P), our main result is an O(nN^{3}) time algorithm for computing a convex decomposition of P. The algorithm produces O(N^{2}) convex parts, which is optimal in the worst case. In most situations where the problem arises (e.g, graphics, tool design, pattern recognition), the number of notches N seems greatly dominated by the number of vertices n; the algorithm is therefore viable in practice.

Original language | English (US) |
---|---|

Title of host publication | Conference Proceedings of the 13th Annual ACM Symposium on Theory of Computing, STOC 1981 |

Publisher | Association for Computing Machinery |

Pages | 70-79 |

Number of pages | 10 |

ISBN (Print) | 0897910419 |

DOIs | |

State | Published - May 11 1981 |

Externally published | Yes |

Event | 13th Annual ACM Symposium on Theory of Computing, STOC 1981 - Milwaukee, United States Duration: Jun 11 1981 → Jun 13 1981 |

### Publication series

Name | Proceedings of the Annual ACM Symposium on Theory of Computing |
---|---|

ISSN (Print) | 0737-8017 |

### Other

Other | 13th Annual ACM Symposium on Theory of Computing, STOC 1981 |
---|---|

Country | United States |

City | Milwaukee |

Period | 6/11/81 → 6/13/81 |

### All Science Journal Classification (ASJC) codes

- Software

## Fingerprint Dive into the research topics of 'Convex decompositions of polyhedra'. Together they form a unique fingerprint.

## Cite this

*Conference Proceedings of the 13th Annual ACM Symposium on Theory of Computing, STOC 1981*(pp. 70-79). (Proceedings of the Annual ACM Symposium on Theory of Computing). Association for Computing Machinery. https://doi.org/10.1145/800076.802459