Bottleneck Segment Matching
Aritra Banik, Matthew J. Katz, Marina Simakov · Canadian Conference on Computational Geometry · 2015
Let R be a set of n red segments and B a set of n blue segments, we wish to nd the minimum value d , such that there exists a perfect matching between R and B with bottleneck d , i.e., the maximum distance between a matched red-blue pair is d . We rst solve the corresponding decision problem: Given R, B and a distance d > 0, nd a maximum matching between R and B with bottleneck at most d. We begin with the simpler case where d = 0 and then extend our solution to the case where d > 0. We focus on the settings for which we are able to solve the decision problem eciently, i.e., in roughly O(n 1:5 ) time. The most general of these, is when one of the sets consists of disjoint arbitrary segments and the other of vertical segments. We apply similar ideas to nd a matching in the setting in which the vertical segments are replaced by points in the plane. After solving the decision problem, we explain how to nd the minimum value d . Finally, we show how to compute a shortest path tree for a given set of n orthogonal segments and a designated root segment in O(n log 2 n) time.