Given a point set $S\subset \mathbb{R}^d$, the $\theta$-graph of $S$ is as follows: for each point $s\in 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^2\alpha(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.
Iranfar,B and Farshi,M . (2020). On the expected weight of the theta graph on uncertain points. Journal of Algorithms and Computation, 52(1), 163-174. doi: 10.22059/jac.2020.76684
MLA
Iranfar,B , and Farshi,M . "On the expected weight of the theta graph on uncertain points", Journal of Algorithms and Computation, 52, 1, 2020, 163-174. doi: 10.22059/jac.2020.76684
HARVARD
Iranfar B, Farshi M. (2020). 'On the expected weight of the theta graph on uncertain points', Journal of Algorithms and Computation, 52(1), pp. 163-174. doi: 10.22059/jac.2020.76684
CHICAGO
B Iranfar and M Farshi, "On the expected weight of the theta graph on uncertain points," Journal of Algorithms and Computation, 52 1 (2020): 163-174, doi: 10.22059/jac.2020.76684
VANCOUVER
Iranfar B, Farshi M. On the expected weight of the theta graph on uncertain points. J. Algo. Comp.. 2020;52(1):163-174. doi: 10.22059/jac.2020.76684
