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.
Origine : Fichiers éditeurs autorisés sur une archive ouverte
Loading...