TY - GEN

T1 - Geometric optimization and sums of algebraic functions

AU - Vigneron, Antoine

PY - 2010

Y1 - 2010

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=77951698315&partnerID=8YFLogxK

U2 - 10.1137/1.9781611973075.73

DO - 10.1137/1.9781611973075.73

M3 - Conference contribution

AN - SCOPUS:77951698315

SN - 9780898717013

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 906

EP - 917

BT - Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms

PB - Association for Computing Machinery (ACM)

T2 - 21st Annual ACM-SIAM Symposium on Discrete Algorithms

Y2 - 17 January 2010 through 19 January 2010

ER -