Online Hitting Sets for Disks of Bounded Radii

Minati De; Satyam Singh; Csaba D. Tóth

doi:10.4230/LIPIcs.ESA.2025.50

Online Hitting Sets for Disks of Bounded Radii

Minati De^*
, Satyam Singh^*
, Csaba D. Tóth^*

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Conference article in proceedings › Scientific › peer-review

2 Downloads (Pure)

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.

Original language	English
Title of host publication	33rd Annual European Symposium on Algorithms, ESA 2025
Editors	Anne Benoit, Haim Kaplan, Sebastian Wild, Sebastian Wild, Grzegorz Herman
Publisher	Schloss Dagstuhl - Leibniz-Zentrum für Informatik
Pages	1-16
Number of pages	16
ISBN (Electronic)	978-3-95977-395-9
DOIs	https://doi.org/10.4230/LIPIcs.ESA.2025.50
Publication status	Published - 1 Oct 2025
MoE publication type	A4 Conference publication
Event	European Symposium on Algorithms - Warsaw, Poland Duration: 15 Sept 2025 → 17 Sept 2025 Conference number: 33

Publication series

Name	Leibniz International Proceedings in Informatics, LIPIcs
Publisher	Schloss Dagstuhl - Leibniz-Zentrum für Informatik
Volume	351
ISSN (Electronic)	1868-8969

Conference

Conference	European Symposium on Algorithms
Abbreviated title	ESA
Country/Territory	Poland
City	Warsaw
Period	15/09/2025 → 17/09/2025

Funding

Minati De: Research on this paper was supported by SERB MATRICS Grant MTR/2021/ 000584. Satyam Singh: Research on this paper was supported by the Research Council of Finland, Grant 363444. Csaba D. Tóth: Research on this paper was supported, in part, by the NSF award DMS-2154347.

Keywords

Disks
Geometric Hitting Set
Homothets
Online Algorithm

Access to Document

10.4230/LIPIcs.ESA.2025.50

Online_Hitting_Sets_for_Disks_of_Bounded_RadiiFinal published version, 1.24 MBLicence: CC BY

Cite this

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 (pp. 1-16). Article 50 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 351). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ESA.2025.50

@inproceedings{510e2fbc47344ac788d08db29083e0a7,

title = "Online Hitting Sets for Disks of Bounded Radii",

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.",

keywords = "Disks, Geometric Hitting Set, Homothets, Online Algorithm",

author = "Minati De and Satyam Singh and T{\'o}th, \{Csaba D.\}",

note = "Publisher Copyright: {\textcopyright} Minati De, Satyam Singh, and Csaba D. T{\'o}th;; European Symposium on Algorithms, ESA ; Conference date: 15-09-2025 Through 17-09-2025",

year = "2025",

month = oct,

day = "1",

doi = "10.4230/LIPIcs.ESA.2025.50",

language = "English",

series = "Leibniz International Proceedings in Informatics, LIPIcs",

publisher = "Schloss Dagstuhl - Leibniz-Zentrum f{\"u}r Informatik",

pages = "1--16",

editor = "Anne Benoit and Haim Kaplan and Sebastian Wild and Sebastian Wild and Grzegorz Herman",

booktitle = "33rd Annual European Symposium on Algorithms, ESA 2025",

address = "Germany",

}

De, M, Singh, S & Tóth, CD 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

Online Hitting Sets for Disks of Bounded Radii. / De, Minati; Singh, Satyam; Tóth, Csaba D.
33rd Annual European Symposium on Algorithms, ESA 2025. ed. / Anne Benoit; Haim Kaplan; Sebastian Wild; Sebastian Wild; Grzegorz Herman. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025. p. 1-16 50 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 351).

Research output: Chapter in Book/Report/Conference proceeding › Conference article in proceedings › Scientific › peer-review

TY - GEN

T1 - Online Hitting Sets for Disks of Bounded Radii

AU - De, Minati

AU - Singh, Satyam

AU - Tóth, Csaba D.

N1 - Conference code: 33

PY - 2025/10/1

Y1 - 2025/10/1

N2 - 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.

AB - 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.

KW - Disks

KW - Geometric Hitting Set

KW - Homothets

KW - Online Algorithm

UR - https://www.scopus.com/pages/publications/105019048201

U2 - 10.4230/LIPIcs.ESA.2025.50

DO - 10.4230/LIPIcs.ESA.2025.50

M3 - Conference article in proceedings

AN - SCOPUS:105019048201

T3 - Leibniz International Proceedings in Informatics, LIPIcs

SP - 1

EP - 16

BT - 33rd Annual European Symposium on Algorithms, ESA 2025

A2 - Benoit, Anne

A2 - Kaplan, Haim

A2 - Wild, Sebastian

A2 - Herman, Grzegorz

PB - Schloss Dagstuhl - Leibniz-Zentrum für Informatik

T2 - European Symposium on Algorithms

Y2 - 15 September 2025 through 17 September 2025

ER -

Online Hitting Sets for Disks of Bounded Radii

Abstract

Publication series

Conference

Funding

Keywords

Access to Document

Other files and links

Fingerprint

AlgoHyper/ Kisfaludi-Bak: Algorithms in Hyperbolic Geometry

Cite this

Online Hitting Sets for Disks of Bounded Radii

Abstract

Publication series

Conference

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Projects

AlgoHyper/ Kisfaludi-Bak: Algorithms in Hyperbolic Geometry

Cite this