  Let $T$ be a tree space (or tree network) represented by a weighted tree with
$t$ vertices, and $S$ be a set of $n$ stochastic points in $T$, each of which
has a fixed location with an independent existence probability. We investigate
two fundamental problems under such a stochastic setting, the closest-pair
problem and the nearest-neighbor search. For the former, we study the
computation of the $\ell$-threshold probability and the expectation of the
closest-pair distance of a realization of $S$. We propose the first algorithm
to compute the $\ell$-threshold probability in $O(t+n\log n+ \min\{tn,n^2\})$
time for any given threshold $\ell$, which immediately results in an
$O(t+\min\{tn^3,n^4\})$-time algorithm for computing the expected closest-pair
distance. Based on this, we further show that one can compute a
$(1+\varepsilon)$-approximation for the expected closest-pair distance in
$O(t+\varepsilon^{-1}\min\{tn^2,n^3\})$ time, by arguing that the expected
closest-pair distance can be approximated via $O(\varepsilon^{-1}n)$ threshold
probability queries. For the latter, we study the $k$ most-likely
nearest-neighbor search ($k$-LNN) via a notion called $k$ most-likely Voronoi
Diagram ($k$-LVD). We show that the size of the $k$-LVD $\varPsi_T^S$ of $S$ on
$T$ is bounded by $O(kn)$ if the existence probabilities of the points in $S$
are constant-far from 0. Furthermore, we establish an $O(kn)$ average-case
upper bound for the size of $\varPsi_T^S$, by regarding the existence
probabilities as i.i.d. random variables drawn from some fixed distribution.
Our results imply the existence of an LVD data structure which answers $k$-LNN
queries in $O(\log n+k)$ time using average-case $O(t+k^2n)$ space, and
worst-case $O(t+kn^2)$ space if the existence probabilities are constant-far
from 0. Finally, we also give an $O(t+ n^2\log n+n^2k)$-time algorithm to
construct the LVD data structure.

Computational Geometry