Fat Arcs and Fat Spheres for Approximating Algebraic Curves and Solving Polynomial Systems

Fat Arcs and Fat Spheres for Approximating Algebraic Curves and Solving Polynomial Systems

Studying objects defined by algebraic equations has been an active research area for a long time. The reason for the interest is the wide variety of applications, which appear in mathematical modeling and physics. Modeling algebraic objects is an essential ingredient of free-form surface visualization and numerical simulations. Thus modeling algorithms are frequently used in CAD-systems, manufacturing, robotics etc. Several problems in applications are described by multivariate polynomial systems with a low dimensional solution set. In the thesis we present a method to generate bounding regions for one- or zero-dimensional solution sets of multivariate polynomial systems.
The one-dimensional solution set of a multivariate polynomial system forms an algebraic curve. These curves are defined as the intersection curves of algebraic surfaces. Representing these algebraic curves is a fundamental problem of some geometric algorithms. For instance such algebraic curves appear as the boundary curves of surfaces created by Boolean operations or the self-intersection curves of surfaces. Due to the importance of these curves several algorithms have been introduced to approximate them, especially for curves embedded in lower dimensional spaces. We formulate in the thesis a new geometrical method, which approximates one-dimensional algebraic sets. The algorithm generates a set of quadratic regions, the so called “fat arcs” , which encloses the algebraic curve within a user specified tolerance. We describe different methods, how to generate these bounding regions, and we study their behavior. Then we combine the fat arc generation with the standard subdivision technique.
The computation of zero-dimensional solution sets of multivariate polynomial systems has also several applications in algebra and geometry. Therefore various methods exist to find or to isolate the roots of polynomial systems. They use symbolic, numeric or combined techniques in order to find the solutions. In the end of the thesis we generalize the definition of fat arcs to the concept of fat spheres. We introduce an iterative domain reduction method based on fat sphere generation. This method generates sequences of bounding regions, which converge with order three to the single roots of a multivariate polynomial system.