Searching for segments with largest relative overlap

F. Aurenhammer and G. Stoeckl

Abstract:

Let $S$ be a set of $n$ possibly intersecting line segments on the $x$-axis. A data structure is developed that - for an arbitrary query segment $\sigma$ - reports in $O(\log)$ time a segment in $S$ which yields the largest relative overlap with $\sigma$. The structure needs $O(n \log)$ time and $O(n)$ space for construction. These bounds are asymptotically optimal.

Reference: F. Aurenhammer and G. Stoeckl. Searching for segments with largest relative overlap. Information Processing Letters, 41:103-108, 1992. [Report B 91-10, FU Berlin, Germany, 1991].