A finite dominating set of cardinality O(k) and a witness set of cardinality O(n) for 1.5D terrain guarding problem

Haluk Eliş ()
Additional contact information
Haluk Eliş: Bilkent University

Annals of Operations Research, 2017, vol. 254, issue 1, No 3, 37-46

Abstract: Abstract 1.5 dimensional (1.5D) terrain is characterized by a piecewise linear curve. Locating minimum number of guards on the terrain (T) to cover/guard the whole terrain is known as 1.5D terrain guarding problem. Approximation algorithms and a polynomial-time approximation scheme have been presented for the problem. The problem has been shown to be NP-Hard. In the problem, the set of possible guard locations and the set of points to be guarded are uncountable. To solve the problem to optimality, a finite dominating set (FDS) of size $$\hbox {O}(n^{2})$$ O ( n 2 ) and a witness set of size $$\hbox {O}(n^{3})$$ O ( n 3 ) have been presented, where n is the number of vertices on T. We show that there exists an even smaller FDS of cardinality $$\hbox {O}(k)$$ O ( k ) and a witness set of cardinality O(n), where k is the number of convex points. Convex points are vertices with the additional property that between any two convex points the piecewise linear curve representing the terrain is convex. Since it is always true that $$k \le n$$ k ≤ n for $$n \ge $$ n ≥ 2 and since it is possible to construct terrains such that $$n=2^{k}$$ n = 2 k , the existence of an FDS with cardinality O(k) and a witness set of cardinality of $$\hbox {O}(n)$$ O ( n ) leads to the reduction of decision variables and constraints respectively in the zero-one integer programming formulation of the problem.

Keywords: Finite dominating sets; Location; Terrain guarding problem; Zero-one integer programming (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10479-017-2432-4 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:254:y:2017:i:1:d:10.1007_s10479-017-2432-4

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-017-2432-4

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().