Exact polynomial system solving for robust geometric computation
dc.contributor.advisor | Friesen, Donald | |
dc.contributor.advisor | Keyser, John | |
dc.creator | Ouchi, Koji | |
dc.date.accessioned | 2007-04-25T20:08:33Z | |
dc.date.available | 2007-04-25T20:08:33Z | |
dc.date.created | 2006-12 | |
dc.date.issued | 2007-04-25 | |
dc.identifier.uri | https://hdl.handle.net/1969.1/4805 | |
dc.description.abstract | I describe an exact method for computing roots of a system of multivariate polynomials with rational coefficients, called the rational univariate reduction. This method enables performance of exact algebraic computation of coordinates of the roots of polynomials. In computational geometry, curves, surfaces and points are described as polynomials and their intersections. Thus, exact computation of the roots of polynomials allows the development and implementation of robust geometric algorithms. I describe applications in robust geometric modeling. In particular, I show a new method, called numerical perturbation scheme, that can be used successfully to detect and handle degenerate configurations appearing in boundary evaluation problems. I develop a derandomized version of the algorithm for computing the rational univariate reduction for a square system of multivariate polynomials and a new algorithm for a non-square system. I show how to perform exact computation over algebraic points obtained by the rational univariate reduction. I give a formal description of numerical perturbation scheme and its implementation. | en |
dc.format.extent | 838575 bytes | en |
dc.format.medium | electronic | en |
dc.format.mimetype | application/pdf | |
dc.language.iso | en_US | |
dc.publisher | Texas A&M University | |
dc.subject | exact computation | en |
dc.subject | geometric computation | en |
dc.title | Exact polynomial system solving for robust geometric computation | en |
dc.type | Book | en |
dc.type | Thesis | en |
thesis.degree.department | Computer Science | en |
thesis.degree.discipline | Computer Science | en |
thesis.degree.grantor | Texas A&M University | en |
thesis.degree.name | Doctor of Philosophy | en |
thesis.degree.level | Doctoral | en |
dc.contributor.committeeMember | Chen, Jianer | |
dc.contributor.committeeMember | Rojas, J. Maurice | |
dc.type.genre | Electronic Dissertation | en |
dc.type.material | text | en |
dc.format.digitalOrigin | born digital | en |
Files in this item
This item appears in the following Collection(s)
-
Electronic Theses, Dissertations, and Records of Study (2002– )
Texas A&M University Theses, Dissertations, and Records of Study (2002– )