Personal tools
You are here: Home Projects External Projects Maximizing the Area of an Axis-Symmetric Polygon Inscribed by a Simple Polygon
« December 2017 »
December
SuMoTuWeThFrSa
12
3456789
10111213141516
17181920212223
24252627282930
31
Log in


Forgot your password?
 

Maximizing the Area of an Axis-Symmetric Polygon Inscribed by a Simple Polygon

[Maximum inscribed polygon]

Abstract

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 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, each cell of which corresponds to a different configuration of the inscribed 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.

Links

  • Gill Barequet and Vadim Rogol
    Maximizing the Area of an Axis-Symmetric Polygon Inscribed by a Simple Polygon [pdf]
  • Gill Barequet and Vadim Rogol
    Maximizing the Area of an Axis-Symmetric Polygon Inscribed by a Convex Polygon
    The 4th Israel-Korea Bi-National Conference on Geometric Modeling and Computer Graphics. Conference Proceedings, 2003, 141-146.
    [BibTex]

Contact

Vadim Rogol http://www.technion.ac.il/~rogolv/ rogolv@techunix.technion.ac.il
Gill Barequet barequet@cs.technion.ac.il
Document Actions