Return to search

Exact polynomial system solving for robust geometric computation

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.

Identiferoai:union.ndltd.org:tamu.edu/oai:repository.tamu.edu:1969.1/4805
Date25 April 2007
CreatorsOuchi, Koji
ContributorsFriesen, Donald, Keyser, John
PublisherTexas A&M University
Source SetsTexas A and M University
Languageen_US
Detected LanguageEnglish
TypeBook, Thesis, Electronic Dissertation, text
Format838575 bytes, electronic, application/pdf, born digital

Page generated in 0.002 seconds