Proportional Symbol Maps - Benchmark Instances, by G. Kunigami, R. G. Cano, P. J. de Rezende and C. C. de Souza
Citing this page:
-
Use the BibTeX entry:
@Misc{symbolmaps-instances-page,
author = {Guilherme Kunigami and Rafael G. Cano and Pedro J. de Rezende and Cid C. de Souza},
title = {Proportional Symbol Maps -- Benchmark Instances},
year = {2011},
note = {{\sl www.ic.unicamp.br/$\sim$cid/Problem-instances/Symbol-Maps}}
}
Problem description
Proportional symbol maps are a cartographic tool that employs symbols to represent data associated with specific locations. Each symbol is drawn at a location 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 sizes. Therefore, the (partial) order in which the disks are drawn affects the visual quality of a map. Let S be a set of n disks and A be the arrangement formed by the boundaries of the disks in S. An intersection of the boundaries of two or more disks defines a vertex of A. We say that an arc is a portion of the boundary of a disk that connects two vertices and contains no other vertices. A drawing of S is a subset of the arcs and vertices of A that is drawn on top of the filled interiors of the disks in S. Not every drawing is suitable for use on a map. Cabello et al. [1, 2] present two types of suitable drawings:- Physically realizable drawings: a physically realizable drawing can be thought of as a drawing constructed from whole disks cut out from sheets of paper. The disks can be interleaved, but cannot be cut. More formally, given a face f of the arrangement, there must be a total order on the disks that contain f. Furthermore, multiple partial orderings of the disks cannot contradict each other.
- Stacking drawings: a drawing is a stacking drawing if it is physically realizable and if there exists a total order on the disks of S.
Input Instances
Each instance is organized in directories, being each directory named after the instance. Inside each directory there exists two input files 'input.csv' and 'arrangement.txt'. For some instances we also provide their decomposed components because we used them in our papers. In this case, besides these files, there exists directories with indexes starting from 0, representing the components resulting from a decomposition. Since each of these instances may be further decomposed, there may be nested directories.File Format: Instances
The input data consists of a cvs file named 'input.csv', using semicolons as separators. Each line describes a disk by its center (x, y), radius and an unique identifier. For each line, the first and second cells are floating point numbers representing the x and y coordinates of the center, respectively. The third cell is also a floating point number representing the radius and finally the fourth cell is an integer identifying the disk. For example, the line113.636 ; 178.552; 0.123 ; 13 ;
represents a circumference with center (113.636, 178.552), radius 0.123 and id 13.
Arrangement File
To avoid precision issues, we also provide a description of the arrangement. This file, named 'arrangement.txt' begins with a line describing the number of disks and arcs, denoted by 'n' and 'm' respectively. Then follow 'm' lines describing each arc. Each line contains an integer with the arc id, an integer with the disk 'dr' of which this arc is border, a floating point number denoting the length of the arc and an integer with the number of disks that contain this arc, 'k'. Then, follow 'k' integers representing the id's of the disks that contain this arc. After that, there is a line with a single integer denoting the number of edges, 'ne', in the disk graph of the arrangement. In the next 'ne' lines, there is a pair of integers denoting the disks which corresponding vertex have an edge in common in the disk graph. Then, there is a line with a single integer representing the number of faces, 'nf', in the arrangement. Each of the 'nf' lines describes a face. It begins with an integer denoting the number of arcs, 'nb', that form the boundary of this face. Then follows 'nb' integers corresponding to the id's of the arcs.Output Solution and Results
For each input instance there is a corresponding solution, named 'solution.txt', and a file with statistics regarding both the exact and the heuristic algorithms which is named 'result.txt'. They are organized in the same directory hierarchy of the input.File Format: Best Known Solution
- Stacking Drawings (SD)
The best solution found for stacking drawings is described in a csv file, using semicolons as separators. Each line is a pair of integers denoting the id (from the input) and the level of each disk. For example, the line20 ; 12 ;
means that disk 20 is placed in the 12-th level in this solution. Note that the levels increase from bottom to up, starting from 1.
- Physically Realizable Drawings (PR)
The best solution found for physically realizable drawings is described in a csv file, using spaces as separators. Each line is a pair of integers denoting the id (from the input) of two intersecting discs i and j, denoting that i is drawn above j. For example, the line13 0
means that disk 13 is drawn above disk 0. Note that disks id's starts from 0.
File Format: Results
For each instance we also provide a plain text file with relevant execution statistcs: the value of the provided solution, the sum of the lengths of the arcs that are always visible, the number of nodes explored and the execution time of the branch-and-cut algorithm; the solution value found by GRASP and the corresponding execution time; the solution value found by the parallel GRASP and the corresponding time. strategy used to solve the instance*, number of iterations or number of nodes explorer (depending on the strategy used) and total execution time.Instances Population
These instances first appeared in [3].| Population | instances[.tgz] (62.3K) | SD solutions [.tgz] (23.0K) | PR solutions [.tgz] (226.0K) |
Instances CHKS
These instances first appeared in [1]*. Optimal solutions for the Max-Total stacking problem were presented in [4] for some of these instances. Optimal solutions for the remaining instances were presents in [5].| City 156 | instances [.tgz] (11K) | SD solutions [.tgz] (7.2K) | PR solutions [.tgz] (11K) | |
| City 538 | instances [.tgz] (86.5K) | SD solutions [.tgz] (27.4K) | PR solutions [.tgz] (207K) | |
| Earthquake Magnitude | instances [.tgz] (34.9K) | SD solutions [.tgz] (12.5K) | PR solutions [.tgz] (405K) | |
| Earthquake Deaths | instances [.tgz] (57.6K) | SD solutions [.tgz] (35.3K) | PR solutions [.tgz] (181K) |
Instances Artificial
These are artificial instances created to test the exact and the heuristic algorithms.| Artificial | instances [.tgz] (392.6K) | SD solutions [.tgz] (3.5K) | PR solutions [.tgz] (53K) |
Acknowledgments
*We wish to thank S. Cabello, H. Haverkort, M. van Kreveld, and B. Speckmann for making available the instances presented in [1] and [2]. This research was supported by FAPESP – Fundação de Amparo à Pesquisa do Estado de São Paulo – Grants #2009/17044-5, #2007/52015-0, CNPq – Conselho Nacional de Desenvolvimento Científico e Tecnológico – Grants #830510/1999-0, #301732/2007-8, 472504/2007-0, 473867/2010-9, 483177/2009-1 and a Grant from FAEPEX/Unicamp.References
- [1] Algorithmic aspects of proportional symbol maps, S. Cabello, H. Haverkort, M. van Kreveld, and B. Speckmann, In Y. Azar and T. Erlebach, editors, Proceedings of the 14th European Symposium on Algorithms (ESA), volume 4168 of Lecture Notes in Computer Science, pages 720–731, Springer-Verlag, 2006.
- [2] Algorithmic aspects of proportional symbol maps, S. Cabello, H. Haverkort, M. van Kreveld, and B. Speckmann, Algorithmica, 58(3):543–565, 2010.
- [3] Effective drawing of proportional symbol maps using grasp, R. G. Cano, G. Kunigami, C. C. de Souza, and P. J. de Rezende, 10th Cologne-Twente Workshop on graphs and combinatorial optimization, Frascati, 2011.
- [4] Optimizing the layout of proportional symbol maps, G. Kunigami, P. J. de Rezende, C. C. de Souza, and T. Yunes, 2010, In B. Murgante et al., editors, Proceedings of 11th International Conference on Computational Science and Its Applications (ICCSA), Part III, volume 6784 of Lecture Notes in Computer Science, pages 1-16, Springer-Verlag, 2011.
- [5] Optimizing the layout of proportional symbol maps: Polyhedra and Computation, G. Kunigami, P. J. de Rezende, C. C. de Souza, and T. Yunes, submitted.
Address
Guilherme Kunigami, Rafael G. Cano, Pedro J. de Rezende, and Cid C. de SouzaUniversidade Estadual de Campinas
Instituto de Computação
Avenida Albert Einstein, 1251
13083-852 Campinas, SP, Brasil
Phone: +55 19 3521.5877
Fax: +55 19 3521.5847
e-mail:
