Geometric optimization and sums of algebraic functions - INRAE - Institut national de recherche pour l’agriculture, l’alimentation et l’environnement Accéder directement au contenu
Communication Dans Un Congrès Année : 2010

Geometric optimization and sums of algebraic functions

Résumé

We present a new optimization technique that yields the first FPTAS for several geometric problems These problems reduce to optimizing a sum of non-negative, constant description-complexity algebraic functions We first give a FPTAS for optimizing such a sum of algebraic functions, and then we apply it, to several geometric optimization problems We obtain the first, FPTAS for two fundamental geometric shape matching problems in fixed dimension: maximizing the volume of over lap of two polyhedra uncle, rigid motions, and minimizing their symmetric difference We obtain the first FPTAS for other problems in fixed dimension, such as computing an optimal ray in a weighted subdivision, finding the largest axially symmetric subset of a. polyhedron, and computing minimum area hulls.
Fichier principal
Vignette du fichier
39366_20100928101208768_1.pdf (572.69 Ko) Télécharger le fichier
Origine : Fichiers éditeurs autorisés sur une archive ouverte
Loading...

Dates et versions

hal-02757340 , version 1 (04-06-2020)

Identifiants

  • HAL Id : hal-02757340 , version 1
  • PRODINRA : 39366
  • WOS : 000280699900073

Citer

Antoine Vigneron. Geometric optimization and sums of algebraic functions. ACM-SIAM Symposium on Discrete Algorithms, Jan 2010, Austin - Texas, United States. ⟨hal-02757340⟩

Collections

INRA INRAE MATHNUM
7 Consultations
144 Téléchargements

Partager

Gmail Facebook X LinkedIn More