Segmenting object space by geometric reference structures

ABSTRACT

A model for segmentation of an object space by an array of binary, radiation-field sensors and geometric reference structures is described. Given a family of binary, radiation-field sensors and a geometric reference structure, we refer to the set of sensor states induced by a source at point p as the signature of p. We study the segmentation of an object space into signature cells and prove near optimal bounds on the number of distinct signatures induced by a point source, as a function of sensor and reference structure complexity. We also show that almost any family of signatures can be implemented under this model.

REFERENCES

• 1: Agarwal, P. K., Alon, N., Aronov, B., and Suri, S. 1994. Can visibility graphs be represented compactly? Discrete Comput. Geom. 12, 347--365.
• 2: Agarwal, P. K. and Sharir, M. 2000. Arrangements and their applications. In Handbook of Computational Geometry, J.-R. Sack and J. Urrutia, Eds. Elsevier Science Publishers B.V., North-Holland, Amsterdam, 49--119.
• 3: Alon, N. and Spencer, J. 1992. The Probabilistic Method. John Wiley & Sons, New York, NY.
• 4: Brady, D. J., Pitsianis, N. P., and Sun, X. 2004. Reference structure tomography. J. Optic. Soc. Amer. 21, 7, 1140--1147.
• 5: Krishnendu Chakrabarty , S. Sitharama Iyengar , Hairong Qi , Eungchun Cho, Grid Coverage for Surveillance and Target Location in Distributed Sensor Networks, IEEE Transactions on Computers, v.51 n.12, p.1448-1453, December 2002 [doi>10.1109/TC.2002.1146711]
• 6: Fenimore, E. E. 1978. Coded aperture imaging---predicted performance of uniformly redundant arrays. Applied Optics 17, 22, 3562--3570.
• 7: H. González-Banos, A randomized art-gallery algorithm for sensor placement, Proceedings of the seventeenth annual symposium on Computational geometry, p.232-240, June 2001, Medford, Massachusetts, United States [doi>10.1145/378583.378674]
• 8: Gopinathan, U., Brady, D. J., and Pitsianis, N. P. 2003. Coded apertures for efficient pyroelectric motion tracking. Optics Express 11, 18, 2142--2152.
• 9: Gottesman, S. R. and Fenimore, E. E. 1989. New family of binary arrays for coded aperture imaging. Applied Optics 28, 20, 4344--4352.
• 10: Carlos Guestrin , Andreas Krause , Ajit Paul Singh, Near-optimal sensor placements in Gaussian processes, Proceedings of the 22nd international conference on Machine learning, p.265-272, August 07-11, 2005, Bonn, Germany [doi>10.1145/1102351.1102385]
• 11: Henderson, T. C., Grant, E., Luthy, K., Mattos, L., and Craver, M. 2005. Precision localization in Monte Carlo sensor networks. In Proceedings of the 18th International Conference on Computer Applications Industry and Engineering. 26--31.
• 12: Mait, J. N., Athale, R., and van der Gracht, J. 2003. Evolutionary paths in imaging and recent trends. Optics Express 11, 18, 2093--2101.
• 13: Joseph O'Rourke, Art gallery theorems and algorithms, Oxford University Press, Inc., New York, NY, 1987
• 14: Potuluri, P., Xu, M. B., and Brady, D. J. 2003. Imaging with random 3D reference structures. Optics Express 11, 18, 2134--2141.
• 15: Micha Sharir , Pankaj K. Agarwal, Davenport-Schinzel sequences and their geometric applications, Cambridge University Press, New York, NY, 1996
• 16: S Suri , J O'Rourke, Worst-case optimal algorithms for constructing visibility polygons with holes, Proceedings of the second annual symposium on Computational geometry, p.14-23, June 02-04, 1986, Yorktown Heights, New York, United States [doi>10.1145/10515.10517]
• 17: Urrutia, J. 2000. Art gallery and illumination problems. In Handbook of Computational Geometry, J.-R. Sack and J. Urrutia, Eds. North-Holland, Amsterdam, 973--1027.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics

General Terms:
Algorithms, Theory

Keywords:
Sensor network, counting problems, prbobabilistic methods, space segmentation