Geometric optimization and sums of algebraic functions

by
Antoine Vigneron

Time: 11am on Friday, Dec 11
Venue: 4472

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