Constrained Two-Line Center Problems
<|reference_start|>Constrained Two-Line Center Problems: Given a set P of n points in the plane, the two-line center problem asks to find two lines that minimize the maximum distance from each point in P to its closer one of the two resulting lines. The currently best algorithm for the problem takes $O(n^2\log^2n)$ time by Jaromczyk and Kowaluk in 1995. In this paper, we present faster algorithms for three variants of the two-line center problem in which the orientations of the resulting lines are constrained. Specifically, our algorithms solve the problem in $O(n \log n)$ time when the orientations of both lines are fixed; in $O(n \log^3 n)$ time when the orientation of one line is fixed; and in $O(n^2 \alpha(n) \log n)$ time when the angle between the two lines is fixed, where $\alpha(n)$ denotes the inverse Ackermann function.<|reference_end|>
@article{ahn2024constrained,
    title={Constrained Two-Line Center Problems},
    author={Taehoon Ahn and Sang Won Bae},
    journal={arXiv preprint arXiv:2409.13304},
    year={2024},
    archivePrefix={arXiv},
    eprint={2409.13304},
    primaryClass={cs.CG}
}