Maximizing the area of an axially symmetric polygon inscribed in a simple polygon

摘要

In this paper we solve the following optimization problem: given a simple polygon P, what is the maximum-area polygon that is axially symmetric and is contained in P? This problem pops up in shape reasoning when planar shapes are approximated by simpler shapes, e.g., symmetric shapes, or when they are decomposed hierarchically into simpler shapes. We propose an algorithm for solving the problem, analyze its running time, and describe our implementation of it (for the case of a convex polygon). The algorithm is based on building and investigating a planar map, each cell of which corresponds to a different configuration of the inscribed polygon. We prove that the complexity of the map is O(n~4), where n is the complexity of P. For a convex polygon the complexity is Θ(n~3) in the worst case. A substantial part of the work concentrates on calculation and analysis of arcs of the planar map. Arcs represent topological changes of the structure of the inscribed polygon, and are determined by the geometry of the original polygon. For each face of the map we calculate the area function of the inscribed polygons and look for a global maximum of the compound area function. We achieve this goal by using a numerical method.