M.Sc Student | Rogol Vadim |
---|---|

Subject | Maxmizing the Area of an Axially Symmetric Polygon Inscribed by a Simple Polygon |

Department | Department of Electrical Engineering |

Supervisor | Professor Gill Barequet |

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*(*n*^{4}), where *n*
is the complexity of *P*. For a convex polygon the complexity is *Θ*(*n*^{3}) 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.

______