Plane Bounded-Degree Spanners Among the Obstacles for the Points in Convex Position

	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

آمار تعداد مشاهده مقاله: 360 تعداد دریافت فایل اصل مقاله: 250

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