پیوندهای مفید
اخبار و اعلانات
آمار
| تعداد نشریات | 158 |
| تعداد شماره‌ها | 6,240 |
| تعداد مقالات | 67,871 |
| تعداد مشاهده مقاله | 115,426,993 |
| تعداد دریافت فایل اصل مقاله | 90,196,090 |
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 | ||
|
آمار تعداد مشاهده مقاله: 97 تعداد دریافت فایل اصل مقاله: 53 |
||