APPROXIMATION ALGORITHMS FOR INSCRIBING OR CIRCUMSCRIBING AN AXIALLY SYMMETRIC POLYGON TO A CONVEX POLYGON

Abstract

Given a convex polygon P with n vertices, we present algorithms to determine approximations of the largest axially symmetric convex polygon S contained in P, and the smallest such polygon S&apos; that contains P. More precisely, for any e > 0, we can find an axially symmetric convex polygon Q c P with area \Q\ > (1 - epsilon)\S\ in time O(n + 1/epsilon(3/2)), and we can find an axially symmetric convex polygon Q&apos; containing P with area \Q&apos;\ < (1 + E)\S&apos;\ in time 0(n + (1/epsilon(2)) log(1/epsilon)). If the vertices of P are given in a sorted array, we can obtain the same results in time O((1/rootepsilon) log n+1/epsilon(3/2)) and O((1/epsilon) log n+ (1/epsilon(2)) log(1/epsilon)) respectively.