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., 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
Behnam Iranfar; Mohammad 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
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
VANCOUVER
Iranfar, B., Farshi, M. On the expected weight of the theta graph on uncertain points. Journal of Algorithms and Computation, 2020; 52(1): 163-174. doi: 10.22059/jac.2020.76684