Document Type : Research Paper

Authors

• Zahraa Marzeh
• Maryam Tahmasbi
• Narges Mirehi

Department of computer science, Shahid Beheshti University, G.C., Tehran, Iran.

Abstract

In many industrial and non-industrial applications, it is necessary to identify the largest inscribed rectangle in a certain shape. The problem is studied for convex and non-convex polygons. Another criterion is the direction of the rectangle: axis aligned or general. In this paper a heuristic algorithm is presented for finding the largest axis aligned inscribed rectangle in a general polygon. Comparing with stare of the art, the rectangles resulted from our algorithm have bigger area. We also proposed an approach to use the algorithm for finding a rectangle with general direction.

Keywords

• non-convex polygon
• IIC
• inscribed rectangle
• longest path
• largest cycle