## 2 Dominating Set
### Algorithm for Unit Disk Graphs  
Now we present a local algorithm for dominating set on unit disk graphs (UDGs) with locality one. Let \(G=(V,E)\) be a unit disk graph. The algorithm works as follows: In each hexagon \(h\) the vertex \(v\) which is closest to the center of \(h\) is assigned to the dominating set \(D\). Ambiguities are resolved by e.g., choosing the vertex with the smallest \(x\)-coordinate. We refer to this as Algorithm 1.  
We prove the correctness of Algorithm 1 in Theorem 1.  
**Theorem 1**.: _Let \(G\) be a unit disk graph. Algorithm 1 has the following properties:_  
1. _The computed set_ \(D\) _is a dominating set for_ \(G\)_._
2. _Let_ \(D_{OPT}\) _be an optimal dominating set. It holds that_ \(|D|\leq 12\cdot|D_{OPT}|\)_._
3. _Whether or not a vertex_ \(v\) _is in_ \(D\) _depends only on the vertices at most one hop away from_ \(v\)_, i.e. Algorithm_ 1 _is local._  
Figure 1: (a) A part of the tiling of the plane into hexagons. (b) One hexagon of the tiling. The bold lines indicate the parts of its border that belong to this hexagon.  
Iii-B4 The processing time for a vertex \(v\) is linear in the number of vertices adjacent to \(v\).  
Proof.: We first prove that \(D\) is indeed a dominating set for \(G\). Let \(h\) be a non-empty hexagon and denote by \(V_{h}\) all vertices in \(h\). As \(V_{h}\
eq\emptyset\) it holds that one vertex \(v\in V_{h}\) is the vertex which is closest to the center of \(h\). So \(v\in D\) and \(v\) dominates all vertices in \(h\).  
Now we prove that for an optimal dominating set \(D_{OPT}\) it holds that \(|D|\leq 12\cdot|D_{OPT}|\). In the following we prove that for any vertex in \(D_{OPT}\) there can exist at most 12 hexagons that have a vertex at (Euclidean) distance at most one from it. (In fact this holds for all vertices but we need the claim only for vertices in \(D_{OPT}\).) Consider a vertex \(v\in D_{OPT}\) in a hexagon \(h\). Without loss of generality we assume that \(v\) is in the gray area of \(h\) as shown in Figure 3 or in the center of \(h\) as shown in Figure 2. In both cases for a vertex \(v^{\prime}\in D\) that is adjacent to \(v\) it holds that \(v^{\prime}\) must be in one of the 9 or 12 hexagon in the respective figure (for the case of \(v\) being in the center of \(h\) check the resolving method for ambiguities at the border of hexagons, Figure 1b). Since at most one vertex per hexagon was assigned to \(D\) there are at most 12 vertices in \(D\) that are adjacent to \(v\). (Note that in the case where \(v\) is in the gray area the resolving method for ambiguities does not come into play.)  
So for each vertex \(v\in D_{OPT}\) it holds that it is adjacent to at most 12 vertices in \(D\). Since \(D_{OPT}\) is a dominating set all vertices in \(D\) must be adjacent to at least one vertex in \(D_{OPT}\). This leads to \(|D|\leq 12\cdot|D_{OPT}|\).  
Next we determine the locality of Algorithm 1. In the algorithm, a vertex \(v\) in a hexagon \(h\) only needs to explore all vertices which are at most one hop away from \(v\) in order to determine whether \(v\) is the vertex closest to the center of \(h\). So whether or not \(v\in D\) depends only on the vertices which are at most one hop away from \(v\).  
Figure 2: A vertex \(v\) in the center of hexagon \(h\) can only be adjacent to vertices in these 9 hexagons. Note that due to the resolving method for vertices at the border of hexagons, the vertices \(v^{\prime}\) and \(v^{\prime\prime}\) belong to the hexagons \(h^{\prime}\) and \(h^{\prime\prime}\) respectively (and are adjacent to \(v\)).  
Now we prove the processing time of Algorithm 1. Let \(v\) be a vertex and define \(n_{1}(v):=|N^{1}(v)|\). In the algorithm \(v\) needs to determine for each vertex \(v^{\prime}\in N^{1}(v)\) whether \(v^{\prime}\in h\) and whether \(v^{\prime}\) is closer to the center of \(h\) than \(v\). This can be done in \(O\left(n_{1}(v)\right)\) time.