Fixed $k$-watchman routes under the Min-Max criterion in staircase polygons

Ghasemi, Rahmat; Bagheri, Alireza; Keshavarz-Kohjerdi, Fatemeh; Farivar, Faezeh

doi:10.22060/ajmc.2024.23104.1228

دانشگاه صنعتی امیرکبیر

تعداد نشریات	8
تعداد شماره‌ها	419
تعداد مقالات	5,514
تعداد مشاهده مقاله	6,250,952
تعداد دریافت فایل اصل مقاله	5,422,372

	Fixed $k$-watchman routes under the Min-Max criterion in staircase polygons
AUT Journal of Mathematics and Computing
مقالات آماده انتشار، پذیرفته شده، انتشار آنلاین از تاریخ 21 شهریور 1403
نوع مقاله: Original Article
شناسه دیجیتال (DOI): 10.22060/ajmc.2024.23104.1228
نویسندگان
Rahmat Ghasemi¹؛ Alireza Bagheri^* ²؛ Fatemeh Keshavarz-Kohjerdi³؛ Faezeh Farivar¹
¹Department of Computer and Mechatronics Engineering, Science and Research Branch, Islamic Azad University, Tehran, Iran
²Department of Computer Engineering, Amirkabir University of Technology (Tehran Polytechnic), Tehran, Iran
³Department of Computer Science, Shahed University, Tehran, Iran
چکیده
In this paper, the problem of multiple watchman routes in staircase polygons is studied. The watchman route problem (WRP) is a variation of the art gallery problem (AGP) in computational geometry, where each point in the given polygon must be visible from at least one point of a route of a watchman. A greedy algorithm is presented for the min-max criterion, where we minimize the maximum route length. We assume that the watchmen's starting points may dominate eachother. This algorithm finds an optimal solution in $O(n^2 \cdot k^2 \cdot \log{n})$ time, where $n$ is the number of vertices and $k$ is the number of watchmen.
کلیدواژه‌ها
Multiple watchman routes؛ Orthogonal polygon؛ Staircase polygon؛ Min-max criterion؛ Fixed watchman route

آمار تعداد مشاهده مقاله: 406

سامانه مدیریت نشریات علمی. طراحی و پیاده سازی از سیناوب

پیوندهای مفید

آمار

Fixed $k$-watchman routes under the Min-Max criterion in staircase polygons