Adaptive Isotopic Approximation of Nonsingular Curves and Surfaces
by Lin, Long, Ph.D., NEW YORK UNIVERSITY, 2011, 147 pages; 3482906
 Abstract: Consider the problem of computing isotopic approximations of nonsingular curves and surfaces that are implicitly represented by equations of the form f(X,Y) = 0 and f(X,Y,Z ) = 0. This fundamental problem has seen much progress along several fronts, but we will focus on domain subdivision algorithms. Two algorithms in this area are from Snyder (1992) and Plantinga & Vegter (2004). We introduce a family of new algorithms that combines the advantages of these two algorithms: like Snyder, we use the parameterizability criterion for subdivision, and like Plantinga and Vegter, we exploit nonlocal isotopy. We first apply our approach to curves, resulting in a more efficient algorithm. We then extend our approach to surfaces. The extension is by no means routine, as the correctness arguments and case analysis are more subtle. Also, a new phenomenon arises in which local rules for constructing surfaces are no longer sufficient. We further extend our algorithms in two important and practical directions: first, we allow subdivision cells to be non squares or non cubes, with arbitrary but bounded aspect ratios: in 2D, we allow boxes to be split into 2 or 4 children; and in 3D, we allow boxes to be split into 2, 4 or 8 children. Second, we allow the input region-of-interest (ROI) to have arbitrary geometry represented by an quadtree or octree, as long as the curves or surfaces has no singularities in the ROI and intersects the boundary of ROI transversally. Our algorithm is numerical because our primitives are based on interval arithmetic and exact BigFloat numbers. It is practical, easy to implement exactly (compared to algebraic approaches) and does not suffer from implementation gaps (compared to geometric approaches). We report some very encouraging experimental results, showing that our algorithms can be much more efficient than the algorithms of Plantinga and Vegter (2D and 3D) and Snyder (2D only).

 Adviser Chee K. Yap School NEW YORK UNIVERSITY Source DAI/B 73-03, p. , Dec 2011 Source Type Dissertation Subjects Mathematics; Computer science Publication Number 3482906
Access the complete dissertation:

» Find an electronic copy at your library.
 Use the link below to access a full citation record of this graduate work: http://gateway.proquest.com/openurl%3furl_ver=Z39.88-2004%26res_dat=xri:pqdiss%26rft_val_fmt=info:ofi/fmt:kev:mtx:dissertation%26rft_dat=xri:pqdiss:3482906 If your library subscribes to the ProQuest Dissertations & Theses (PQDT) database, you may be entitled to a free electronic version of this graduate work. If not, you will have the option to purchase one, and access a 24 page preview for free (if available).