Safety zone problem

Given a simple polygon P, its safety mne S (of width delta) is a closed region 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 distance 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 polygon. 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.