I have a finite set of $n$ points $V \subset \mathbb{R}^d$. To each of these point, let say $x$, it is associated a set $N(x)\subset V\setminus \{x\}$ of cardinality $k<n$. Given $z\in \mathbb{R}^d$, I would like to know $\text{argmin}_{y \in N(x)}d(z,y)$, where $d$ is the euclidean distance.
What I want to do is to effectively check this distances only if I can not exclude $y$ a-priori through triangular inequality: $$d(x,z)\leq d(x,y)+d(y,z) \ \implies \ d(y,z) \geq d(x,z)-d(x,y) \, ,$$ so, if I've already computed a distance $d(z,y^{\prime})$ for another $y^{\prime} \in N(x)$ and I have $d(x,z)-d(x,y)\geq d(z,y^{\prime})$, then I know for sure that $d(y,z)\geq d(z,y^{\prime})$ and I don't need to compute that distance.
Now my question is: taken $x\in V$ what is the expected number of distances between $z$ and elements in $N(x)$ i need to compute? I would like to have an exact value or an upper bound for it (not the trivial one with $\leq|N(x)|$). In this process I assume a fixed order for the elements of $N(x)=(y_1,\dots,y_k)$, so that I can refer to "already known distances".
This is my attempt:
For $y\in N(x)$ define I(y) = 1 if $d(z,y)$ is checked and $I(y)=0$ otherwise. Then $C(x):=\sum_{y\in N(x)} I(y)$ represents the number of checked distances for $x$ and its expected value is: \begin{align*} \mathbb{E}[C(x)]&=\sum_{y \in N(x)} \mathbb{E}[I(y)] = \sum_{y \in N(x)} \mathbb{P}(I(y)=1) = \sum_{y \in N(x)} 1-\mathbb{P}(I(y)=0) \\ &= k- \sum_{i=1}^k \mathbb{P}\Bigl(\exists j<i \, | \, d(x,z)-d(x,y_i)\geq d(z,y_j)\Bigr) \leq \ ???\end{align*}
Is my approach correct? How can I complete it or, eventually, is there another possible approach which leads to a solution?