Algorithms for necklace maps

Research output: Contribution to journalArticleAcademicpeer-review

1 Citation (Scopus)
102 Downloads (Pure)

Abstract

Necklace maps visualize quantitative data associated with regions by placing scaled symbols, usually disks, without overlap on a closed curve (the necklace) surrounding the map regions. Each region is projected onto an interval on the necklace that contains its symbol. In this paper we address the algorithmic question how to maximize symbol sizes while keeping symbols disjoint and inside their intervals. For that we reduce the problem to a one-dimensional problem which we solve efficiently. Solutions to the one-dimensional problem provide a very good approximation for the original necklace map problem. We consider two variants: Fixed-Order, where an order for the symbols on the necklace is given, and Any-Order where any symbol order is possible. The Fixed-Order problem can be solved in O(n log n) time. We show that the Any-Order problem is NP-hard for certain types of intervals and give an exact algorithm for the decision version. This algorithm is fixed-parameter tractable in the thickness K of the input. Our algorithm runs in O(n log n + n2K4K) time which can be improved to O(n log n + nK2K) time using a heuristic. We implemented our algorithm and evaluated it experimentally. Keywords: Necklace maps; scheduling; automated cartography
Original languageEnglish
Pages (from-to)15-36
JournalInternational Journal of Computational Geometry and Applications
Volume25
Issue number1
DOIs
Publication statusPublished - 2015

Fingerprint

Dive into the research topics of 'Algorithms for necklace maps'. Together they form a unique fingerprint.

Cite this