Computational complexity issues in synthesis of simple distributed detection networks

Algorithmic issues of simple object detection problems in the context of a system consisting of a finite set of sensors that monitor a workspace are studied. Each sensor detects the presence of only a certain subset of a given set of objects O. Given that an object has been detected by a subset of sensors, the detection problem deals with identifying whether the object in the workspace is a member of O and, if so, computing the maximal set of such numbers. A conceptual graph structure called the detection network that yields efficient algorithms for the detection problem for combinational, message-based, sequential and parallel computing systems is proposed. The problem of computing a detection network with the minimum number of edges is shown to be computationally intractable, and polynomial-time approximation algorithms are presented. Sequential algorithms to solve the detection problem with and without preprocessing are presented. Parallel algorithms on shared memory systems and hypercube-based message passing systems are discussed. It is shown that the problem of detecting multiple objects is computationally intractable