Algorithms for necklace maps

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

1 Citaat (Scopus)
94 Downloads (Pure)


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
Originele taal-2Engels
Pagina's (van-tot)15-36
TijdschriftInternational Journal of Computational Geometry and Applications
Nummer van het tijdschrift1
StatusGepubliceerd - 2015

Vingerafdruk Duik in de onderzoeksthema's van 'Algorithms for necklace maps'. Samen vormen ze een unieke vingerafdruk.

Citeer dit