×

Optimizing the layout of proportional symbol maps: polyhedra and computation. (English) Zbl 1356.68253

Summary: Proportional symbol maps are a cartographic tool to assist in the visualization and analysis of quantitative data associated with specific locations, such as earthquake magnitudes, oil well production, and temperature at weather stations. As the name suggests, symbol sizes are proportional to the magnitude of the physical quantities that they represent. We present two novel integer linear programming (ILP) models to solve this computational geometry problem: how to draw opaque disks on a map so as to maximize the total visible border of all disks. We focus on drawings obtained by layering symbols on top of each other, also known as stacking drawings. We introduce decomposition techniques as well as several families of facet-defining inequalities, which are used to strengthen the ILP models that are supplied to a commercial solver. We demonstrate the effectiveness of our approach through a series of computational experiments using hundreds of instances generated from real demographic and geophysical data sets. To the best of our knowledge, we are the first to use ILP to tackle this problem, and the first to provide provably optimal symbol maps for those data sets.

MSC:

68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
51M20 Polyhedra and polytopes; regular figures, division of spaces
65D18 Numerical aspects of computer graphics, image analysis, and computational geometry
90C10 Integer programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Cabello S, Haverkort H, van Kreveld M, Speckmann B (2006) Algorithmic aspects of proportional symbol maps. Azar Y, Erlebach T, eds. Proc. 14th Eur. Sympos. Algorithms (ESA), Lecture Notes in Computer Science, Vol. 4168 (Springer-Verlag, Berlin), 720-731. CrossRef · Zbl 1131.68563
[2] Cabello S, Haverkort H, van Kreveld M, Speckmann B (2010) Algorithmic aspects of proportional symbol maps. Algorithmica 58:543-565. CrossRef · Zbl 1202.68471
[3] Dent B (1999) Cartography–Thematic Map Design, 5th ed. (McGraw-Hill, Boston).
[4] Fair Isaac Corporation (2009) Xpress Optimizer Reference Manual. Accessed June 22, 2013, http://www.fico.com/en/FIResourcesLibrary/Xpress-Optimizer-Refernce-Manual.pdf.
[5] Garey MR, Johnson DS (1979) Computers and Intractability (Freeman, San Francisco).
[6] Griffin T (1990) The importance of visual contrast for graduated circles. Cartography 19:21-30. CrossRef
[7] Gupta R, Walrand J, Goldschmidt O (2005) Maximal cliques in unit disk graphs: Polynomial approximation. Proc. Second Internat. Network Optim. Conf. (INOC), Lisbon, Portugal. Accessed November 1, 2012, http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.70.1687&rep=rep1&type=pdf.
[8] Kunigami G, de Rezende PJ, de Souza CC, Yunes T (2011) Optimizing the layout of proportional symbol maps. Murgante B, Gervasi O, Iglesias A, Taniar D, Apduhan BO, eds. Proc. ICCSA, Part III, 11th Internat. Workshop on Computational Geometry and Appl. (CGA), Lecture Notes Computer Science, Vol. 6784 (Springer-Verlag, Berlin), 1-16. CrossRef
[9] Müller R (1996) On the partial order polytope of a digraph. Math. Programming 73:31-49. CrossRef · Zbl 0848.90105
[10] Nemhauser GL, Sigismondi G (1992) A strong cutting plane/branch-and-bound algorithm for node packing. J. Oper. Res. Soc. 43:443-457. CrossRef · Zbl 0756.90067
[11] NOAA Satellite and Information Service (2005) National geophysical data center. Accessed November 1, 2012, http://www.ngdc.noaa.gov.
[12] Padberg MW (1973) On the facial structure of set packing polyhedra. Math. Programming 5:199-215. CrossRef · Zbl 0272.90041
[13] Slocum TA, McMaster RB, Kessler FC, Howard HH (2003) Thematic Cartography and Geographic Visualization, 2nd ed. (Prentice Hall, Upper Saddle River, NJ).
[14] Wein R, Fogel E, Zukerman B, Halperin D (2007) Advanced programming techniques applied to CGAL’s arrangement package. Computational Geometry 38:37-63. CrossRef · Zbl 1114.65312
[15] West D (2001) Introduction to Graph Theory, 2nd ed. (Prentice Hall, Upper Saddle River, NJ).
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.