2026-07-21T11:08:49Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26052 2026-06-23T13:18:39Z ddc:004 open_access

Online Hitting Set for Axis-Aligned Squares De, Minati Singh, Satyam Tóth, Csaba D. axis-aligned squares hitting set homothets of a polygon online algorithm Given a set P of n points in the plane and a sequence of axis-aligned squares that arrive in an online fashion, the online hitting set problem consists of maintaining, by adding new points from P if necessary, a hitting set H ⊆ P, which contains at least one point in every input square that has already arrived. We present an O(log n)-competitive deterministic algorithm for this problem. The competitive ratio is the best possible, apart from constant factors. In fact, this is the first O(log n)-competitive algorithm for the online hitting set problem that works for geometric objects of arbitrary sizes (i.e., unbounded scaling factors) in the plane. We further generalize this result to positive homothets of a polygon with k ≥ 3 vertices in the plane and provide an O(k²log n)-competitive algorithm. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Minati De and Satyam Singh and Csaba D. Tóth 2026 Is Part Of LIPIcs, Volume 370, 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SWAT.2026.16 urn:nbn:de:0030-drops-260528 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2026.16 eng https://creativecommons.org/licenses/by/4.0/legalcode