آمار

تعداد نشریات8
تعداد شماره‌ها430
تعداد مقالات5,589
تعداد مشاهده مقاله7,005,116
تعداد دریافت فایل اصل مقاله5,987,738
Ghasemi, Rahmat, Bagheri, Alireza, Keshavarz-Kohjerdi, Fatemeh, Farivar, Faezeh. (1403). Fixed $k$-watchman routes under the Min-Max criterion in staircase polygons. نشریه مهندسی عمران امیرکبیر, (), -. doi: 10.22060/ajmc.2024.23104.1228
Rahmat Ghasemi; Alireza Bagheri; Fatemeh Keshavarz-Kohjerdi; Faezeh Farivar. "Fixed $k$-watchman routes under the Min-Max criterion in staircase polygons". نشریه مهندسی عمران امیرکبیر, , , 1403, -. doi: 10.22060/ajmc.2024.23104.1228
Ghasemi, Rahmat, Bagheri, Alireza, Keshavarz-Kohjerdi, Fatemeh, Farivar, Faezeh. (1403). 'Fixed $k$-watchman routes under the Min-Max criterion in staircase polygons', نشریه مهندسی عمران امیرکبیر, (), pp. -. doi: 10.22060/ajmc.2024.23104.1228
Ghasemi, Rahmat, Bagheri, Alireza, Keshavarz-Kohjerdi, Fatemeh, Farivar, Faezeh. Fixed $k$-watchman routes under the Min-Max criterion in staircase polygons. نشریه مهندسی عمران امیرکبیر, 1403; (): -. doi: 10.22060/ajmc.2024.23104.1228

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 Ghasemi1؛ Alireza Bagheri* 2؛ Fatemeh Keshavarz-Kohjerdi3؛ Faezeh Farivar1
1Department of Computer and Mechatronics Engineering, Science and Research Branch, 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 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
آمار
تعداد مشاهده مقاله: 521


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