An Efficient Algorithm for Scatter Chart Labeling

Sebastian Theophil, Arno Schödl

This paper presents an efficient algorithm for a new variation of the point feature labeling problem. The goal is to position the largest number of point labels such that they do not intersect each other or their points. First we present an algorithm using a greedy algorithm with limited lookahead. We then present an algorithm that iteratively regroups labels, calling the first algorithm on each group, thereby identifying a close to optimal labeling order. The presented algorithm is being used in a commercial product to label charts, and our evaluation shows that it produces results far superior to those of other labeling algorithms.

Subjects: 15.7 Search; 15.2 Constraint Satisfaction


This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.