  In this paper, we analyze the approximation quality of a greedy heuristic for
automatic map labeling. As input, we have a set of events, each associated with
a label at a fixed position, a timestamp, and a weight. Let a time-window
labeling be a selection of these labels such that all corresponding timestamps
lie in a queried time window and no two labels overlap. A solution to the
time-window labeling problem consists of a data structure that encodes a
time-window labeling for each possible time window; when a user specifies a
time window of interest using a slider interface, we query the data structure
for the corresponding labeling.
  We define the quality of a time-window labeling solution as the sum of the
weights of the labels in each time-window labeling, integrated over all time
windows. We aim at maximizing the quality under the condition that a label may
never disappear when the user shrinks the time window. In this paper, we
analyze how well a greedy heuristic approximates the maximum quality that can
be realized under this condition.
  On the one hand, we present an instance with square labels of equal size and
equal weight for which the greedy heuristic fails to find a solution of at
least 1/4 of the quality of an optimal solution. On the other hand, we prove
that the greedy heuristic does guarantee a solution with at least 1/8 of the
quality of an optimal solution. In the case of disk-shaped labels of equal size
and equal weight, the greedy heuristic gives a solution with at least 1/10 of
the quality of an optimal solution. If the labels are squares or disks of equal
size and the maximum weight divided by the minimum weight is at most b, then
the greedy heuristic has approximation ratio Theta(log b).
