Contour Edge Analysis for Polyhedron Projections. Lutz Kettner and Emo Welzl. In: W. Strasser, R. Klein, R. Rau (Eds.), Geometric Modeling: Theory and Practice, Springer, pp. 379-394, 1997.

Given a polyhedron (in 3-space) and a view
point, an edge of the polyhedron is called *contour edge*, if
one of the two incident facets is directed towards the view point,
and the other incident facet is directed away from the view point.
Algorithms on polyhedra can exploit the fact that the number of
contour edges is usually much smaller than the overall number of
edges. The main goal of this paper is to provide evidence for
(and quantify) the claim, that the number of contour edges is
small in many situations.

An asymptotic analysis of polyhedral
approximations of a sphere with Hausdorff distance *eps*
shows that while the required number of edges for such an
approximation grows like *Theta(1/eps)*, the number of
contour edges in a random *orthogonal* projection is
*Theta(1/sqrt(eps))*.

In an experimental study we investigate a number of polyhedral objects from several application areas. We analyze the expected number of contour edges and the expected number of intersections of contour edges in a projection (a quantity relevant for line sweep algorithms). We conclude that, indeed, the number of contour edges is small and the number of intersections of contour edges appears to be even more favorable. As a specific application we describe the computation of the silhouette of a polyhedral object with a sweep line algorithm in object space.

Lutz Kettner
(*<surname>*@mpi-inf.mpg.de).
Last modified on Friday, 15-Jul-2005 18:55:24 MEST.