Guarding galleries and terrains

Alon Efrat; Sariel Har-Peled

doi:10.1016/j.ipl.2006.05.014

Guarding galleries and terrains

Alon Efrat
, Sariel Har-Peled

Computer Science

Research output: Contribution to journal › Article › peer-review

80 Scopus citations

Abstract

Let P be a polygon with n vertices. We say that two points of P see each other if the line segment connecting them lies inside (the closure of) P. In this paper we present efficient approximation algorithms for finding the smallest set G of points of P so that each point of P is seen by at least one point of G, and the points of G are constrained to be belong to the set of vertices of an arbitrarily dense grind. We also present similar algorithms for terrains and polygons with holes.

Original language	English (US)
Pages (from-to)	238-245
Number of pages	8
Journal	Information Processing Letters
Volume	100
Issue number	6
DOIs	https://doi.org/10.1016/j.ipl.2006.05.014
State	Published - Dec 31 2006

ASJC Scopus subject areas

Theoretical Computer Science
Signal Processing
Information Systems
Computer Science Applications

Access to Document

10.1016/j.ipl.2006.05.014

Cite this

@article{d609a6bbc8a44049b3751c5df6c3e856,

title = "Guarding galleries and terrains",

abstract = "Let P be a polygon with n vertices. We say that two points of P see each other if the line segment connecting them lies inside (the closure of) P. In this paper we present efficient approximation algorithms for finding the smallest set G of points of P so that each point of P is seen by at least one point of G, and the points of G are constrained to be belong to the set of vertices of an arbitrarily dense grind. We also present similar algorithms for terrains and polygons with holes.",

author = "Alon Efrat and Sariel Har-Peled",

year = "2006",

month = dec,

day = "31",

doi = "10.1016/j.ipl.2006.05.014",

language = "English (US)",

volume = "100",

pages = "238--245",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier B.V.",

number = "6",

}

TY - JOUR

T1 - Guarding galleries and terrains

AU - Efrat, Alon

AU - Har-Peled, Sariel

PY - 2006/12/31

Y1 - 2006/12/31

N2 - Let P be a polygon with n vertices. We say that two points of P see each other if the line segment connecting them lies inside (the closure of) P. In this paper we present efficient approximation algorithms for finding the smallest set G of points of P so that each point of P is seen by at least one point of G, and the points of G are constrained to be belong to the set of vertices of an arbitrarily dense grind. We also present similar algorithms for terrains and polygons with holes.

AB - Let P be a polygon with n vertices. We say that two points of P see each other if the line segment connecting them lies inside (the closure of) P. In this paper we present efficient approximation algorithms for finding the smallest set G of points of P so that each point of P is seen by at least one point of G, and the points of G are constrained to be belong to the set of vertices of an arbitrarily dense grind. We also present similar algorithms for terrains and polygons with holes.

UR - https://www.scopus.com/pages/publications/33749991397

UR - https://www.scopus.com/pages/publications/33749991397#tab=citedBy

U2 - 10.1016/j.ipl.2006.05.014

DO - 10.1016/j.ipl.2006.05.014

M3 - Article

AN - SCOPUS:33749991397

SN - 0020-0190

VL - 100

SP - 238

EP - 245

JO - Information Processing Letters

JF - Information Processing Letters

IS - 6

ER -

Guarding galleries and terrains

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this