## 3 DTSPN Intersecting Regions Algorithm
### Performance Comparison  
The Intersecting Regions Algorithm (IRA) proposed here is similar to the Resolution Complete Method (RCM) proposed in [15] with the key exception that we use the fact that visiting one of the samples in the intersection of multiple regions achieves the goal of visiting all the regions in the intersection. Figure 5 illustrate this key difference. The RCM requires mutually exclusive node sets for the conversion from DTSPN to a GTSP with disjoint node sets. To meet this requirement, samples are assigned directly to the node set of the region from whose boundary they are drawn, as depicted in Figure 5(b). If multiple regions overlap and a sample lies in the intersection, IRA assigns this sample to all the node sets corresponding to the intersecting regions, as depicted in Figure 5(a), while RCM does not. The IRA then uses this additional information in the optimization.  
**Theorem 3.4** (IRA Performance).: _Given \(\rho>0\), the set of \(n\geq 2\) possibly intersecting regions, \(\mathcal{R}\), and the set of \(m\) sample configurations, \(\mathcal{S}\), let \(T_{IRA}\) and \(T_{RCM}\) denote the tours produced by IRA and the RCM [15], respectively. Then the length of \(T_{IRA}\) is no greater than that of \(T_{RCM}\),_  
\[\mathrm{length}(T_{IRA})\leq\mathrm{length}(T_{RCM}) \tag{7}\]  
Proof.: [Proof of Theorem 3.4] Let \(T=\{S_{1},S_{2},\ldots,S_{n}\}\) be a feasible tour, and note that both IRA and RCM minimize the tour length plus an additive constant while ensuring that all regions are visited. The difference is that IRA may produce tours visiting fewer than \(n\) unique samples, should some samples lie in the multiple regions. In particular, the IRA ensures that each leg of the tour enters at least one new region, by construction. Therefore, in performing the optimization IRA will either consider T, or subset of T, in which samples at the end of legs not entering an unvisited region have been removed. Due to  
Figure 4: Example of Problem (P5) and Problem (P6) from Stage 3 of transformation. (**a**) Problem (P5): The clustered TSP is created by forming zero cost intra-set cycles and adjusting the originating node in each inter-set arc; (**b**) Problem (P6): A large finite cost \(\beta\) is added to each inter-set edge. Here \(\bar{c}_{i,j}=c^{6}_{i,j}\), where \(c^{6}_{i,j}\) is defined in Equation (5). The optimal tour is shown in red with a cost of \(\hat{c}_{8,2}+\beta+\hat{c}_{2,8}\).  
the Dubins distance function satisfying the triangle inequality [20], a tour that visits a redundant sample will be longer than a tour that visits a subset of the samples. The optimal tour \(T_{IRA}\) cannot be longer than \(T_{RCM}\), because both optimize over the same set of feasible tours except for the tours in which IRA bypasses these unneeded samples.  
The property _resolution complete method_ as used in [15], dictates that the method converges to a solution at least as good as any nonisolated optimum solution as the number of sample configurations goes to infinity.  
**Corollary 3.5** (IRA is Resolution Complete).: _Given \(\rho>0\), the set of \(n\geq 2\) possibly intersecting regions, \(\mathcal{R}\), and the set of \(m\) sample configurations, \(\mathcal{S}\) drawn from a Halton quasi-random sequence[21] as in RCM, then IRA is Resolution Complete._  
Proof.: [Proof of Corollary 3.5] From [15], the RCM is a resolution complete method and converges as the number of samples goes to infinity, and from Theorem 3.4, we have shown that for the same set of sample configurations IRA will produce a tour that is no longer than RCM.