On the expected weight of the theta graph on uncertain points

Given a point set $Ssubset mathbb{R}^d$, the $theta$-graph of $S$ is as follows: for each point $sin S$, draw cones with apex at $s$ and angle $theta$ %fix a line through $p$ at each cone and connect $s$ to the point in each cone such that the projection of the point on the bisector of the cone is the closest to~$s$. One can define the $theta$- graph on an uncertain point set, i.e. a point set where each point $s_i$ exists with an independent probability $pi_i in (0,1]$. In this paper, we propose an algorithm that computes the expected weight of the $theta$-graph on a given uncertain point set. The proposed algorithm takes $O(n^2alpha(n^2,n)^{2d})$ time and $O(n^2)$ space, where $n$ is the number of points, $d$ and $theta$ are constants, and $alpha$ is the inverse of the Ackermann's function.