2026-08-07T07:37:48Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:22132 2024-12-04T06:53:43Z ddc:004 open_access

Constrained Two-Line Center Problems Ahn, Taehoon Bae, Sang Won two-line center problem geometric location problem geometric optimization 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² log² n) 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³ n) time when the orientation of one line is fixed; and in O(n² α(n) log n) time when the angle between the two lines is fixed, where α(n) denotes the inverse Ackermann function. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Taehoon Ahn and Sang Won Bae 2024 Is Part Of LIPIcs, Volume 322, 35th International Symposium on Algorithms and Computation (ISAAC 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2024.5 urn:nbn:de:0030-drops-221327 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2024.5 eng https://creativecommons.org/licenses/by/4.0/legalcode