機動車安全技術(shù)檢驗機構(gòu)檢驗

1、Chapter 4 Partition(1) ShiftingDing-Zhu Du汽車防盜器 zg001gps.Disk CoveringGiven a set of n points in the Euclidean plane, find the minimum number of unit disks to cover the n given points.(x,x)Partition P(x)a.Construct Minimum Unit Disk Cover in Each Cell1/2Each square with edge length1/2 can be covered

2、 by a unitdisk.Hence, each cell can be coveredBy at most disks. Suppose a cell contains ni points.Then there are ni(ni-1) possiblepositions for each disk.Minimum cover can be computed In time niO(a )2.Solution S(x) associated with P(x)For each cell, construct minimum cover.S(x) is the union of those

3、 minimum covers.Suppose n points are distributed into k cells containing n1, , nk points, respectively.Then computing S(x) takes timen1 + n2 + + nk nO(a )O(a )O(a )O(a )2222.Approximation AlgorithmFor x=0, -2, , -(a-2), compute S(x).Choose minimum one from S(0), S(-2), , S(-a+2).AnalysisConsider a m

4、inimum cover.Modify it to satisfy the restriction, i.e., a union of disk covers each for a cell. To do such a modification, we need to add some disks and estimate how many added disks. .Added DisksCount twiceCount four times2.2Shifting.Estimate # of added disksShifting.Estimate # of added disksVerti

5、cal stripsEach disk appearsonce.Estimate # of added disksHorizontal stripsEach disk appears once.Estimate # of added disks# of added disks for P(0)+ # of added disks for P(-2)+ + # of added disks for P(-a+2) 3 opt where opt is # of disk in a minimum cover.There is a x such that # of added disks for

6、P(x) (6/a) opt.Performance RatioP.R. 1 + 6/a 1 + when we choose a = 6 1/ .Running time is n.O(1/ )2.Unit disk graph15!.Each node can be charged at most 10 times!.Shifting3a/(2(h+1) = integerTime=nO(a )2h=2.Weighted Dominating SetGiven a unit disk graph with vertex weight, find a dominating set with

7、minimum total weight.Can the partition technique be used for the weighted dominating set problem?.Dominating Set in Intersection Disk GraphAn intersection disk graph is given by a set of points (vertices) in the Euclidean plane, each associated with a disk and an edge exists between two points iff two disks associated with