| Texto completo | |
| Autor(es): |
Crepaldi, Bruno E.
;
de Rezende, Pedro J.
;
de Souza, Cid C.
Número total de Autores: 3
|
| Tipo de documento: | Artigo Científico |
| Fonte: | COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS; v. 48, n. 5, p. 10-pg., 2015-07-01. |
| Resumo | |
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) | |
| Processo FAPESP: | 12/17608-9 - O Problema do Posicionamento de Antenas: um Estudo Geometrico e Algortmico |
| Beneficiário: | Bruno Espinosa Crepaldi |
| Modalidade de apoio: | Bolsas no Brasil - Mestrado |
| Processo FAPESP: | 07/52015-0 - Métodos de aproximação para computação visual |
| Beneficiário: | Jorge Stolfi |
| Modalidade de apoio: | Auxílio à Pesquisa - Temático |