Accéder directement au contenu Accéder directement à la navigation
Communication dans un congrès

Geometric optimization and sums of algebraic functions

Abstract : 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.
Type de document :
Communication dans un congrès
Liste complète des métadonnées

Littérature citée [26 références]  Voir  Masquer  Télécharger

https://hal.inrae.fr/hal-02757340
Déposant : Migration Prodinra <>
Soumis le : jeudi 4 juin 2020 - 00:19:14
Dernière modification le : vendredi 12 juin 2020 - 10:43:26

Fichier

39366_20100928101208768_1.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

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

Collections

Citation

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

Partager

Métriques

Consultations de la notice

4

Téléchargements de fichiers

18