Name
Abstract | ||
|---|---|---|
Let P be a set of 2n points in the plane, and let MC (resp., MNC) denote a bottleneck matching (resp., a bottleneck non-crossing matching) of P. We study the problem of computing MNC. We present an O(n1.5log0.5n)-time algorithm that computes a non-crossing matching M of P, such that $bn(M) \le 2\sqrt{10} \cdot bn(M_{\rm NC})$, where bn(M) is the length of a longest edge in M. An interesting implication of our construction is that $bn(M_{\rm NC})/bn(M_{\rm C}) \le 2\sqrt{10}$. We also show that when the points of P are in convex position, one can compute MNC in O(n3) time. (In the full version of this paper, we also prove that the problem is NP-hard and does not admit a PTAS.) |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1016/j.comgeo.2013.10.005 | Computational Geometry: Theory and Applications |
Keywords | DocType | Volume |
bottleneck matching,time algorithm,approximation algorithms | Conference | 47 |
Issue | ISSN | Citations |
3 | 0925-7721 | 3 |
PageRank | References | Authors |
0.56 | 14 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| A. Karim Abu-Affash | 1 | 37 | 7.94 |
| Paz Carmi | 2 | 321 | 43.14 |
| Matthew J. Katz | 3 | 225 | 19.92 |
| Yohai Trabelsi | 4 | 3 | 0.56 |