Research Publications

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 {\em most} of the days (weeks or years), but not necessarily on {\em every} day (week or year). During the modelling of such applications, we encountered an elementary problem on bitstrings, that we call {\sc 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 $1$'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.