Geometric optimization and sums of algebraic functions

Antoine Vigneron*

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

15 Scopus citations

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 overlap of two polyhedra under 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.

Original languageEnglish (US)
Title of host publicationProceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms
PublisherAssociation for Computing Machinery (ACM)
Pages906-917
Number of pages12
ISBN (Print)9780898717013
DOIs
StatePublished - Jan 1 2010
Event21st Annual ACM-SIAM Symposium on Discrete Algorithms - Austin, TX, United States
Duration: Jan 17 2010Jan 19 2010

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

Other

Other21st Annual ACM-SIAM Symposium on Discrete Algorithms
CountryUnited States
CityAustin, TX
Period01/17/1001/19/10

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Fingerprint Dive into the research topics of 'Geometric optimization and sums of algebraic functions'. Together they form a unique fingerprint.

Cite this