a hitting set of size $k$ on the set system $(\mathcal{U}, \mathcal{S})$, then there is a dominating set of size at most $k$ on $G$.

\[prf:lem:ifMHSthenMDS\] Suppose that $M'$ is a hitting set of size $k$ for the set system $(\mathcal{U}, \mathcal{S})$. For each hitting element $e\in M'$: add $P$ to $M$, where $P$ is the path for which $e$ is a supporting segment of ${\texttt{cross}}(P)$. Clearly, $\lvert M\rvert\leq k$. To see why $M$ is a dominating set for $G$, consider any path $P$ and let $S\in\mathcal{S}$ denote its corresponding set. Since $M'$ is a hitting set, there must be a hitting element $e'\in M'$ that intersects $S$. Let $P'$ be the path for which $e'$ is a supporting segment of ${\texttt{corner}}(P')$; notice that $P'\in M$. If $P'=P$, then we are done. Otherwise, $e'$ must hit the cross $c$ corresponding to $P$ since $c\in S$. This means that the cross corresponding to $P'$ intersects $c$ and so $P$ is intersected by $P$ by Observation \[obs:crossAndPath\].

#### Approximation using $\varepsilon$-nets.

An [*$\varepsilon$-net*]{} for a set system $\mathcal{R}=(\mathcal{U}, \mathcal{S})$ is a subset $N$ of $\mathcal{U}$ such that every set $S$ in $\mathcal{S}$ with size at least $\varepsilon\cdot\lvert\mathcal{U}\rvert$ has a non-empty intersection with 