Safety Zone Problem

✍ Scribed by Subhas C. Nandy; Bhargab B. Bhattacharya; Antonio Hernández-Barrera

• Book ID: 102573633
• Publisher: Elsevier Science
• Year: 2000
• Tongue: English
• Weight: 228 KB
• Volume: 37
• Category: Article
• ISSN: 0196-6774
• DOI: 10.1006/jagm.2000.1092

✦ Synopsis

Given a simple polygon P, its safety zone S of width ␦ is a closed region Ž . consisting of straight line segments and circular arcs of radius ␦ bounding the Ž . polygon P such that there exists no pair of points p on the boundary of P and q Ž . Ž . on the boundary of S having their Euclidean distance d p, q less than ␦. 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.