@techreport{Kettner:1996:CAE,
optpostscript = {},
number = {258},
month = dec,
author = {Lutz Kettner and Emo Welzl},
optkey = {},
optannote = {},
opttype = {},
url = {http://www.mpisb.mpg.de/~kettner/pub/contour_edge_tr_96_a.html},
address = {Switzerland},
localfile = {papers/Kettner.1996.CAE.pdf},
optkeywords = {},
optciteseer = {},
optdoi = {},
optwww = {},
abstract = {Given a polyhedron (in 3space) 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.},
title = {{C}ontour {E}dge {A}nalysis for {P}olyhedron {P}rojections},
year = {1996},
institution = {Departement Informatik, ETH Z{\"u}rich},
}
