Fixed k-watchman routes under the Min-Max criterion in staircase polygons | ||
| AUT Journal of Mathematics and Computing | ||
| مقاله 1، دوره 7، شماره 3، پاییز 2026، صفحه 271-282 اصل مقاله (535.78 K) | ||
| نوع مقاله: Original Article | ||
| شناسه دیجیتال (DOI): 10.22060/ajmc.2024.23104.1228 | ||
| نویسندگان | ||
| Rahmat Ghasemi1؛ Alireza Bagheri* 2؛ Fatemeh Keshavarz-Kohjerdi3؛ Faezeh Farivar1 | ||
| 1Department of Computer Engineering, SR.C., Islamic Azad University, Tehran, Iran | ||
| 2Department of Computer Engineering, Amirkabir University of Technology (Tehran Polytechnic), Tehran, Iran | ||
| 3Department 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 along the route taken by one of the watchmen. A greedy algorithm is presented for the min-max criterion, where we minimize the maximum route length. We assume some starting points of the watchmen may dominate the others. This algorithm finds an optimal solution in $O(n^2 \cdot k^2 \cdot \log{n})$ time, where $n$ represents the number of vertices of the give polygon, and $k$ represents the number of watchmen. | ||
| کلیدواژهها | ||
| Multiple watchman routes؛ Orthogonal polygon؛ Staircase polygon؛ Min-Max criterion؛ Fixed watchman route | ||
| مراجع | ||
|
| ||
|
آمار تعداد مشاهده مقاله: 733 تعداد دریافت فایل اصل مقاله: 4 |
||
| تعداد نشریات | 9 |
| تعداد شمارهها | 459 |
| تعداد مقالات | 5,790 |
| تعداد مشاهده مقاله | 8,570,904 |
| تعداد دریافت فایل اصل مقاله | 7,100,415 |