پیوندهای مفید
اخبار و اعلانات
آمار
| تعداد نشریات | 158 |
| تعداد شماره‌ها | 6,232 |
| تعداد مقالات | 67,790 |
| تعداد مشاهده مقاله | 115,264,592 |
| تعداد دریافت فایل اصل مقاله | 90,006,494 |
Plane Bounded-Degree Spanners Among the Obstacles for the Points in Convex Position | ||
| Journal of Algorithms and Computation | ||
| دوره 53، شماره 2، اسفند 2021، صفحه 85-90 اصل مقاله (320.02 K) | ||
| نوع مقاله: Research Paper | ||
| شناسه دیجیتال (DOI): 10.22059/jac.2021.85252 | ||
| نویسنده | ||
| Davood Bakhshesh* | ||
| Department of Computer Science, University of Bojnord, Bojnord, Iran. | ||
| چکیده | ||
| 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 | ||
|
آمار تعداد مشاهده مقاله: 237 تعداد دریافت فایل اصل مقاله: 112 |
||