Guarding monotone art galleries with sliding cameras in linear time

M.T. Berg, de, S. Durocher, S. Mehrabi

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

5 Citations (Scopus)

Abstract

A sliding camera in an orthogonal polygon P is a point guard g that travels back and forth along an orthogonal line segment s inside P. A point p in P is guarded by g if and only if there exists a point q on s such that line segment pq is normal to s and contained in P. In the minimum sliding cameras (MSC) problem, the objective is to guard P with the minimum number of sliding cameras. We give a linear-time dynamic programming algorithm for the MSC problem on x-monotone orthogonal polygons, improving the 2-approximation algorithm of Katz and Morgenstern (2011). More generally, our algorithm can be used to solve the MSC problem in linear time on simple orthogonal polygons P for which the dual graph induced by the vertical decomposition of P is a path. Our results provide the first polynomial-time exact algorithms for the MSC problem on a non-trivial subclass of orthogonal polygons.
Original languageEnglish
Title of host publicationCombinatorial Optimization and Applications (8th International Conference, COCOA 2014, Wailea, Maui, HI, USA, December 19-21, 2014. Proceedings)
EditorsZ. Zhang, L. Wu, W. Xu, D.Z. Du
PublisherSpringer
Pages113-125
ISBN (Print)978-3-319-12690-6
DOIs
Publication statusPublished - 2014
Event8th International Conference on Combinatorial Optimization and Applications (COCOA 2014) - Mailea, Maui, United States
Duration: 19 Dec 201421 Dec 2014
Conference number: 8

Publication series

NameLecture Notes in Computer Science
Volume8881
ISSN (Print)0302-9743

Conference

Conference8th International Conference on Combinatorial Optimization and Applications (COCOA 2014)
Abbreviated titleCOCOA 2014
CountryUnited States
CityMailea, Maui
Period19/12/1421/12/14

Fingerprint Dive into the research topics of 'Guarding monotone art galleries with sliding cameras in linear time'. Together they form a unique fingerprint.

Cite this