Covering a line segment with variable radius discs
Authors:
- Enrico GrandeEGEnrico Grande
- Pitu B. MirchandaniPMPitu B. Mirchandani
Preprint
Abstract
The paper addresses the problem of locating sensors with a circular field of view so that a given line segment is under full surveillance, which is termed as the Disc Covering Problem on a Line. The cost of each sensor includes a fixed component, and a variable component that is proportional to the field-of-view area. When only one type of sensor or, in general, one type of disc, is available, then a simple polynomial algorithm solves the problem. When there are different types of sensors in terms of fixed and variable costs, the problem becomes NP-hard. A branch-and-bound algorithm as well as an efficient heuristic are developed. The heuristic very often obtains the optimal solution as shown in extensive computational testing.Keywords
All Related Versions
This publication has 3 references indexed in Scilit:
- Almost optimal set covers in finite VC-dimensionDiscrete & Computational Geometry, 1995
- Discrete Location TheoryJournal of the Operational Research Society, 1991
- Facilities Location: Models and MethodsJournal of the Operational Research Society, 1989