## Appendix A Resampling Algorithms  
```
1:functionMultinomial_Ancestors(\(w\in[0,\infty)^{N}\))
2:\(W\leftarrow\text{InclusivePrefixSum}(w)\)
3:for\(i\gets 1\) to N do
4:\(u^{i}\sim U[0,W_{N})\)\(\triangleright\) Sample uniformly in range \([0,W_{N})\)
5:\(a^{i}\leftarrow\text{LowerBound}(W,u^{i})\)\(\triangleright\) Find lower bound index
6:endfor
7:return\(a\)
8:endfunction
```  
**Algorithm A1** Multinomial Ancestors  
```
1:functionStratified_Resampling(\(w\in[0,\infty)^{N}\))
2:\(N\leftarrow\text{count}(w)\)
3:\(W\leftarrow\text{InclusivePrefixSum}(w)\)
4:for\(n\gets 1\) to N do
5:\(u_{n}\sim U[0,1)\)\(\triangleright\) Sample uniformly in range \([0,1)\)
6:endfor
7:\(u_{i}\leftarrow\frac{i-1+u_{i}}{N}\) for \(i=1,\ldots,N\)
8:\(k\gets 1\)
9:for\(i\gets 1\) to N do
10:while\(W(k)<u(i)\)do
11:\(k\gets k+1\)
12:endwhile
13:\(a(i)\gets k\)
14:endfor
15:return\(a\)
16:endfunction
```  
**Algorithm A2** Stratified Resampling
```
1:functionSystematic_Resampling(\(w\in[0,\infty)^{N}\))
2:\(N\leftarrow\text{count}(w)\)
3:\(W\leftarrow\text{InclusivePrefixSum}(w)\)
4:\(u_{0}\sim U[0,1)\)\(\triangleright\) Sample uniformly in range \([0,1)\)
5:\(u\leftarrow\frac{u_{0}}{N}\)
6:\(k\gets 1\)
7:for\(i\gets 1\) to \(N\)do
8:while\(W(k)<u(i)\)do
9:\(k\gets k+1\)
10:endwhile
11:\(a(i)\gets k\)
12:endfor
13:return\(a\)
14:endfunction
```  
**Algorithm A3** Systematic Resampling  
```
1:functionMetropolisC1_Resampling(\(w\in[0,\infty)^{N}\))
2:\(N\leftarrow\text{count}(w)\)
3: Initialize \(a\) as an array of size \(N\)
4:for\(i\gets 1\) to \(N\)do
5:\(p\gets i\)
6:\(u\sim U[0,1)\)
7:\(u\sim U[0,1)\)
8:endwhile
10:\(a(i)\gets p\)
11:endfor
12:return\(a\)
13:endfunction
```  
**Algorithm A4** Rejection Resampling  
```
1:functionMetropolisC1_Resampling(\(w\in[0,\infty)^{N}\))
2:\(N\leftarrow\text{count}(w)\)
3:\(N\leftarrow\text{count}(w)\)
4:\(u\sim U[0,1)\)
5:endfor
6:return\(a\)
7:endfunction
```  
**Algorithm A5** Metropolis Resampling  
```
1:functionMetropolisC1_Resampling(\(w\in[0,\infty)^{N}\))
2:\(N\leftarrow\text{count}(w)\)
3:\(B\leftarrow\text{number of iterations}\)
4: Initialize \(a\) as an array of size \(N\)
5:for\(i\gets 1\) to \(N\)do
6:\(p\gets i\)
7:for\(j\gets 1\) to \(B\)do
8:\(u\sim U[0,1)\)\(\triangleright\) Sample uniformly in range \([0,1)\)
9:\(q\sim U\{1,\ldots N\}\)\(\triangleright\) Sample within segment
10:if\(u\leq\frac{w(q)}{w(p)}\)then
11:\(p\gets q\)
12:endif
13:endfor
14:\(a(i)\gets p\)
15:endfor
16:return\(a\)
17:endfunction
```  
**Algorithm A6** Metropolis Resampling  
```
1:functionMetropolisC1_Resampling(\(w\in[0,\infty)^{N}\))
2:\(N\leftarrow\text{count}(w)\)
3:\(N\leftarrow\text{count}(w)\)
4:\(u\sim U[0,1)\)
5:\(u\sim U[0,1)\)
6:\(u\sim U[0,1)\)
7:\(u\sim U[0,1)\)
8:endfor
9:return\(a\)
10:endfunction
```  
**Algorithm A7** Metropolis Resampling  
```
1:functionMetropolisC1_Resampling(\(w


```
1:functionMetropolisC1_Resampling(\(w\in[0,\infty)^{N}\))
2:\(N\leftarrow\text{count}(w)\)
3:\(B\leftarrow\text{number of iterations}\)
4:\(SC\leftarrow\text{number of segments}\)\(\triangleright\) Number of segments
5:\(DC\leftarrow\text{segment size}\)\(\triangleright\) Size of each segment
6:Initialize \(a\) as an array of size \(N\)
7:for\(i\gets 1\) to \(N\)do
8:\(p\gets i\)
9:\(s\sim U\{1,\dots,SC\}\)\(\triangleright\) Sample segment index
10:for\(j\gets 1\) to \(B\)do
11:\(u\sim U[0,1)\)\(\triangleright\) Sample uniformly in range \([0,1)\)
12:\(q\sim U\{(s-1)\times DC+1,s\times DC\}\)\(\triangleright\) Sample within segment
13:if\(u\leq\frac{w(q)}{w(p)}\)then
14:\(p\gets q\)
15:endif
16:endfor
17:\(a(i)\gets p\)
18:endfor
19:return\(a\)
20:endfunction
```
**Algorithm A6** MetropolisC1 Resampling
```
1:functionMetropolisC2_Resampling(\(w\in[0,\infty)^{N}\))
2:\(N\leftarrow\text{count}(w)\)
3:\(B\leftarrow\text{number of iterations}\)
4:\(SC\leftarrow\text{number of segments}\)\(\triangleright\) Number of segments
5:\(DC\leftarrow\text{segment size}\)\(\triangleright\) Size of each segment
6:Initialize \(a\) as an array of size \(N\)
7:for\(i\gets 1\) to \(N\)do
8:\(p\gets i\)
9:for\(j\gets 1\) to \(B\)do
10:\(u\sim U[0,1)\)\(\triangleright\) Sample uniformly in range \([0,1)\)
11:\(s\sim U\{1,\dots,SC\}\)\(\triangleright\) Sample segment index
12:\(q\sim U\{(s-1)\times DC+1,s\times DC\}\)\(\triangleright\) Sample within segment
13:if\(u\leq\frac{w(q)}{w(p)}\)then
14:\(p\gets q\)
15:endif
16:endfor
17:\(a(i)\gets p\)
18:endfor
19:return\(a\)
20:endfunction
```
**Algorithm A7** MetropolisC2 Resampling
```
1:for\(m=thread1d\) to \(N_{p}\), step = \(blockDim\cdot gridDim\)do
2:\(x_{1}^{m}=randU(x_{min},x_{max})\)
3:\(y_{1}^{m}=randU(y_{min},y_{max})\)
4:\(\theta_{1}^{m}=randU(\theta_{min},\theta_{max})\)
5:endfor
```
**Algorithm A8** Particle Initialization

### Particle Initialization
```
1:functionMetropolisC1_Resampling(\(w\in[0,\infty)^{N}\))
2:\(N\leftarrow\text{count}(w)\)
3:\(B\leftarrow\text{number of iterations}\)
4:\(SC\leftarrow\text{number of segments}\)\(\triangleright\) Number of segments
5:\(DC\leftarrow\text{segment size}\)\(\triangleright\) Size of each segment
6:Initialize \(a\) as an array of size \(N\)
7:for\(i\gets 1\) to \(N\)do
8:\(p\gets i\)
9:for\(j\gets 1\) to \(B\)do
10:\(u\sim U[0,1)\)\(\triangleright\) Sample uniformly in range \([0,1)\)
11:\(s\sim U\{1,\dots,SC\}\)\(\triangleright\) Sample segment index
12:\(q\sim U\{(s-1)\times DC+1,s\times DC\}\)\(\triangleright\) Sample within segment
13:if\(u\leq\frac{w(q)}{w(p)}\)then
14:\(p\gets q\)
15:endif
16:endfor
17:\(a(i)\gets p\)
18:endfor
19:return\(a\)
20:endfunction
```
**Algorithm A9** Particle Initialization

### Particle Prediction
```
1:for\(m=threadId\) to N\({}_{p}\), step = \(blockDim\cdot gridDim\)do
2:\(x_{1}^{m}=x_{t-1}^{m}+\delta_{s}\cdot\cos(\theta_{t-1}^{m}+\frac{\delta_{ \theta}}{2})\)
3:\(y_{1}^{m}=y_{t-1}^{m}+\delta_{s}\cdot\sin(\theta_{t-1}^{m}+\frac{\delta_{ \theta}}{2})\)
4:\(\theta_{t}^{m}=\theta_{t-1}^{m}+\delta_{\theta}\)
5:endfor
```
**Algorithm A9** Particle Prediction
```
1:for\(m=blockId\) to N\({}_{p}\), step = \(gridDim\)do
2:for\(n=threadId\) to N\({}_{I}\), step = \(blockDim\)do
3:\(dx=x_{1}^{m}-x_{2}^{m}\)\(\triangleright\) position of the landmark w.r.t.