Algorithms for Consistent Dynamic Labeling of Maps With a Time-Slider Interface

Area of Science:

• Computer Science
• Information Visualization
• Human-Computer Interaction

Background:

• User interfaces for spatio-temporal events often use time sliders to filter events visualized on maps with labels.
• Ensuring clear visualization requires selective labeling, as not all events can be displayed.
• Label stability and non-overlap are crucial for effective interaction with time-varying data.

Purpose of the Study:

• To develop algorithms for creating a data structure that encodes displayed labels for all possible time windows.
• To maximize the total weight of displayed labels integrated over all time windows, considering label priorities.
• To ensure label stability during basic time slider interactions.

Main Methods:

• Algorithms for setting up a data structure encoding displayed labels for every time window.
• Analysis of label overlap and stability during time window manipulations (moving, scaling, endpoint dragging).
• Development of approximation algorithms (constant-factor for specific shapes, greedy heuristic for arbitrary shapes) and comparison with exact methods (integer linear programming).

Main Results:

• Proved that finding an optimal solution for maximizing displayed label weight is NP-hard.
• Proposed efficient constant-factor approximation algorithms for unit-square and unit-disk labels.
• Developed a fast greedy heuristic for arbitrarily shaped labels.
• Experimental comparison of approximation algorithms against an exact approach using real-world data.

Conclusions:

• The study presents novel algorithms for optimizing spatio-temporal label display, balancing visualization clarity with user interaction stability.
• Efficient approximation algorithms are provided for practical applications where optimal solutions are computationally infeasible.
• The proposed methods ensure non-overlapping labels and guarantee stability under common time slider interactions, enhancing user experience.