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|)\) .

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Online Bichromatic Piercing Set Problem

  • Minati De,
  • Ratnadip Mandal

摘要

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|)\) .