Fast Matching Algorithms for Points on a Polygon
Odile Marcotte, Subhash Suri · SIAM Journal on Computing · 1991
Given a set P of $2n$ points on the boundary of a polygon, consider the complete graph whose vertex set is P, and whose edges are assigned weights equal to the Euclidean distance between their endpoints if the endpoints see each other in the polygon and $ + \infty $ otherwise. The problem of finding a minimum-weightperfect matching is investigated in this graph, and an $O(n\log (n))$ time algorithm is obtained if the polygon is convex; an $O(n\log ^2 (n))$ time algorithm is obtained if the polygon is simple but not convex. Similar results are obtained for the assignment problem and the maximum-weight problem.