In the online hitting set problem, sets arrive one at a time and the algorithm must maintain a collection of elements that hits every set seen so far. For general set systems, the best competitive ratio is O(log n · log m) where n is the number of elements and m the number of sets. The question: can geometric structure help?
Bhore, Gupta, and Kumar break through the double-logarithmic barrier. For weighted set systems with linear shallow-cell complexity — a structural property satisfied by most natural geometric families including halfplanes, disks, and fat objects — they achieve O(log n · log log n). The second logarithmic factor drops from log m to log log n.
The improvement exploits the shallow-cell property: in geometric systems, not too many cells of the arrangement are “shallow” (hit by few elements). This structural regularity allows the algorithm to make more informed decisions about which elements to add, avoiding the worst-case scenarios that force the extra logarithmic factor in general systems.
The result also provides the first bounds for weighted online hitting set on natural geometric families, resolving open questions about the gap between general and geometric versions of the problem. The unweighted case was understood; the weighted case required new techniques because the interplay between element costs and geometric structure creates complications absent from the unweighted setting.
A factor of log m replaced by log log n. The gap between general and geometric online optimization, measured precisely for the first time.