Geometric predicates as arrangements of hypersurfaces: Application to comparison of algebraic numbers

George Tzoumas 1
1 VEGAS - Effective Geometric Algorithms for Surfaces and Visibility
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : A lot of geometric predicates can be formulated as an arrangement of hypersurfaces (algebraic varieties) in a high-dimensional space, where each cell of the arrangement corresponds to an outcome of the predicate, and an evaluation of the predicate maps to point-location queries in this arrangement. To do this successfully, the arrangement has to be decomposed by the aid of subsidiary hypersurfaces, the degree of which plays a fundamental role in the algebraic complexity of the predicate, with respect to the input coefficients. For example, the widely used predicate of root comparison of quadratic polynomials can be mapped to an arrangement of lines and a parabola. For cubics, it becomes an arrangement of planes and a quartic surface, when a monic polynomial of degree d is represented as a point in R^d. Minimizing the degree of the subsidiary equations is an outstanding open problem.
Type de document :
Poster
Fall School Shapes, Geometry, and Algebra - SAGA 2010, Oct 2010, Kolympari, Greece
Liste complète des métadonnées

https://hal.inria.fr/inria-00538839
Contributeur : George Tzoumas <>
Soumis le : mardi 23 novembre 2010 - 14:06:00
Dernière modification le : jeudi 11 janvier 2018 - 06:20:14
Document(s) archivé(s) le : jeudi 24 février 2011 - 03:11:27

Fichier

poster-a3.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00538839, version 1

Collections

Citation

George Tzoumas. Geometric predicates as arrangements of hypersurfaces: Application to comparison of algebraic numbers. Fall School Shapes, Geometry, and Algebra - SAGA 2010, Oct 2010, Kolympari, Greece. 〈inria-00538839〉

Partager

Métriques

Consultations de la notice

175

Téléchargements de fichiers

144