Geometric algorithms and modeling with algebraic primitives

Dr. Angelos Mantzaflaris

Sept. 1, 2011, 8 a.m. S2 416

We present examples of effective use of applied algebra in geometric modeling. First, the approximation of planar semi-algebraic sets, commonly occurring in constraint geometric solving. We present a method that identifies connected components and, for a given precision, computes a polygonal and isotopic approximation of a planar semi-algebraic set. We focus on the special case of arrangements of algebraic curves. Second, we present an algebraic framework to compute generalized Voronoi diagrams, that is applicable to diagrams where the distance from a site is expressed by a bi-variate polynomial function (anisotropic, power diagram etc) or by a tri-variate implicit equation (eg. Apollonius diagram, diagram of ellipses and so on). A common need behind these algorithms is efficient polynomial system solving. To this end, we introduce new subdivision methods, i.e. branch and bound techniques that compute real solutions both fast and accurately. We discuss difficulties posed by singular solutions as well as local methods for their treatment.