Busca avançada
Ano de início
Entree
(Referência obtida automaticamente do Web of Science, por meio da informação sobre o financiamento pela FAPESP e o número do processo correspondente, incluída na publicação pelos autores.)

A hybrid GRASP heuristic to construct effective drawings of proportional symbol maps

Texto completo
Autor(es):
Cano, Rafael G. [1] ; Kunigami, Guilherme [1] ; de Souza, Cid C. [1] ; de Rezende, Pedro J. [1]
Número total de Autores: 4
Afiliação do(s) autor(es):
[1] Univ Estadual Campinas, Inst Comp, BR-13084852 Campinas, SP - Brazil
Número total de Afiliações: 1
Tipo de documento: Artigo Científico
Fonte: Computers & Operations Research; v. 40, n. 5, p. 1435-1447, MAY 2013.
Citações Web of Science: 4
Resumo

Proportional symbol map is a cartographic tool that employs symbols to represent data associated with specific locations. Each symbol is drawn at the location of an event and its size is proportional to the numerical data collected at that point on the map. The symbols considered here are opaque disks. When two or more disks overlap, part of their boundaries may not be visible and it might be difficult to gauge their size. Therefore, the order in which the disks are drawn affects the visual quality of a map. In this work, we focus on stacking drawings, i.e., a drawing that corresponds to the disks being stacked up, in sequence, starting from the one at the bottom of the stack. We address the Max-Total problem, which consists in maximizing the total visible boundary of all disks. We propose a sophisticated heuristic based on GRASP that includes most of the advanced techniques described in the literature for this procedure. We tested both sequential and parallel implementations on benchmark instances and the comparison against optimal solutions confirms the high quality of our heuristic. To the best of our knowledge, this is the first time a metaheuristic is applied to this problem. (C) 2012 Elsevier Ltd. All rights reserved. (AU)

Processo FAPESP: 09/17044-5 - Desenho de mapas de símbolos proporcionais utilizando GRASP
Beneficiário:Rafael Ghussn Cano
Linha de fomento: Bolsas no Brasil - Iniciação Científica
Processo FAPESP: 07/52015-0 - Métodos de aproximação para computação visual
Beneficiário:Jorge Stolfi
Linha de fomento: Auxílio à Pesquisa - Temático