An Algorithm for Determining the Medial Axis of an Arbitrary Simple Polygon

Two algorithms are presented for determining the medial axes of a convex polygon and an arbitrary simple polygon. Its basic idea is to use the locus of the points, which are equidistant from two or three sides of a polygon. Both the algorithms can be constructed in O(n) time. They are better than Lee's(1982) and Aggarwal's algorithms(1989). They have the same orders of time complexity as the algorithm presented by Chin et al(1999), but their methods are quite different, and the obtained results are different, either. The algorithms obtain the trees of straight segments, it is beneficial to applications.