Helsinki CS Theory Seminar: Satyam Singh

CS Theory Seminar, Helsinki CS Theory Seminar
The seminar is a weekly series of talks on a broad scope of CS theory hosted by Helsinki Algorithms and Theory.

When

–

Where

Onsite
AS3, Maarintie 8

Event language(s)

English

Speaker: Satyam Singh

Date:15 October 2025

Time:14:15
 

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 𝑃 of 𝑛 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, 𝑀], we present an 𝑂 (log 𝑀 log 𝑛)-competitive algorithm. This result generalizes from disks to positive homothets of any convex body in the plane with scaling factors in the interval [1, 𝑀 ]. 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 𝑁 > 1, we present an 𝑂 (log 𝑁 )-competitive algorithm for the variant where 𝑃 is a subset of an 𝑁 × 𝑁 section of the integer lattice, and the geometric objects are bottomless rectangles.

More Information about the Helsinki CS Theory Seminar is available on the event website

  • Updated:
  • Published:
Share
URL copied!