Safety zone problem

Given a simple polygon P, its safety mne S (of width delta) is a closed reg ion consisting of straight line segments and circular arcs (of radius delta ) bounding the polygon P such that there exists no pair of points p ton the boundary of P) and q ton the boundary of S) having their Euclidean distanc e d(p, q) less than delta. In this paper we present a linear time algorithm for finding the minimum area safety zone of an arbitrarily shaped simple p olygon. It is also shown that our proposed method can easily be modified to compute the Minkowski sum of a simple polygon and a convex polygon in O(MN ) time, where M and N are the number of vertices of both the polygons. (C) 2000 Academic Press.