Histogram decomposition and stereolithography

Fekete, Sandor P. and Mitchell, Joseph S. B. (1997) Histogram decomposition and stereolithography.
Technical Report , 13 p.


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: [img] Postscript
Download (268kB) | Preview
Editorial actions: View Item View Item (Login required)
Deposit Information:
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