Sensor selection in arbitrary dimensions

Volkan Isler, Malik Magdon-Ismail

Research output: Contribution to journalArticlepeer-review

9 Scopus citations


We address the sensor selection problem which arises in tracking and localization applications. In sensor selection, the goal is to select a small number of sensors whose measurements provide a good estimate of a target's state (such as location). We focus on the bounded uncertainty sensing model where the target is a point in the d-dimensional Euclidean space. Each sensor measurement corresponds to a convex polyhedral subset of the space. The measurements are merged by intersecting corresponding sets. We show that, on the plane, four sensors are sufficient (and sometimes necessary) to obtain an estimate whose area is at most twice the area of the best possible estimate (obtained by intersecting all measurements). We also extend this result to arbitrary dimensions and show that a constant number of sensors suffice for a constant factor approximation in arbitrary dimensions. Both constants depend on the dimensionality of the space but are independent of the total number of sensors in the network.

Original languageEnglish (US)
Article number4473032
Pages (from-to)651-660
Number of pages10
JournalIEEE Transactions on Automation Science and Engineering
Issue number4
StatePublished - Oct 2008

Bibliographical note

Funding Information:
Manuscript received February 12, 2007; revised May 6, 2007. First published March 24, 2008; current version published October 1, 2008. This paper was recommended for publication by Associate Editor J. Selig and Editor M. Wang upon evaluation of the reviewers’ comments. The work of V. Isler was supported in part by the National Science Foundation under Grant CCF-0634823. The work of M. Magdon-Ismail was supported in part by the National Science foundation under Grant CNS-0323324.


  • Camera networks and sensor selection
  • Computational geometry and object modeling
  • Geometric algorithms
  • Languages
  • Minimum enclosing simplex
  • Polytope approximation
  • Sensor networks
  • Systems


Dive into the research topics of 'Sensor selection in arbitrary dimensions'. Together they form a unique fingerprint.

Cite this