Minimizing uncertainty through sensor placement with angle constraints

Ioana O. Bercea, Volkan Isler, Samir Khuller

Research output: Contribution to conferencePaperpeer-review


We study the problem of sensor placement in environments in which localization is a necessity, such as ad-hoc wireless sensor networks that allow the placement of a few anchors that know their location or sensor arrays that are tracking a target. In most of these situations, the quality of localization depends on the relative angle between the target and the pair of sensors observing it. In this paper, we consider placing a small number of sensors which ensure good angular α-coverage: given α in [0, π/2], for each target location t, there must be at least two sensors s1 and s2 such that the <(s1ts2) is in the interval [α, π − α]. One of the main difficulties encountered in such problems is that since the constraints depend on at least two sensors, building a solution must account for the inherent dependency between selected sensors, a feature that generic Set Cover techniques do not account for. We introduce a general framework that guarantees an angular coverage that is arbitrarily close to α for any α <= π/3 and apply it to a variety of problems to get bi-criteria approximations. When the angular coverage is required to be at least a constant fraction of α, we obtain results that are strictly better than what standard geometric Set Cover methods give. When the angular coverage is required to be at least (1 − 1/δ) · α, we obtain a O(log δ)- approximation for sensor placement with α-coverage on the plane. In the presence of additional distance or visibility constraints, the framework gives a O(log δ · log kOPT)-approximation, where kOPT is the size of the optimal solution. We also use our framework to give a O(log δ)-approximation that ensures (1 − 1/δ) · α-coverage and covers every target within distance 3R.

Original languageEnglish (US)
Number of pages8
StatePublished - Jan 1 2016
Event28th Canadian Conference on Computational Geometry, CCCG 2016 - Vancouver, Canada
Duration: Aug 3 2016Aug 5 2016


Conference28th Canadian Conference on Computational Geometry, CCCG 2016

ASJC Scopus subject areas

  • Computational Mathematics
  • Geometry and Topology


Dive into the research topics of 'Minimizing uncertainty through sensor placement with angle constraints'. Together they form a unique fingerprint.

Cite this