Computational and Algorithmic Representations of Geonetric Objects - CARGO: Degeneracy Detection for Curved Solids

Texas A&M Engineering Experiment Station, College Station TX

Investigators

Abstract

DMS-0138446 John Keyser Degeneracies are a major source of robustness problems in many geometric algorithms. Many degenerate situations can be expressed as a root of a multivariate system of polynomials. We propose to study the use of toric resultants to detect degenerate situations in solid modeling applications. By taking advantage of the underlying monomial structure of a system of polynomials, the toric resultant can provide a method for solving systems of polynomials that is dramatically more efficient than the classical "dense" resultants of Macaulay and Cayley. We will focus on application to boundary evaluation for curved solids. Our work will include enumeration of degenerate conditions and identifying detection algorithms for each category, using the toric resultant where appropriate. The work is intended to foster future collaborative research endeavors on topics including resolution of geometric degeneracies, general algebraic number computation, and computational Morse theory. Geometric degeneracies occur when a minor perturbation of the geometry would cause a qualitatively different positioning between the objects. Degeneracies, such as two overlapping surfaces or a vertex of one object lying on the face of another, are common occurances in many real-world solid modeling examples. The problems of detecting and dealing with degenerate situations becomes particularly difficult when dealing with curved surfaces. Usually, detecting such cases involves finding roots of polynomials. Thus, accurate and efficient root-finding is crucial to an effective approach for handling degeneracies. The toric resultant is an approach for finding solutions to systems of polynomial equations. Because of its efficiency compared to other methods of solving such systems, it is a promising approach for detecting and treating degeneracies. We propose to address degeneracies in solid modeling applications through the use of the toric resultant.