Efficient algorithms find line centers for paired points in plane
Bichromatic Line-Centers for Point Pairs
Computational Geometry
Summary
This paper looks at a problem where you have pairs of points on a flat surface, and you want to divide each pair so one point is red and the other is blue. Then, for each color, you find the narrowest band that covers all its points. The goal is to make the widest of the two bands as small as possible. The authors provide fast methods to solve this problem in different scenarios, such as when lines have fixed directions or are free to rotate.
What this means in practice
- •For computer graphics developers: Compute efficient bounding regions for paired object features with color coding under orientation constraints.
- •For robotics path planners: Optimize path constraints when robot sensors detect paired landmarks assigned to different categories with directional preferences.
Authors
Jaegun Lee, Youjung Bae, Taehoon Ahn, Sang Won Bae, Hee-Kap Ahn
Abstract
We study the \emph{bichromatic line-center problem} for $n$ pairs of points in the plane. A feasible solution assigns one point from each pair to the red set $R$ and the other to the blue set $B$. The goal is to minimize $\max\{w^\circ(R),\,w^\circ(B)\}$, where $w^\circ(X)$ denotes the minimum width of a strip enclosing $X$; the midlines of the corresponding optimal strips define the line-centers of $R$ and $B$. 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 $O(n^2)$-time algorithm. For two line-centers, we obtain an $O(n)$-time algorithm when both are horizontal, and $Θ(n\log n)$-time algorithms when the two centers are parallel or when both orientations are prescribed. When exactly one orientation is prescribed, we give an $O(n^2)$-time algorithm. Finally, for the unrestricted case, we present an $O(n^3\log n)$-time algorithm.