# 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 largest and smallest distances between a facility cluster \(\overline{F_{C}}\) and a border point \(q_{b}\) of the query segment \(\overline{q_{s}q_{e}}\) are computed, where \(q_{b}\in\{q_{s},q_{e}\}\). The smallest and largest distances between \(\overline{F_{C}}\) and \(q_{b}\) are represented by \(d_{min}(q_{b},\overline{F_{C}})=min\{d(q_{b},\,f)\,|\,f\in\overline{F_{C}}\}\) and \(d_{max}(q_{b},\overline{F_{C}})=max\{d(q_{b},\,f)\,|\,f\in\overline{F_{C}}\}\), respectively. The smallest distance between \(q_{b}\) and \(\overline{F_{C}}\) is evaluated as \(d_{min}(q_{b},\overline{F_{C}})=min\{d(q_{b},\,f_{b})|f_{b}\in\overline{B( \overline{F_{C}})}\}\), where \(f_{b}\) is a border point of \(\overline{F_{C}}\). However, the largest distance between \(q_{b}\) and \(\overline{F_{C}}\) is evaluated as \(d_{max}(q_{b},\overline{F_{C}})=max\{d_{max}(q_{b},\overline{f_{b}f_{m}})\,| \,\overline{f_{b}f_{m}}\in\overline{F_{C}}\}\), where \(\overline{f_{b}f_{m}}\) is a facility segment in \(\overline{F_{C}}\), and \(d_{max}(q_{b},\overline{f_{b}f_{m}})\) is the largest distance between \(q_{b}\) and \(\overline{f_{b}f_{m}}\). The largest and smallest distances between a facility cluster \(\overline{F_{C}}\) and a border point \(q_{b}\) of the query segment are computed using the example in Figure 5, where \(q_{b}\)\(\in\)\(\{v_{1},v_{2}\}\) and \(\overline{F}\)\(=\)\(\{\overline{f_{1}f_{2}f_{3}}\},\{\overline{f_{4}f_{5}},\overline{f_{5}f_{6}}\}\). Figures 6-9 illustrate the computations of \(d_{max}(v_{1},\{\overline{f_{1}f_{2}f_{3}}\})\), \(d_{max}(v_{1},\{\overline{f_{4}f_{5}},\overline{f_{5}f_{6}}\})\), \(d_{max}(v_{2},\{\overline{f_{1}f_{2}f_{3}}\})\), and \(d_{max}(v_{2},\{\overline{f_{4}f_{5}},\overline{f_{5}f_{6}}\})\), respectively. Figure 6 depicts the computation of \(d_{max}(v_{1},\overline{f_{1}f_{2}f_{3}})\). The distances from \(v_{1}\) to endpoints \(f_{1}\) and \(f_{3}\) of \(\overline{f_{1}f_{2}f_{3}}\) are \(d(v_{1},f_{1})=21\) and \(d(v_{1},f_{3})=21\), respectively, because the path from \(v_{1}\) to \(f_{1}\) (\(f_{3}\)) is \(v_{1}\to v_{3}\to f_{1}\) (\(v_{1}\to v_{2}\to v_{4}\to v_{5}\to f_{3}\)). Imagine a point \(f\) in \(\overline{f_{1}f_{2}f_{3}}\). The distance from \(v_{1}\) to \(f\) is then evaluated to \(d(v_{1},f)=min\{d(v_{1},f_{1})+len(\overline{f_{1}f}),d(v_{1},f_{3})+len( \overline{f_{3}f})\}=min\{21+len(\overline{f_{1}f}),21+len(\overline{f_{3}f})\}\) because the path from \(v_{1}\) to \(f\) should be \(v_{1}\to f_{1}\to f\) or \(v_{1}\to f_{3}\to f\). Let \(x=len(\overline{f_{1}f})\). Accordingly, \(len(\overline{f_{3}f})=5-x\) because \(len(\overline{f_{1}f})+len(\overline{f_{3}f})=5\). The distance from \(v_{1}\) to \(f\) can be represented as \(d(v_{1},f)=min\{21+x,21+(5-x)\}\) for \(0\leq x\leq 5\). As shown in Figure 6,  
Figure 5: Clustering method for grouping facilities into facility clusters: (**a**) grouping facilities into facility segments; (**b**) grouping facility segments into facility clusters. the largest and smallest distances from \(v_{1}\) to \(\overline{f_{1}f_{2}f_{3}}\) are evaluated as \(d_{max}(v_{1},\overline{f_{1}f_{2}f_{3}})=23.5\) and \(d_{min}(v_{1},\overline{f_{1}f_{2}f_{3}})=21\), respectively. The star sign (\(\bigstar\)) in Figure 6 is used to signify \(d_{max}(v_{1},\overline{f_{1}f_{2}f_{3}})=23.5\). Figure 7 illustrates the \(d_{max}(v_{1},\{\overline{f_{4}f_{5}},\overline{f_{5}f_{6}}\})\) computation. Naturally, the largest distance between \(v_{1}\) and \(\{\overline{f_{4}f_{5}},\overline{f_{5}f_{6}}\}\) is evaluated as \(d_{max}(v_{1},\{\overline{f_{4}f_{5}},\overline{f_{5}f_{6}}\})=max\{d_{max}(v_ {1},\overline{f_{4}f_{5}}),\)\(d_{max}(v_{1},\overline{f_{5}f_{6}}\})\). Figures 7a,b present the \(d_{max}(v_{1},\overline{f_{4}f_{5}})\) and \(d_{max}(v_{1},\overline{f_{5}f_{6}})\) computations, respectively.