| Full text | |
| Author(s): |
Crepaldi, Bruno E.
;
de Rezende, Pedro J.
;
de Souza, Cid C.
Total Authors: 3
|
| Document type: | Journal article |
| Source: | COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS; v. 48, n. 5, p. 10-pg., 2015-07-01. |
| Abstract | |
Considered a variation of the art gallery problem, the wireless localization problem deals with the placement of the smallest number of broadcasting antennas required to satisfy some property within a given polygon. The case dealt with here consists of antennas that propagate a unique key within a certain antenna-specific angle of broadcast, so that the set of keys received at any given point is sufficient to determine whether that point is inside or outside the polygon. To ascertain this localization property, a Boolean formula must be produced along with the placement of the antennas. In this paper, we present an exact algorithm based on integer linear programming for solving the NIP-hard natural wireless localization problem. The efficiency of our algorithm is certified by experimental results comprising the solutions of 720 instances, including polygon with holes, of up to 1000 vertices, in less than fifteen minutes on a standard desktop computer. (C) 2015 Elsevier B.V. All rights reserved. (AU) | |
| FAPESP's process: | 12/17608-9 - Wireless Localization Problem: a geometric and algorithmic study |
| Grantee: | Bruno Espinosa Crepaldi |
| Support Opportunities: | Scholarships in Brazil - Master |
| FAPESP's process: | 07/52015-0 - Approximation methods for visual computing |
| Grantee: | Jorge Stolfi |
| Support Opportunities: | Research Projects - Thematic Grants |