Bichromatic Line-Centers for Point Pairs
In the authors' words
We study the bichromatic line-center problem for pairs of points in the plane. A feasible solution assigns one point from each pair to the red set and the other to the blue set . The goal is to minimize , where denotes the minimum width of a strip enclosing ; the midlines of the corresponding optimal strips define the line-centers of and . We consider several variants induced by orientational constraints on line-centers and provide efficient algorithms for each. For one line-center, which consists of computing a minimum-width strip that contains at least one point from each pair, we give an -time algorithm. For two line-centers, we obtain an -time algorithm when both are horizontal, and -time algorithms when the two centers are parallel or when both orientations are prescribed. When exactly one orientation is prescribed, we give an -time algorithm. Finally, for the unrestricted case, we present an -time algorithm.
Appeared: Tuesday, September 22. arXiv. Preprint, not yet peer-reviewed.