טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentRogol Vadim
SubjectMaxmizing the Area of an Axially Symmetric Polygon Inscribed
by a Simple Polygon
DepartmentDepartment of Electrical Engineering
Supervisor Professor Gill Barequet


Abstract

In this thesis we solve the following optimization problem: Given a simple polygon P, what is the maximum-area polygon that is

axially symmetric and is contained by P? We propose an algorithm for solving this problem, analyze its complexity, and describe our

implementation of it (for the case of a convex polygon). The algorithm is based on building and investigating a planar map in

the dual plane, each cell of which corresponds to a different combinatorial structure of the inscribed polygon. Substantial part

of the work concentrates on calculation and analysis of arcs of the planar map. Arcs represent topological changes of the

structures of the inscribed polygon, and are determined by the geometry of the original polygon. We prove that the complexity of

the map is O(n4), where n is the complexity of P. For a convex polygon the complexity is Θ(n3) in the worst case. For each face of the map we calculate the area function of inscribed polygons and look for a global maximum of the compound area function. We achieve this goal by using a numerical method. Then we analyze the running-time complexity of the algorithm. Finally, we describe our implementation of the algorithm in software.

______