Online Bichromatic Piercing Set Problem
摘要
We study a natural generalized version of the online piercing set problem: the online bichromatic piercing set problem. Here, we are given a set \(\mathcal {S}_r\) of red objects in advance. Blue objects from a set \(\mathcal {S}_b\) will be introduced one after another. We need to maintain a minimum cardinality piercing set for the arrived set of blue objects by making irreversible decisions with the constraint that none of the points in the piercing set should lie in the interior of any of the red objects in \(\mathcal {S}_r\) . When both \(\mathcal {S}_r\) and \(\mathcal {S}_b\) consist of unit disks, we propose an \(O(\log |\mathcal {S}_r|)\) -competitive deterministic algorithm for the problem and show that the competitive ratio of any deterministic or randomized online algorithm is \(\varOmega (\log |\mathcal {S}_r|)\) .