Back to search

Institutes outside Greece

Robust algebraic methods for geometric computing

Abstract

dc:description

Geometric computation in computer aided geometric design and solid modeling calls for solving non-linear polynomial systems in an approximate-yetcertified manner. We introduce new subdivision algorithms that tackle this fundamental problem. In particular, we generalize the univariate so-called continued fraction solver to general dimension. Fast bounding functions, unicity tests, projection and preconditioning are employed to speed up convergence. Apart from practical experiments, we provide theoretical bit complexity estimates, as well as bounds in the real RAM model, by means of real condition numbers. A main bottleneck for any real solving method is singular isolated points. We employ local inverse systems and certified numerical computations to provide certification criteria to treat singular solutions. In doing so, we are able to check existence and uniqueness of singularities of a given multiplicity structure using verification methods, based on interval arithmetic and fixed point theorems. Two major geometric applications are undertaken. First, the approximation of planar semi-algebraic sets, commonly occurring in constraint geometric solving. We present an efficient algorithm to identify connected components and, for a given precision, to compute polygonal and isotopic approximation of the exact set. Second, we present an algebraic framework to compute generalized Voronoï diagrams, that is applicable to any diagram type in which the distance from a site can be expressed by a bi-variate polynomial function (anisotropic, power diagram etc). In cases where this is not possible (eg. Apollonius diagram, VD of ellipses and so on), we extend the theory to implicitly given distance functions.

Degree

thesis:*
Grantor dc:publisher
Institutes outside Greece
Year dc:date
2011

Author and committee

dc:creator, dc:contributor.*
Authors dc:creator
  • Mantzaflaris, Angelos
  • Μαντζαφλάρης, Άγγελος

Subjects

dc:subject × 34

Rights

Language dc:language
eng

Identifiers

dc:identifier.*
Identifier
10.12681/eadd/62803

Chain of custody

source
Harvested from
Greek National Archive of PhD Theses
Base URL
phdtheses.ekt.gr/eadd_oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Mantzaflaris, Angelos; Μαντζαφλάρης, Άγγελος. Robust algebraic methods for geometric computing. Institutes outside Greece, 2011. http://hdl.handle.net/10442/hedi/62803