On the expected weight of the theta graph on uncertain points

	On the expected weight of the theta graph on uncertain points
Journal of Algorithms and Computation
دوره 52، شماره 1، شهریور 2020، صفحه 163-174 اصل مقاله (378.76 K)
نوع مقاله: Research Paper
شناسه دیجیتال (DOI): 10.22059/jac.2020.76684
نویسندگان
Behnam Iranfar¹؛ Mohammad Farshi²
¹Department of Computer Science, Yazd University, Yazd, Iran
²Department of Mathematical Sciences, Yazd University, Yazd, Iran
چکیده
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.
کلیدواژه‌ها
uncertain points؛ expected weight

آمار تعداد مشاهده مقاله: 314 تعداد دریافت فایل اصل مقاله: 208

سامانه مدیریت نشریات علمی. قدرت گرفته از سیناوب