We are given a trajectory T and an area A. T might intersect A several times, and our aim is to detect whether T visits A with some regularity, e.g. what is the longest time span that a GPS-GSM equipped elephant visited a specific lake on a daily (weekly or yearly) basis, where the elephant has to visit the lake most of the days (weeks or years), but not necessarily on every day (week or year). During the modelling of such applications, we encounter an elementary problem on bitstrings, that we call LDS (LongestDenseSubstring). The bits of the bitstring correspond to a sequence of regular time points, in which a bit is set to 1 iff the trajectory T intersects the area A at the corresponding time point. For the LDS problem, we are given a string s as input and want to output a longest substring of s, such that the ratio of l's in the substring is at least a certain threshold. In our model, LDS is a core problem for many applications that aim at detecting regularity of T intersecting A. We propose an optimal algorithm to solve LDS, and also for related problems that are closer to applications, we provide efficient algorithms for detecting regularity.
展开▼
