Guarding simple polygons with semi-open edge guards

Asish Mukhopadhyay, Chris Drouillard, Godfried Toussaint

Research output: Contribution to conferencePaperpeer-review

Abstract

In this note we explore an upper bound on the number of semi-open guard edges in a non star-shaped polygon and provide a characterization to detect semi-open guard edges. Based on this characterization we propose an O(n) time algorithm to find all semi-open guard edges in a polygon.

Original languageEnglish (US)
Pages417-422
Number of pages6
StatePublished - 2013
Event3rd International Conference on Digital Information Processing and Communications, ICDIPC 2013 - Dubai, United Arab Emirates
Duration: Jan 30 2013Feb 1 2013

Other

Other3rd International Conference on Digital Information Processing and Communications, ICDIPC 2013
CountryUnited Arab Emirates
CityDubai
Period1/30/132/1/13

Keywords

  • Art-gallery problems
  • Edge guards
  • Geometric algorithms
  • Visibility

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Information Systems
  • Signal Processing

Fingerprint Dive into the research topics of 'Guarding simple polygons with semi-open edge guards'. Together they form a unique fingerprint.

Cite this