Győri, Ervin and Mezei, Tamás Róbert (2019) Mobile vs. point guards. DISCRETE AND COMPUTATIONAL GEOMETRY. pp. 1-33. ISSN 0179-5376 (nyomtatott); 1432-0444 (online)
|
Text
mobile-vs-point-guards.pdf Download (204kB) | Preview |
Abstract
We study the problem of guarding orthogonal art galleries with horizontal mobile guards (alternatively, vertical) and point guards, using “rectangular vision”. We prove a sharp bound on the minimum number of point guards required to cover the gallery in terms of the minimum number of vertical mobile guards and the minimum number of horizontal mobile guards required to cover the gallery. Furthermore, we show that the latter two numbers can be computed in linear time.
| Item Type: | Article |
|---|---|
| Subjects: | Q Science / természettudomány > QA Mathematics / matematika |
| SWORD Depositor: | MTMT SWORD |
| Depositing User: | MTMT SWORD |
| Date Deposited: | 29 Apr 2019 11:13 |
| Last Modified: | 29 Apr 2019 11:13 |
| URI: | http://real.mtak.hu/id/eprint/93097 |
Actions (login required)
 |
Edit Item |
