---
_id: '4118'
abstract:
- lang: eng
  text: A rectilinear polygon can be viewed as an art gallery room whose walls meet
    at right angles. An algorithm is presented that stations guards in such a room
    so that every interior point is visible to some guard. The algorithm partitions
    the polygon into L-shaped pieces, a subclass of star-shaped pieces, and locates
    one guard within each kernel. The algorithm runs in O(n log n) time in the worst
    case for a polygon of n vertices.
article_processing_charge: No
article_type: original
author:
- first_name: Herbert
  full_name: Edelsbrunner, Herbert
  id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
  last_name: Edelsbrunner
  orcid: 0000-0002-9823-6833
- first_name: Joseph
  full_name: O'Rourke, Joseph
  last_name: O'Rourke
- first_name: Emo
  full_name: Welzl, Emo
  last_name: Welzl
citation:
  ama: Edelsbrunner H, O’Rourke J, Welzl E. Stationing guards in rectilinear art galleries.
    <i>Computer Vision, Graphics, and Image Processing</i>. 1984;27(2):167-176. doi:<a
    href="https://doi.org/10.1016/S0734-189X(84)80041-9">10.1016/S0734-189X(84)80041-9</a>
  apa: Edelsbrunner, H., O’Rourke, J., &#38; Welzl, E. (1984). Stationing guards in
    rectilinear art galleries. <i>Computer Vision, Graphics, and Image Processing</i>.
    Elsevier. <a href="https://doi.org/10.1016/S0734-189X(84)80041-9">https://doi.org/10.1016/S0734-189X(84)80041-9</a>
  chicago: Edelsbrunner, Herbert, Joseph O’Rourke, and Emo Welzl. “Stationing Guards
    in Rectilinear Art Galleries.” <i>Computer Vision, Graphics, and Image Processing</i>.
    Elsevier, 1984. <a href="https://doi.org/10.1016/S0734-189X(84)80041-9">https://doi.org/10.1016/S0734-189X(84)80041-9</a>.
  ieee: H. Edelsbrunner, J. O’Rourke, and E. Welzl, “Stationing guards in rectilinear
    art galleries,” <i>Computer Vision, Graphics, and Image Processing</i>, vol. 27,
    no. 2. Elsevier, pp. 167–176, 1984.
  ista: Edelsbrunner H, O’Rourke J, Welzl E. 1984. Stationing guards in rectilinear
    art galleries. Computer Vision, Graphics, and Image Processing. 27(2), 167–176.
  mla: Edelsbrunner, Herbert, et al. “Stationing Guards in Rectilinear Art Galleries.”
    <i>Computer Vision, Graphics, and Image Processing</i>, vol. 27, no. 2, Elsevier,
    1984, pp. 167–76, doi:<a href="https://doi.org/10.1016/S0734-189X(84)80041-9">10.1016/S0734-189X(84)80041-9</a>.
  short: H. Edelsbrunner, J. O’Rourke, E. Welzl, Computer Vision, Graphics, and Image
    Processing 27 (1984) 167–176.
date_created: 2018-12-11T12:07:02Z
date_published: 1984-08-01T00:00:00Z
date_updated: 2022-01-28T08:03:51Z
day: '01'
doi: 10.1016/S0734-189X(84)80041-9
extern: '1'
intvolume: '        27'
issue: '2'
language:
- iso: eng
month: '08'
oa_version: None
page: 167 - 176
publication: Computer Vision, Graphics, and Image Processing
publication_identifier:
  eissn:
  - 0734-189X
  issn:
  - 1557-895X
publication_status: published
publisher: Elsevier
publist_id: '2002'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Stationing guards in rectilinear art galleries
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 27
year: '1984'
...