ISSN:
1432-0444
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract. The view graph of a surface N in 3-space is a graph embedded in the space ${\cal V}$ of centers or directions of projection, whose nodes correspond to maximal connected regions of ${\cal V}$ which yield equivalent views of N . The size of the view graph of a piecewise smooth algebraic surface N with transverse self-intersection curves and isolated triple-points and cross-caps is O(n K dim $\cal V$ d 6 dim $\cal V$), where n and d denote the number of ``component surfaces'' of N and their maximal degree, respectively, and where K=6 in general or K=3 for N diffeomorphic to the boundary of a polyhedron. (For surfaces without cross-caps, this bound has been established in [17].) Also, for the special piecewise linear case, where d=1 and K=3 , it is known that the size of the view graph is actually $\Theta$ (n3 dim $\cal V$). It is shown that the exact view graphs of such surfaces can be determined in O(n K(2 dim $\cal V$ +1)). $\cal P$ (d,L) time by a deterministic algorithm and in O(n K dim $\cal V +\epsilon$). $\cal P$ (d,L) expected time by a randomized algorithm. Here $\cal P$ is some polynomial, L is the maximal coefficient size of the defining polynomials of N , and ε is an arbitrarily small positive constant. Note that the randomized algorithm is, in terms of combinatorial complexity (where d and L are assumed to be constants which do not depend on n ), nearly optimal—its combinatorial time complexity exceeds the size of the view graph only by ε in the exponent. 〈lsiheader〉 〈onlinepub〉7 August, 1998 〈editor〉Editors-in-Chief: &lsilt;a href=../edboard.html#chiefs&lsigt;Jacob E. Goodman, Richard Pollack&lsilt;/a&lsigt; 〈pdfname〉20n2p205.pdf 〈pdfexist〉yes 〈htmlexist〉no 〈htmlfexist〉no 〈texexist〉no 〈sectionname〉 〈/lsiheader〉
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/PL00009383
Permalink
