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