User interfaces for inspecting spatio-temporal events often allow their users to filter the events by specifying a time window with a time slider. We consider the case that filtered events are visualized on a map using textual or iconic labels. However, to ensure a clear visualization, not all filtered events are annotated with a label. We present algorithms for setting up a data structure that encodes for every possible time window the set of displayed labels. Our algorithms ensure that the displayed labels never overlap and guarantee the stability of the labeling during certain basic interactions with the time slider. Assuming that the labels have different priorities (weights), we aim to maximize the weight of the displayed labels integrated over all possible time windows. As basic interactions, we consider moving the entire time window, symmetrically scaling it, and dragging one of its endpoints. We consider two stability requirements: (1) during a basic interaction, a label should appear and disappear at most once; (2) if a label is displayed for a time window $Q$Q, then it is also displayed for all the time windows contained in $Q$Q and that contain its timestamp. We prove that finding an optimal solution is NP-hard and propose efficient constant-factor approximation algorithms for unit-square and unit-disk labels, as well as a fast greedy heuristic for arbitrarily shaped labels. In experiments on real-world data, we compare the non-exact algorithms with an exact approach through integer linear programming.

Suppose that a circular fire spreads in the plane at unit speed. A fire fighter can build a barrier at speed v > 1. How large must v be to ensure that the fire can be contained, and how should the fire fighter proceed? We provide two results. First, we analyze the natural strategy where the fighter keeps building a barrier along the frontier of the expanding fire. We prove that this approach contains the fire if v > v_c = 2.6144... holds. Second, we show that any "spiralling" strategy must have speed v > 1.618, the golden ratio, in order to succeed.

Several recent works considered cooperative cleaning in static and dynamic environments, which incorporates a swarm of simple robots cleaning an expanding region of contaminated cells in a 2-D grid. However, even the state of the art strategy requires continuously-updated global domain information. In this work-in-progress we examine a strategy operating truly local. Neither in the beginning of a cleaning process, nor later on will our robot swarm receive any global information in order to perform the cooperative cleaning task.

Searching for a point in the plane is a well-known search game problem introduced in the early eighties. The best known search strategy is given by a spiral and achieves a competitive ratio of 17.289 … It was shown by Gal [14] that this strategy is the best strategy among all monotone and periodic strategies. Since then it was unknown whether the given strategy is optimal in general. This paper settles this old open fundamental search problem and shows that spiral search is indeed optimal. The given problem can be considered as the continuous version of the well-known m-ray search problem and also appears in several non-geometric applications and modifications. Therefore the optimality of spiral search is an important question considered by many researchers in the last decades. We answer the logarithmic spiral conjecture for the given problem. The lower bound construction might be helpful for similar settings, it also simplifies existing proofs on classical m-ray search.

How efficiently can we search an unknown environment for a goal in an unknown position? How much would it help if the environment were known? We answer these questions for simple polygons and for undirected graphs by providing online search strategies that are as good as the best offline search algorithms, up to a constant factor. For other settings we prove that no such online algorithms exist. We introduce a natural measure which gives reasonable results and is more realistic than pure pessimistic competitive analysis.

A simple polygon P with two distinguished vertices, s and t, is called a street if the two boundary chains from s to t are mutually weakly visible. We present an on-line strategy that walks from s to t, in any unknown street, on a path at most $\sqrt{2}$ times longer than the shortest path. This matches the best lower bound previously known and settles an open problem in the area of competitive path planning. (The result was simultaneously and independently obtained by the first three authors and by the last two authors. Both papers, [C. Icking, R. Klein, and E. Langetepe, Proceedings of the 16th Symposium on Theoretical Aspects in Computer Science, Lecture Notes in Comput. Sci. 1563, Springer-Verlag, Berlin, 1999, pp. 110--120] and [S. Schuierer and I. Semrau, Proceedings of the 16th Symposium on Theoretical Aspects of Computer Science, pp. 121--131], were presented at STACS'99. The present paper contains a joint full version.)