Arc-based integer programming formulations for three variants of proportional symbol maps |
| |
| Affiliation: | 1. Institute of Computing, University of Campinas, Campinas, Brazil;2. School of Business Administration, University of Miami, Coral Gables, USA;1. Institute of Math. Sciences, IV Cross Road, Taramani, Chennai 600 113, India;2. School of Comp. Science, Simon Fraser University, Burnaby, Canada V5A 1S6;3. DIMAP and Math. Institute, University of Warwick, Coventry CV4 7AL, UK;1. Institute for Software Technology, University of Technology, Graz, Austria;2. Instituto de Matemáticas, Universidad Nacional Autónoma de México, D.F. México, México |
| |
| Abstract: | Proportional symbol maps are a cartographic tool that employs scaled symbols to represent data associated with specific locations. The symbols we consider are opaque disks, which may be partially covered by other overlapping disks. We address the problem of creating a suitable drawing of the disks that maximizes one of two quality metrics: the total and the minimum visible length of disk boundaries. We study three variants of this problem, two of which are known to be NP-hard and another whose complexity is open. We propose novel integer programming formulations for each problem variant and test them on real-world instances with a branch-and-cut algorithm. When compared with state-of-the-art models from the literature, our models significantly reduce computation times for most instances. |
| |
| Keywords: | Symbol Maps Integer Programming Computational Geometry |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
