{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:40:19Z","timestamp":1750308019052,"version":"3.41.0"},"reference-count":21,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2007,10,1]],"date-time":"2007-10-01T00:00:00Z","timestamp":1191196800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Sen. Netw."],"published-print":{"date-parts":[[2007,10]]},"abstract":"<jats:p>We consider sensors, such as fibers, lasers, and pyroelectric motion detectors, that fire when objects cross a boundary. A moving object can be localized by analyzing sequences of boundary crossings. We consider the number of distinct sequences and object positions that can be achieved using boundary sensors in one- and two-dimensional spaces. For 1D systems we use representations of sensor sequences on graphs to derive limits on the number of object locations that can be monitored by a given sensor population and sequence length. For 2D systems we show that in certain circumstances the ratio of the number of unique sensor sequences to the number of unique object paths is exponential in the sequence length and we argue that the probability of unique identification is high for sufficiently large sequences. We also prove the triangle grid can track an object with error limited to a small neighborhood.<\/jats:p>","DOI":"10.1145\/1281492.1281496","type":"journal-article","created":{"date-parts":[[2007,10,12]],"date-time":"2007-10-12T15:47:29Z","timestamp":1192204049000},"page":"21","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["Localization using boundary sensors"],"prefix":"10.1145","volume":"3","author":[{"given":"Yunhui","family":"Zheng","sequence":"first","affiliation":[{"name":"Duke University, Durham, NC"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David J.","family":"Brady","sequence":"additional","affiliation":[{"name":"Duke University, Durham, NC"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pankaj K.","family":"Agarwal","sequence":"additional","affiliation":[{"name":"Duke University, Durham, NC"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2007,10]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"crossref","unstructured":"Aigner M. and Ziegler G. M. 1998. Proofs from the Book. Springer-Verlag Berlin Germany.  Aigner M. and Ziegler G. M. 1998. Proofs from the Book. Springer-Verlag Berlin Germany.","DOI":"10.1007\/978-3-662-22343-7"},{"volume-title":"Proceedings of the 12th International Joint Conference on Artificial Intelligence (IJCAI).","author":"Bellutta P.","key":"e_1_2_1_2_1"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-9967-7"},{"key":"e_1_2_1_4_1","unstructured":"Chung F. R. K. 1997. Spectral Graph Theory. American Mathematical Society Providence RI.  Chung F. R. K. 1997. Spectral Graph Theory. American Mathematical Society Providence RI."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1024596016427"},{"key":"e_1_2_1_6_1","first-page":"203","article-title":"Circuits and trees in oriented linear graphs","volume":"28","author":"de Bruijn N.","year":"1951","journal-title":"Simon Stevin"},{"key":"e_1_2_1_7_1","unstructured":"Dougherty B. C. Bunch R. M. Lukens R. E. Nagel J. and Wolfe W. L. 2004. Passive infrared device for detection of boundary crossings. United States Patent Application 20040129883.  Dougherty B. C. Bunch R. M. Lukens R. E. Nagel J. and Wolfe W. L. 2004. Passive infrared device for detection of boundary crossings. United States Patent Application 20040129883."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1364\/OE.11.002142"},{"key":"e_1_2_1_9_1","unstructured":"Harary F. 1994. Graph Theory. Addison-Wesley 376--379.  Harary F. 1994. Graph Theory. Addison-Wesley 376--379."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/941350.941367"},{"key":"e_1_2_1_11_1","unstructured":"Lucas E. 1891. Recreations Mathematiques. Gauthier-Villares Paris France.  Lucas E. 1891. Recreations Mathematiques. Gauthier-Villares Paris France."},{"volume-title":"Proceedings of INFOCOM. 1380--1387","author":"Meguerdichian S.","key":"e_1_2_1_12_1"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/381677.381691"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/501431.501432"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1364\/OE.11.000965"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1080\/00029890.1941.11991103"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/570738.570744"},{"volume-title":"International Conference on Distributed Computing Systems.","author":"Ye F.","key":"e_1_2_1_18_1"},{"volume-title":"Proceedings of the IEEE International Symposium on Circuits and Systems. 376--379","author":"Zahnd S.","key":"e_1_2_1_19_1"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1364\/AO.44.004306"},{"key":"e_1_2_1_21_1","unstructured":"Zheng Y. Pitsianis N. P. and Brady D. J. 2006. A fiber sensor floor web for multi-person tracking. IEEE Sensor J. To appear.  Zheng Y. Pitsianis N. P. and Brady D. J. 2006. A fiber sensor floor web for multi-person tracking. IEEE Sensor J. To appear."}],"container-title":["ACM Transactions on Sensor Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1281492.1281496","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1281492.1281496","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T15:13:46Z","timestamp":1750259626000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1281492.1281496"}},"subtitle":["An analysis based on graph theory"],"short-title":[],"issued":{"date-parts":[[2007,10]]},"references-count":21,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2007,10]]}},"alternative-id":["10.1145\/1281492.1281496"],"URL":"https:\/\/doi.org\/10.1145\/1281492.1281496","relation":{},"ISSN":["1550-4859","1550-4867"],"issn-type":[{"type":"print","value":"1550-4859"},{"type":"electronic","value":"1550-4867"}],"subject":[],"published":{"date-parts":[[2007,10]]},"assertion":[{"value":"2007-10-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}