Improved bounds for wireless localization

Improved bounds for wireless localization

0.00 Avg rating0 Votes
Article ID: iaor20103514
Volume: 57
Issue: 3
Start Page Number: 499
End Page Number: 516
Publication Date: Jul 2010
Journal: Algorithmica
Authors: , , ,
Keywords: art gallery problem
Abstract:

We consider a novel class of art gallery problems inspired by wireless localization that has recently been introduced by Eppstein, Goodrich, and Sitchinava. Given a simple polygon P, place and orient guards each of which broadcasts a unique key within a fixed angular range. In contrast to the classical art gallery setting, broadcasts are not blocked by the edges of P. At any point in the plane one must be able to tell whether or not one is located inside P only by looking at the set of keys received. In other words, the interior of the polygon must be described by a monotone Boolean formula composed from the keys. We improve both upper and lower bounds for the general problem where guards may be placed anywhere by showing that the maximum number of guards to describe any simple polygon on n vertices is between roughly 3 5 n equ1 and 4 5 n equ2 . A guarding that uses at most 4 5 n equ13 guards can be obtained in O(nlogn) time. For the natural setting where guards may be placed aligned to one edge or two consecutive edges of P only, we prove that n-2 guards are always sufficient and sometimes necessary.

Reviews

Required fields are marked *. Your email address will not be published.