Fast matching algorithms for points on a polygon

The complete graph induced by a set of 2n points on the boundary of a polygon is considered. The edges are assigned weights equal to the Euclidean distance between their endpoints if the endpoints see each other in the polygon, and +∞ otherwise. An O(n log n)-time algorithm is obtained for finding a minimum-weight perfect matching in this graph if the polygon is convex, and an O(n log²n)-time algorithm if the polygon is simple but nonconvex. The assignment problem for a convex polygon is solved in time O(n log n ), and O(nα(n)) and O(nα(n) log n) time bounds are obtained for the verification problem on convex and nonconvex polygons, respectively, where α(n) is the functional inverse of the Ackermann function