Fast Matching Algorithms for Points on a Polygon (extended abstract)

Given a set of 2n points on the boundary of a polygon, consider the complete graph induced by these points. The edges are assigned weights equal to the Euclidean distance between their endpoints if the endpoints see each other in the polygon, and +cm otherwise. We obtain the following results for finding a minimum-weight perfect matching in this graph: an O(n1ogn) time algorithm if the polygon is convex, and an O(n log' n) time algorithm if the polygon is simple but nonconvex. We also solve the assignment problem for a convex polygon in time O(nlogn), and obtain O(na(n)) and O(na(n) log n) time bounds for the verification problem on convex and nonconvex polygons, respectively, where a(n) is the functional inverse of Ackermann's function.