Art Gallery Problem, Indoor Localization and Sensor Scheduling

Jie Gao, Stony Brook University

March 22, 2016

We examine the problem of using infrared sensors for indoor localization and tracking. Infrared signals are directional with coverage range limited by line-of-sight constraint. A moving target can be localized and tracked by sensing the shadow cast by the target. In this talk I will talk about the computational geometry problems arising in this setting, namely the sensor placement problem (related to the classical Art Gallery Problem), and the sensor scheduling problem — which and what subset of sensors to turn on in order to guarantee each point in the domain is covered frequently enough. I will report exact and approximation algorithms as well as experiments on a testbed system.

Bio: Jie Gao is an Associate Professor at Computer Science department, Stony Brook University. She received BS from the special class for the gifted young program at University of Science and Technology of China in 1999 and Ph.D in computer science from Computer Science department, Stanford University in 2004. She received NSF Career award in 2006. She is currently serving on the editorial board of ACM Transactions on Sensor Networks and Journal of Discrete Algorithms.