Searching for segments with largest relative overlap

F. Aurenhammer and G. Stoeckl


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. In Proc. $15^{th}$ IFIP Conf. System Modelling and Optimization, Lecture Notes in Control and Information Sciences, volume 180, pages 77-84, Zuerich, Switzerland, 1992. Springer Verlag.