Guarding monotone art galleries with sliding cameras in linear time

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

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

5 Citaten (Scopus)

Samenvatting

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.
Originele taal-2Engels
TitelCombinatorial Optimization and Applications (8th International Conference, COCOA 2014, Wailea, Maui, HI, USA, December 19-21, 2014. Proceedings)
RedacteurenZ. Zhang, L. Wu, W. Xu, D.Z. Du
UitgeverijSpringer
Pagina's113-125
ISBN van geprinte versie978-3-319-12690-6
DOI's
StatusGepubliceerd - 2014
Evenement8th International Conference on Combinatorial Optimization and Applications (COCOA 2014) - Mailea, Maui, Verenigde Staten van Amerika
Duur: 19 dec 201421 dec 2014
Congresnummer: 8

Publicatie series

NaamLecture Notes in Computer Science
Volume8881
ISSN van geprinte versie0302-9743

Congres

Congres8th International Conference on Combinatorial Optimization and Applications (COCOA 2014)
Verkorte titelCOCOA 2014
LandVerenigde Staten van Amerika
StadMailea, Maui
Periode19/12/1421/12/14
Ander8th International Conference on Combinatorial Optimization and Applications

Vingerafdruk Duik in de onderzoeksthema's van 'Guarding monotone art galleries with sliding cameras in linear time'. Samen vormen ze een unieke vingerafdruk.

Citeer dit