A note on guarding staircase polygons

Matt Gibson , Erik Krohn , Bengt J. Nilsson , Matthew Rayford , Paweł Żyliński

Abstract

We exhibit two linear time approximation algorithms for guarding rectilinear staircase polygons both having approximation factor 2. The first algorithm benefits from its simplicity, where as the second provides more insight to the problem.
Document typepaper presented
Author Matt Gibson
Matt Gibson,,
-
, Erik Krohn
Erik Krohn,,
-
, Bengt J. Nilsson
Bengt J. Nilsson,,
-
, Matthew Rayford
Matthew Rayford,,
-
, Paweł Żyliński (FMPI / II)
Paweł Żyliński,,
- Institute of Informatics
Languageen angielski
Issue year2019
Pages105-109
URL https://sites.ualberta.ca/~cccg2019/cccg2019_proceedings.pdf
Score (nominal)0
Conference31st Canadian Conference on Computational Geometry (CCCG 2019), 08-08-2019 - 10-08-2019, Edmonton, Kanada
Citation count*
Share Share

Get link to the record

Back