make unit disk graph given set of points

Slide 36 Extra nodes in a fixed partition P(a) Each boundary point of D* may be charged 6 times Each boundary point of D is used once. Each vertex can appear in the boundary area of at most 4(h+1) partitions. Slide 35 Shifting Shifting the partition with distance 1. Therefore, each node can be charged at most 6 times. Each component makes at most 2 charges to a node. Slide 32 Multiple Charges charge How many possible charges for each Boundary node? How many components can each node be adjacent to? Slide 33 How many independent points can be packed in a half disk with radius 1? 1 >1 3 Slide 34 Each node can be charged at most 6 times!!! Each node can connect to at most 3 components. Rule 2: In each component, charge to the point just outside the central area. Slide 31 Charge the extra vertices to a boundary point charging Charged to Rule 1: Each component Is charged at most twice. Use Charging Method to count the extra from (1). components of D* that are in the same component of G. For an MCDS D*, modify it as follows: (1) In each central area, connect all conn. Then computing S(x) takes time n 1 + n 2 + + n k 1 components that are in the same component of G.

Suppose n points are distributed into k cells containing n 1,, n k points, respectively. S(x) is the union of those minimum covers. Minimum cover can be computed In time n i O(a ) 2 Slide 5 Solution S(x) associated with P(x) For each cell, construct minimum cover. Then there are n i (n i -1) possible positions for each disk. Hence, each cell can be covered By at most disks. Slide 3 (x,x) Partition P(x) a Partition as a restriction Slide 4 Construct Minimum Unit Disk Cover in Each Cell 1/2 Each square with edge length 1/2 can be covered by a unit disk. Covering and Dominating Slide 2 Unit Disk Covering Given a set of n points in the Euclidean plane, find the minimum number of unit disks to cover the n given points.

Make unit disk graph given set of points