TY - JOUR

T1 - Geometric optimization and sums of algebraic functions

AU - Vigneron, Antoine E.

N1 - KAUST Repository Item: Exported on 2020-10-01

PY - 2014/1/1

Y1 - 2014/1/1

N2 - We present a new optimization technique that yields the first FPTAS for several geometric problems. These problems reduce to optimizing a sum of nonnegative, constant description complexity algebraic functions. We first give an 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 nonnegative, constant description complexity algebraic functions. We first give an 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://hdl.handle.net/10754/577071

UR - https://dl.acm.org/doi/10.1145/2532647

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

U2 - 10.1145/2532647

DO - 10.1145/2532647

M3 - Article

SN - 1549-6325

VL - 10

SP - 1

EP - 20

JO - ACM Transactions on Algorithms

JF - ACM Transactions on Algorithms

IS - 1

ER -