Given a polygonal object (simple polygon, geometric graph, wire-frame, skel
eton or more generally a set of line segments) in three-dimensional Euclide
an space, we consider the problem of computing a variety of "nice" parallel
(orthographic) projections of the object. We show that given a general pol
ygonal object consisting of n line segments in space, deciding whether it a
dmits a crossing-free projection can be done in O(n(2) log n + k) time and
O(n(2) + k) space, where X: is the number of edge intersections of forbidde
n quadrilaterals (i,e., a set of directions that admits a crossing) and var
ies from zero to O(n(4)). This implies for example that, given a simple pol
ygon in 3-space, we can determine if there exists a plane on which the proj
ection is a simple polygon, within the same complexity. Furthermore, if suc
h a projection does not exist, a minimum-crossing projection can be found i
n O(n(4)) time and space, We show that an object always admits a regular pr
ojection (of interest to knot theory) and that such a projection can be obt
ained in O(n(2)) time and space or in O(n(4)) time and linear space, A desc
ription of the set of all directions which yield regular projections can be
computed in O(n(3) log n + k) time, where k is the number of intersections
of a set of quadratic arcs on the direction sphere and varies from O(n(3))
to O(n(6)). Finally, when the objects are polygons and trees in space, we
consider monotonic projections, i.e., projections such that every path from
the root of the tree to every leaf is monotonic in a common direction on t
he projection plane. We solve a variety of such problems. For example, give
n a polygonal chain P, we can determine in O(n) time if P is monotonic on t
he projection plane, and in O(n log n) time we can find all the viewing dir
ections with respect to which P is monotonic. In addition, in O(n(2)) time,
we can determine all directions with respect to which a given tree or simp
le polygon is monotonic. (C) 1999 Academic Press.