Bottleneck Non-Crossing Matching in the Plane

Details Bottleneck Non-Crossing Matching in the Plane Bottleneck Non-Crossing Matching in the Plane

2012-02-19

arxiv.org/abs/1202.4146v1

Computer Science

Computational Geometry

17 pages, 13 figures

Scientific paper

Let $P$ be a set of $2n$ points in the plane, and let $M_{\rm C}$ (resp., $M_{\rm NC}$) denote a bottleneck matching (resp., a bottleneck non-crossing matching) of $P$. We study the problem of computing $M_{\rm NC}$. We first prove that the problem is NP-hard and does not admit a PTAS. Then, we present an $O(n^{1.5}\log^{0.5} n)$-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}$.

Affiliated with

Also associated with

No associations

Rating

Bottleneck Non-Crossing Matching in the Plane does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Bottleneck Non-Crossing Matching in the Plane, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Bottleneck Non-Crossing Matching in the Plane will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-419427