Algorithms for Proportional Symbol Maps Problems – Københavns Universitet

Algorithms for Proportional Symbol Maps Problems

Talk by Rafael Cano at September 10th, 2014, from 15.00 – 16.00


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 present a series of decomposition techniques and three integer programming models, which together allow us to find provably optimal solutions for many real-world instances in less than a minute.

Short Bio

  • 2011: BSc in Computer Engineering from the Institute of Computing, University of Campinas, Brazil.
  • Since 2011: PhD student at the University of Campinas.
  • Currently working at the Eindhoven University of Technology as a visiting PhD student.