Searching for segments with largest relative overlap
F. Aurenhammer and G. Stoeckl
be a set of
possibly intersecting line segments on the
data structure is developed that - for an arbitrary query segment
- reports in
time a segment in
which yields the largest
relative overlap with
. The structure needs
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].