2026-09-05T11:58:23Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25837 2026-06-23T12:59:17Z ddc:004 open_access

Linear-Time (1+ε)-Approximation Algorithms for Two-Line-Center Problems Chung, Chaeyoon Maheshwari, Anil Smid, Michiel Approximation algorithm two-line-center problem k-line-center problem projective clustering ε-certificate ε-coreset width of a point set Given a set S of n points in the plane, we study the two-line-center problem: finding two lines that minimize the maximum distance from each point in S to its closest line. We present a (1+ε)-approximation algorithm for the two-line-center problem that runs in O((n/ε) log (1/ε)) time, which improves the previously best O(nlog n + (n/ε²) log (1/ε) + (1/ε³)log (1/ε))-time algorithm. We also consider three variants of this problem, in which the orientations of the two lines are restricted: (1) the orientation of one of the two lines is fixed, (2) the orientations of both lines are fixed, and (3) the two lines are required to be parallel. For each of these three variants, we give the first (1+ε)-approximation algorithm that runs in linear time. In particular, for the variant where the orientation of one of the two lines is fixed, we also give an improved exact algorithm that runs in O(n log n) time and show that it is optimal. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Chaeyoon Chung and Anil Maheshwari and Michiel Smid 2026 Is Part Of LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2026.31 urn:nbn:de:0030-drops-258374 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.31 eng https://creativecommons.org/licenses/by/4.0/legalcode