# The Efficient Processing of Moving \(k\)-Farthest Neighbor Queries in Road Networks +
## 4 Clustering Facilities and Computing Distances
### Computing Distances between a Facility Cluster and a Border Point of the Query Segment
The distance from \(v_{1}\) to \(f_{4}\) (\(f_{5}\)) is \(d(v_{1},f_{4})=12\) (\(d(v_{1},f_{5})=8\)) because the shortest path from \(v_{1}\) to \(f_{4}\) (\(f_{5}\)) is \(v_{1}\to v_{2}\to f_{5}\to f_{4}\) (\(v_{1}\to v_{2}\to f_{5}\)). Imagine a point \(f\) in \(\overline{f_{4}f_{5}}\). The distance from \(v_{1}\) to \(f\) is computed as \(d(v_{1},f)=min\{d(v_{1},f_{4})+len(\overline{f_{4}f}),d(v_{1},f_{5})+len( \overline{f_{5}f})\}\)\(=min\{12+len(\overline{f_{4}f}),8+len(\overline{f_{5}f})\}\); therefore, the largest and smallest distances from \(v_{1}\) to \(\overline{f_{4}f_{5}}\) are calculated as \(d_{max}(v_{1},\overline{f_{4}f_{5}})=12\) and \(d_{min}(v_{1},\overline{f_{4}f_{5}})=8\), respectively (Figure 7a). The same method in Figure 6 can be used to compute the largest and smallest distances from \(v_{1}\) to \(\overline{f_{5}f_{6}}\) (Figure 7b). The detailed procedure for the largest and smallest distance computation from \(v_{1}\) to \(\overline{f_{5}f_{6}}\) is omitted for simplicity. The shortest path from \(v_{1}\) to \(f_{5}\) (\(f_{6}\)) is \(v_{1}\to v_{2}\to f_{5}\) (\(v_{1}\to v_{2}\to f_{5}\to f_{6}\)), and the distance from \(v_{1}\) to \(f_{5}\) (\(f_{6}\)) is \(d(v_{1},f_{5})=8\) (\(d(v_{1},f_{6})=11\)). Therefore, the largest and smallest distances between \(v_{1}\) and \(\{\overline{f_{4}f_{5}},\overline{f_{5}f_{6}}\}\) are computed as \(d_{max}(v_{1},\{\overline{f_{4}f_{5}},\overline{f_{5}f_{6}}\})\)\(=12\) and \(d_{min}(v_{1},\{\overline{f_{4}f_{5}},\overline{f_{5}f_{6}}\})\)\(=8\), respectively. Figure 8 demonstrates the \(d_{max}(v_{2},\overline{f_{1}f_{2}f_{3}})\) computation. Note that the shortest path from \(v_{2}\) to \(f_{1}\) (\(f_{3}\)) is \(v_{2}\to v_{4}\to v_{3}\to f_{1}\) (\(v_{2}\to v_{4}\to v_{5}\to f_{3}\)), and the distance from \(v_{2}\) to \(f_{1}\) (\(f_{3}\)) is \(d(v_{2},f_{1})=17\) (\(d(v_{2},f_{3})=16\)). The same method in Figure 6 can be used to compute the largest and smallest distances from \(v_{2}\) to \(\overline{f_{1}f_{2}f_{3}}\) (Figure 8). The detailed procedure for computing the largest and smallest distances from \(v_{2}\) to \(\overline{f_{1}f_{2}f_{3}}\) is omitted for simplicity. The largest and smallest distances between \(v_{2}\) and \(\overline{f_{1}f_{2}f_{3}}\) are \(d_{max}(v_{2},\overline{f_{1}f_{2}f_{3}})=19\) and \(d_{min}(v_{2},\overline{f_{1}f_{2}f_{3}})\)\(=16\), respectively. The star sign (\(\bigstar\)) in Figure 8 is used to signify \(d_{max}(v_{2},\overline{f_{1}f_{2}f_{3}})\)\(=19\). Figure 9 presents the \(d_{max}(v_{2},\{\overline{f_{4}f_{5}},\overline{f_{5}f_{6}}\})\) computation. The largest distance between \(v_{2}\) and \(\{\overline{f_{4}f_{5}},\overline{f_{5}f_{6}}\}\) is evaluated as \(d_{max}(v_{2},\{\overline{f_{4}f_{5}},\overline{f_{5}f_{6}}\})=max\{d_{max}(v_ {2},\overline{f_{4}f_{5}})\), \(d_{max}(v_{2},\overline{f_{5}f_{6}})\}\). Figures 9a,b depict the \(d_{max}(v_{2},\overline{f_{4}f_{5}})\) and \(d_{max}(v_{2},\overline{f_{5}f_{6}})\) computations, respectively. The distance from \(v_{2}\) to \(f_{4}\) (\(f_{5}\)) is \(v_{2}\to f_{5}\to f_{4}\) (\(v_{2}\to f_{5}\)). The same method in Figure 6 can be used to compute the largest and smallest distances from \(v_{2}\) to \(\overline{f_{4}f_{5}}\) (Figure 9a). Thus, the largest and smallest distances from \(v_{2}\) to \(\overline{f_{4}f_{5}}\) are \(d_{max}(v_{2},\overline{f_{4}f_{5}})=7\) and \(d_{min}(v_{2},\overline{f_{4}f_{5}})=3\), respectively. The detailed procedure for computing the largest and smallest distances from \(v_{2}\) to \(\overline{f_{4}f_{5}}\) is omitted for simplicity. The distance from \(v_{2}\) to \(f_{5}\) (\(f_{6}\)) is \(d(v_{2},f_{5})=3\) (\(d(v_{2},f_{6})=6\)) because the shortest path from \(v_{2}\) to \(f_{5}\) (\(f_{6}\)) is \(v_{2}\to f_{5}\) (\(v_{2}\to f_{5}\to f_{6}\)). The same method in Figure 6 can be used to compute the largest and smallest distances from \(v_{2}\) to \(\overline{f_{5}f_{6}}\) (Figure 9b).