Given an orthogonal polygon P, let |Π(P)| be the number of rectangles that result when we partition P by extending the edges incident to reflex vertices towards INT(P). In [4] we have shown that |Π(P)| ≤ 1+r+r2, where r is the number of reflex vertices of P. We shall now give sharper bounds both for maxp|Π(P)| and minp|Π(P)|. Moreover, we characterize the structure of orthogonal polygons in general position for which these new bounds are exact. We also present bounds on the area of grid n-ogons and characterize those having the largest and the smallest area.
4 September 2009 in Journal of Mathematical Sciences
We address the problem of stationing guards in vertices of a simple polygon in such a way that the whole polygon is guarded and the number of guards is minimum. This problem is NP-hard with relevant practical applications. In this paper we propose three metaheuristic approaches to this problem. Combined with the genetic algorithms strategy, which was proposed, these four approximation algorithms have been implemented and compared. The experimental evaluation from the hybrid strategy shows significant improvement in the number of guards compared to theoretical bounds.