# Histogram decomposition and stereolithography

Fekete, Sandor P. and Mitchell, Joseph S. B.
(1997)
*Histogram decomposition and stereolithography.*

Technical Report
, 13 p.

## Abstract

A polyhedral solid model can be constructed by the process of stereolithography if it has a facet so that all points of the model can see this facet, in the direction orthogonal to it; such a polyhedron is a histogram. In stereolithography, or other forms of layered manufacturing, one may want to decompose a model into a small number of histograms. In this note, we provide the first algorithmic results on the histogram decomposition problem, proving that it is NP-complete to decide if a model can be decomposed into k histograms, if the model is either a polygonal region (with holes) in the plane, or a solid polyhedral model of genus 0.

Download: |
Postscript
Download (268kB) | Preview |
---|---|

Editorial actions: |
View Item (Login required) |

ZAIK Number: | zpr97-280 |
---|---|

Depositing User: | Archive Admin |

Date Deposited: | 02 Apr 2001 00:00 |

Last Modified: | 19 Dec 2011 09:45 |

URI: | http://e-archive.informatik.uni-koeln.de/id/eprint/280 |