Structural properties of bichromatic non-crossing matchings

作者：

Highlights：

• The theory of orbits provides combinatorial properties for the structure of feasible edges of non-crossing matchings of bichromatic point sets in convex position.

• O(n2)-time algorithm for finding a bottleneck bichromatic non-crossing matching of points in convex position.

• O(n)-time algorithm for finding a bottleneck bichromatic non-crossing matching of points on a circle.

摘要

•The theory of orbits provides combinatorial properties for the structure of feasible edges of non-crossing matchings of bichromatic point sets in convex position.•O(n2)-time algorithm for finding a bottleneck bichromatic non-crossing matching of points in convex position.•O(n)-time algorithm for finding a bottleneck bichromatic non-crossing matching of points on a circle.

论文关键词：Orbit,Matching,Bottleneck,Non-crossing,Bichromatic,Convex,Circle

论文评审过程：Received 2 April 2021, Revised 23 September 2021, Accepted 25 September 2021, Available online 10 October 2021, Version of Record 10 October 2021.

论文官网地址：https://doi.org/10.1016/j.amc.2021.126695