Minimum covering with travel cost

Sándor P. Fekete (), Joseph S. B. Mitchell () and Christiane Schmidt ()
Additional contact information
Sándor P. Fekete: Braunschweig Institute of Technology
Joseph S. B. Mitchell: Stony Brook University
Christiane Schmidt: Braunschweig Institute of Technology

Journal of Combinatorial Optimization, 2012, vol. 24, issue 1, No 3, 32-51

Abstract: Abstract Given a polygon and a visibility range, the Myopic Watchman Problem with Discrete Vision (MWPDV) asks for a closed path P and a set of scan points $\mathcal{S}$ , such that (i) every point of the polygon is within visibility range of a scan point; and (ii) path length plus weighted sum of scan number along the tour is minimized. Alternatively, the bicriteria problem (ii′) aims at minimizing both scan number and tour length. We consider both lawn mowing (in which tour and scan points may leave P) and milling (in which tour, scan points and visibility must stay within P) variants for the MWPDV; even for simple special cases, these problems are NP-hard. We show that this problem is NP-hard, even for the special cases of rectilinear polygons and L ∞ scan range 1, and negligible small travel cost or negligible travel cost. For rectilinear MWPDV milling in grid polygons we present a 2.5-approximation with unit scan range; this holds for the bicriteria version, thus for any linear combination of travel cost and scan cost. For grid polygons and circular unit scan range, we describe a bicriteria 4-approximation. These results serve as stepping stones for the general case of circular scans with scan radius r and arbitrary polygons of feature size a, for which we extend the underlying ideas to a $\pi(\frac{r}{a}+\frac{r+1}{2})$ bicriteria approximation algorithm. Finally, we describe approximation schemes for MWPDV lawn mowing and milling of grid polygons, for fixed ratio between scan cost and travel cost.

Keywords: Covering; Minimum Watchman Problem; Limited visibility; Lawn mowing; Bicriteria problems; Approximation algorithm; PTAS (search for similar items in EconPapers)
Date: 2012
References: View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-010-9303-0 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:jcomop:v:24:y:2012:i:1:d:10.1007_s10878-010-9303-0

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-010-9303-0

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().