ls11-www.cs.tu-dortmund.de/_media/buchin/teaching/akda_ws21/geometric-set-cover.pdf
space
1 2
3 4
5 6
7 8
red = {1, 2, 3, 4, 5, 7, 8} green = {1, 2, 7, 8}
blue = {2, 3, 5, 6}
orange = {1, 2, 3, 4, 7, 8} purple = {1, 2, 3, 4, 5, 6}
pink = {1, 2, 3, 4, 5, 6, 7}
X = {1, 2, 3, 4, 5, 6, 7, 8} [...] space
1 2
3 4
5 6
7 8
red = {1, 2, 3, 4, 5, 7, 8} green = {1, 2, 7, 8}
blue = {2, 3, 5, 6}
orange = {1, 2, 3, 4, 7, 8} purple = {1, 2, 3, 4, 5, 6}
pink = {1, 2, 3, 4, 5, 6, 7}
X = {1, 2, 3, 4, 5, 6, 7, 8} [...] ofRp 5. sample newR′ 6. returnR′
1 red = {1, 2, 3, 4, 5, 7, 8} 1 green = {1, 2, 7, 8} 1 orange = {1, 2, 3, 4, 7, 8}
6
8
2 3 1 4
5 7
W (r)
The algorithm
1 blue = {2, 3, 5, 6} 1 purple = {1, 2, 3, 4, 5, 6} …