On the Geometric Set Multicover Problem

Rajiv Raman, Saurabh Ray

Research output: Contribution to journalArticlepeer-review


In the Set Multicover problem, we are given a set system (X, S) , where X is a finite ground set, and S is a collection of subsets of X. Each element x∈ X has a non-negative demand d(x). The goal is to pick a smallest cardinality sub-collection S of S such that each point is covered by at least d(x) sets from S. In this paper, we study the set multicover problem for set systems defined by points and non-piercing regions in the plane, which includes disks, pseudodisks, k-admissible regions, squares, unit height rectangles, homothets of convex sets, upward paths on a tree, etc. We give a polynomial time (2 + ϵ) -approximation algorithm for the set multicover problem (P, R) , where P is a set of points with demands, and R is a set of non-piercing regions, as well as for the set multicover problem (D, P) , where D is a set of pseudodisks with demands, and P is a set of points in the plane, which is the hitting set problem with demands.

Original languageEnglish (US)
Pages (from-to)566-591
Number of pages26
JournalDiscrete and Computational Geometry
Issue number2
StatePublished - Sep 2022


  • Geometric hypergraphs
  • Local search
  • Packing and covering
  • Planar support
  • Pseudodisks

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics


Dive into the research topics of 'On the Geometric Set Multicover Problem'. Together they form a unique fingerprint.

Cite this