Fast Matching Algorithms for Points on a Polygon
Let \(P\) be a set of \(2n\) points on the boundary of a polygon in the Euclidean plane. Consider the complete graph on \(P\) with edge-weight equal to the Euclidean distance if two endpoints see each other and \(+\infty\) otherwise. The authors investigated the problem of finding the minimum weight perfect matching in this graph. They obtained an \(O(n\log n)\)-time algorithm if the polygon is convex and an \(O(n\log^ 2n)\)-time algorithm if the polygon is simple and not necessarily convex. Similar results were also obtained for the assignment problem and the maximum-weight problem.
- A maximum b-matching problem arising from median location models with applications to the roommates problem
- Perspectives of Monge properties in optimization
- Minimum cost b-matching problems with neighborhoods
- Two dimensional maximum weight matching using Manhattan topology
- Efficient many-to-Many point matching in one dimension
- Faster strongly polynomial algorithms for the unbalanced transportation problem and assignment problem with Monge costs
- Geometry Helps in Matching
- Bipartite graph matching for points on a line or a circle
- An EP Algorithm for Computing a Minimum Weight Perfect Matching for a Set of Points on the Plane
- An algorithm to find polygon similarity
- New variants of perfect non-crossing matchings
- Dynamic Euclidean bottleneck matching
- A generalized hypergreedy algorithm for weighted perfect matching
- An efficient parallel algorithm for finding minimum weight matching for points on a convex polygon
- New variants of perfect non-crossing matchings
This page was built for publication: Fast Matching Algorithms for Points on a Polygon
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3978776)
