Minimum area polygons with two reflex angles enclosing k points

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 O((n-k)2n2 + nr n log n) time, where nr could be O(n-k)3 in the worst case. The algorithm for the non-orthoconvex polygon has a complexity of O((n-k)2n2 + nr n log n) where nr could be O((n-k)5n) in the worst case. © 2001 OPA (Overseas Publishers Association) N.V. Published by license under the Gordon and Breach Science Publishers imprint.