Geometric set cover problem

The geometric set cover problem is the special case of the set cover problem in geometric settings. The input is a range space ℝd and X and geometric shapes such as disks and axis-parallel rectangles. The goal is to select a minimum-size subset 𝒞.

Given the same range space ℛ has nonempty intersection with X contains points on the real line and

The greedy algorithm for the general set cover problem gives O(log⁡𝖮𝖯𝖳)-approximate set cover/hitting set for a range space O(log⁡log⁡𝖮𝖯𝖳) or ℝ2, respectively.

Based on the iterative-reweighting technique of Clarkson and Brönnimann and Goodrich, Agarwal and Pan gave algorithms that computes an approximate set cover/hitting set of a geometric range space in O(nlog3nlog⁡log⁡log⁡𝖮𝖯𝖳) time for range spaces induced by 2D axis-parallel rectangles; and it computes an Feige, Uriel (1998), "A threshold of ln n for approximating set cover", Journal of the ACM, 45 (4): 634–652, CiteSeerX 10.1.1.70.5014, doi:10.1145/285055.285059, S2CID 52827488{{citation}}: Cite uses deprecated parameter |citeseerx= (help)

↑ Clarkson, Kenneth L. (1993-08-11). "Algorithms for polytope covering and approximation". In Dehne, Frank; Sack, Jörg-Rüdiger; Santoro, Nicola; et al. (eds.). Algorithms and Data Structures. Lecture Notes in Computer Science. Vol. 709. Springer Berlin Heidelberg. pp. 246–252. doi:10.1007/3-540-57155-8_252. ISBN 978-3-540-57155-1.