2026-07-20T14:51:08Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24518 2025-12-16T14:00:16Z ddc:004 open_access

Online Hitting Sets for Disks of Bounded Radii De, Minati Singh, Satyam Tóth, Csaba D. Geometric Hitting Set Online Algorithm Homothets Disks We present algorithms for the online minimum hitting set problem in geometric range spaces: Given a set P of n points in the plane and a sequence of geometric objects that arrive one-by-one, we need to maintain a hitting set at all times. For disks of radii in the interval [1,M], we present an O(log M log n)-competitive algorithm. This result generalizes from disks to positive homothets of any convex body in the plane with scaling factors in the interval [1,M]. As a main technical tool, we reduce the problem to the online hitting set problem for a finite subset of integer points and bottomless rectangles. Specifically, for a given N > 1, we present an O(log N)-competitive algorithm for the variant where P is a subset of an N× N section of the integer lattice, and the geometric objects are bottomless rectangles. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Minati De and Satyam Singh and Csaba D. Tóth 2025 Is Part Of LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2025.50 urn:nbn:de:0030-drops-245181 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.50 eng https://creativecommons.org/licenses/by/4.0/legalcode