Top Qs
Timeline
Chat
Perspective

Geometric set cover problem

From Wikipedia, the free encyclopedia

Remove ads
Remove ads

The geometric set cover problem is the special case of the set cover problem in geometric settings. The input is a range space where is a universe of points in and is a family of subsets of called ranges, defined by the intersection of and geometric shapes such as disks and axis-parallel rectangles. The goal is to select a minimum-size subset of ranges such that every point in the universe is covered by some range in .

Given the same range space , a closely related problem is the geometric hitting set problem, where the goal is to select a minimum-size subset of points such that every range of has nonempty intersection with , i.e., is hit by .

In the one-dimensional case, where contains points on the real line and is defined by intervals, both the geometric set cover and hitting set problems can be solved in polynomial time using a simple greedy algorithm. However, in higher dimensions, they are known to be NP-complete even for simple shapes, i.e., when is induced by unit disks or unit squares.[1] The discrete unit disc cover problem is a geometric version of the general set cover problem which is NP-hard.[2]

Many approximation algorithms have been devised for these problems. Due to the geometric nature, the approximation ratios for these problems can be much better than the general set cover/hitting set problems. Moreover, these approximate solutions can even be computed in near-linear time.[3]

Remove ads

Approximation algorithms

The greedy algorithm for the general set cover problem gives approximation, where . This approximation is known to be tight up to constant factor.[4] However, in geometric settings, better approximations can be obtained. Using a multiplicative weight algorithm,[5] Brönnimann and Goodrich[6] showed that an -approximate set cover/hitting set for a range space with constant VC-dimension can be computed in polynomial time, where denotes the size of the optimal solution. The approximation ratio can be further improved to or when is induced by axis-parallel rectangles or disks in , respectively.

Remove ads

Near-linear-time algorithms

Based on the iterative-reweighting technique of Clarkson[7] and Brönnimann and Goodrich,[6] Agarwal and Pan[3] gave algorithms that computes an approximate set cover/hitting set of a geometric range space in time. For example, their algorithms computes an -approximate hitting set in time for range spaces induced by 2D axis-parallel rectangles; and it computes an -approximate set cover in time for range spaces induced by 2D disks.

Remove ads

See also

References

Loading content...
Loading related searches...

Wikiwand - on

Seamless Wikipedia browsing. On steroids.

Remove ads