On guarding the vertices of rectilinear domains (Q2477198): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/j.comgeo.2007.02.002 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W1970504456 / rank | |||
Normal rank |
Revision as of 00:11, 20 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On guarding the vertices of rectilinear domains |
scientific article |
Statements
On guarding the vertices of rectilinear domains (English)
0 references
13 March 2008
0 references
Two problems on visibility coverage are studied. One is the problem of guarding the vertices of a rectilinear polygon \(P\), which is considered in three different versions which are proved to be NP-hard. The three cases are the following: 1) guards may lie anywhere on the boundary of \(P\), 2) guards may lie only at vertices of \(P\), 3) guards may lie anywhere in \(P\). A 1.5D rectilinear terrain, which is defined by an \(x\)-monotone chain \(T\) of horizontal and vertical line segments, is the region to be guarded in the second problem considered in the article. A connection is established between this problem and the problem of computing a minimum clique cover in chordal graphs. A \(2\)-approximation algorithm for the guarding problem is described. Each part of the article is summarized in terms of a theorem.
0 references
geometric optimization
0 references
guarding
0 references
NP-hardness
0 references
approximation algorithms
0 references
visibility coverage
0 references
piercing problems
0 references