We are given a trajectory $\mathcal{T}$ and an area $\mathcal{A}$. $\mathcal{T}$ might intersect $\mathcal{A}$ several times, and our aim is to detect whether $\mathcal{T}$ visits $\mathcal{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).#R##N##R##N#During the modelling of such applications, we encountered 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 if and only if the trajectory $\mathcal {T}$ intersects the area $\mathcal{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 1’s in the substring is at least a certain threshold.#R##N##R##N#In our model, LDS is a core problem for many applications that aim at detecting regularity of $\mathcal{T}$ intersecting  $\mathcal{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.
['Bojan Djordjevic', 'Joachim Gudmundsson', 'Anh Pham', 'Thomas Wolle']
Detecting Regular Visit Patterns