Efficient algorithms are given for decomposing a simple polygon into two special polygons, each with the property that every
boundary and interior point can be connected to a single edge by a perpendicular line segment interior to the polygon. This
allows efficient construction of certain classes of 3D parts via Layered Manufacturing.
Research of II and RJ supported, in part, by NSF grant CCR-9712226. This effort is also sponsored, in part, by the Army High
Performance Computing Research Center under the auspices of the Department of the Army, Army Research Laboratory cooperative
agreement number DAAD19-01-2-0014, the content of which does not necessarily reflect the position or the policy of the government,
and no official endorsement should be inferred. Research of MS supported by NSERC.