تعداد نشریات | 158 |
تعداد شمارهها | 6,241 |
تعداد مقالات | 67,871 |
تعداد مشاهده مقاله | 115,467,788 |
تعداد دریافت فایل اصل مقاله | 90,238,112 |
Plane Bounded-Degree Spanners Among the Obstacles for the Points in Convex Position | ||
Journal of Algorithms and Computation | ||
مقالات آماده انتشار، پذیرفته شده، انتشار آنلاین از تاریخ 25 دی 1400 اصل مقاله (301.57 K) | ||
نوع مقاله: Research Paper | ||
شناسه دیجیتال (DOI): 10.22059/jac.2022.85498 | ||
چکیده | ||
Let $S$ be a set of points in the plane that are in convex position. Let~$\cal O$ be a set of simple polygonal obstacles whose vertices are in $S$. The visibility graph $Vis(S,{\cal O})$ is the graph which is obtained from the complete graph of $S$ by removing all edges intersecting some obstacle of $\cal O$. In this paper, we show that there is a plane $5.19$-spanner of the visibility graph $Vis(S,{\cal O})$ of degree at most 6. Moreover, we show that there is a plane $1.88$-spanner of the visibility graph $Vis(S,{\cal O})$. These improve the stretch factor and the maximum degree of the previous results by A. van Renssen and G. Wong ({\em Theoretical Computer Science, 2021}) in the context of points in convex position. | ||
کلیدواژهها | ||
Plane spanner؛ Stretch factor؛ Shortest path؛ Computational Geometry | ||
آمار تعداد مشاهده مقاله: 98 تعداد دریافت فایل اصل مقاله: 53 |