Online Hitting Sets for Disks of Bounded Radii
Loading...
Access rights
openAccess
CC BY
CC BY
publishedVersion
URL
Journal Title
Journal ISSN
Volume Title
A4 Artikkeli konferenssijulkaisussa
This publication is imported from Aalto University research portal.
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Unless otherwise stated, all rights belong to the author. You may download, display and print this publication for Your own personal use. Commercial use is prohibited.
Authors
Date
Department
Major/Subject
Mcode
Degree programme
Language
en
Pages
16
Series
33rd Annual European Symposium on Algorithms, ESA 2025, pp. 1-16, Leibniz International Proceedings in Informatics, LIPIcs ; Volume 351
Abstract
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.Description
Publisher Copyright: © Minati De, Satyam Singh, and Csaba D. Tóth;
Keywords
Other note
Citation
De, M, Singh, S & Tóth, C D 2025, Online Hitting Sets for Disks of Bounded Radii. in A Benoit, H Kaplan, S Wild, S Wild & G Herman (eds), 33rd Annual European Symposium on Algorithms, ESA 2025., 50, Leibniz International Proceedings in Informatics, LIPIcs, vol. 351, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, pp. 1-16, European Symposium on Algorithms, Warsaw, Poland, 15/09/2025. https://doi.org/10.4230/LIPIcs.ESA.2025.50