Minimum area polygons with two reflex angles enclosing k Points

Abstract

We present in this paper, algorithms for finding the minimum area isothetic polygons having two reflex angles containing k points; (k<n) Our algorithms are based on line sweep paradigm. The idea is to enumerate all the polygons in each kind and find the minimum one. We also analyse the complexities of each of the algorithms. We find that out of the four orthogonal polygons with two reflex angles, three are orthoconvex and the algorithms presented for these polygons work in time, where n could be O(n-k)³ in the worst case. The algorithm for the non-orthoconvex polygon has a complexity of where n could be O((n-k)³ n) in the worst case.

Keywords:

• Optimization problem
• Polygon enclosing points
• Minimum area polygon
• Isothetic polygon with reflex angles
• Line sweep paradigm
• Orthoconvex polygon

C.R. Categories::

• F.2.2[Analysis of Algorithms and Problem Complexity]
• I.3.5[Computational Geometry and Object Modeling]