Online bichromatic piercing set problem

DOI10.1007/978-3-031-92935-9_17MaRDI QIDQ6902102zbMATH OpenFDO

Authors Minati De, Ratnadip Mandal

Publication date 11 November 2025

Full work available at URL https://doi.org/10.1007/978-3-031-92935-9_17

zbMATH Keywords

bichromatic objectscompetitive ratioonline algorithmpiercing setrandomized lower boundunit disk

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cites work

• A constant-factor approximation algorithm for red-blue set cover with unit disks
• A randomized algorithm for online unit clustering
• Approximating hitting sets of axis-parallel rectangles intersecting a monotone curve
• Fast stabbing of boxes in high dimensions
• Incremental Clustering and Dynamic Information Retrieval
• Independent and hitting sets of rectangles intersecting a diagonal line: algorithms and complexity
• Maintenance of a piercing set for intervals with applications
• On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles
• Online class cover problem
• Online geometric covering and piercing
• Online unit clustering and unit covering in higher dimensions
• Online unit covering in Euclidean space
• Optimal packing and covering in the plane are NP-complete
• Piercing translates and homothets of a convex body
• Polynomial-time approximation schemes for packing and piercing fat objects

Cited in

(1)

• Online geometric hitting set using points in \(\mathbb{Z}^d\)

This page was built for publication: Online bichromatic piercing set problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6902102)