REAL

Mobile vs. point guards

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)

[img]
Preview
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 Edit Item