## 3 Theory: A Lower Bound Construction
### Lower Bounding the Direct Search Space  
Let us now assume that the contraction hierarchy has been created with an _arbitrary_ contraction order. We will show that no matter what this contraction order is, the average size of the direct search space is \(\Omega(\sqrt{n})\). In our analysis, we only consider shortest path trees rooted in the top right quarter of the grid (there are \(n/4\) of them). For these shortest path trees, their lower left part always contains a subtree of size \(\Theta(n)\) as depicted in Figure 5.  
The idea of the analysis is to identify pairs \((x,v)\) such that \(v\in DSS(x)\). We will consider each of the shortest path trees rooted at \(s\) in the top right quarter and for each identify \(\Theta(\sqrt{n})\) such pairs (not necessarily with \(x=s\)). The main challenge will be to make sure that no double counting of pairs occurs when considering all these shortest path trees. Figure 4: Shortest path tree from red source. Let us focus on one shortest path tree rooted at \(s\) and the subtree of the lower left part as shown in Figure 6. By construction, we have \(\Theta(\sqrt{n})\) vertical branches in this subtree. Figure 5: Relevant lower left parts of shortest path trees rooted in top right quarter. Figure 6: Subtree in the lower left of a shortest path tree and charging argument. Consider one branch, spawning at its corner node \(c\). Furthermore, let \(s^{\prime}\) be the node in the branch which has the same distance to \(c\) as \(c\) to \(s\). One can think of \(s\) being mirrored at \(c\), see Figure 6. Let \(w\) be the highest-level node on the shortest path from \(s\) to \(s^{\prime}\). There are two cases: (a) \(w\) lies on the vertical branch including \(c\) (this is depicted as \(w_{1}\) in Figure 6). (b) \(w\) lies on the horizontal part of the shortest path from \(s\) to \(s^{\prime}\) excluding \(c\) (this is depicted as \(w_{2}\) in the Figure). In case (a) we generate \((s,w_{1})\) since obviously \(w_{1}\in DSS(s)\). In case (b), we cannot simply generate \((s,w_{2})\) as the same pair might be identified when considering other branches in the shortest path tree from \(s\) leading to double counting. However, we also know that \(w_{2}\) lies in the direct search space of \(s^{\prime}_{2}\). Intuitively, we charge \(s^{\prime}_{2}\) by generating the pair \((s^{\prime}_{2},w_{2})\). Therefore, when considering the shortest path tree of a node \(s\), we generate exactly one pair \((x,v)\) for each of the \(\Theta(\sqrt{n})\) vertical branches to the lower left. Let us first show that we did not double count in this process. **Lemma 2**. : _No pair \((x,v)\) is generated more than once._  
Proof. : Consider a pair \((s,v)\) that was generated according to case (a), i.e., \(s\) lies to the upper right or the right of \(v\). Clearly, the same pair cannot be generated according to case (a) again, as the vertical branch in which \(v\) resides is only considered once from source \(s\). However, it also cannot be generated according to case (b), as these pairs have always \(s\) to the lower left of \(v\). A pair \((s,v)\) generated according to case (b) has \(s\) to the lower left of \(v\), thus cannot be generated by case (a) as these pairs have \(s\) to the upper right or right of \(v\). As \((s,v)\) was generated according to case (b), it was generated when inspecting the shortest path tree from a source \(s^{\prime}\) which is the node \(s\) mirrored at the corner vertex of the shortest path from \(s\) to \(v\). However, this source \(s^{\prime}\) is uniquely determined, so \((s,v)\) can only be generated when the shortest path tree rooted at \(s^{\prime}\) with the vertical branch containing \(v\) was considered. Now, we are ready to prove the first main result of this paper. **Theorem 1**. : _The average direct search space of \(G_{lh}\) is \(\Omega(\sqrt{n})\)._  
Proof. : In our process, we considered \(n/4\) shortest path trees, in each of which we identified \(\Omega(\sqrt{n})\) pairs \((x,v)\) where \(v\in DSS(x)\) and no pair appears twice.