Günter Rote, Christian Schwarz, and Jack Snoeyink:
Maintaining the approximate width of a set of points in the plane
(extended abstract)
In: Proceedings of the Fifth Canadian Conference on Computational
Geometry,
Waterloo, August 5-9, 1993. Editor: A. Lubiw,
J. Urrutia;
pp. 258-263.
Abstract
The width of a set of n
points in the plane is the smallest distance between two parallel lines
that enclose the set. We maintain the set of points under insertions
and deletions of points and we are able to report an approximation of
the width of this dynamic point set. Our data structure takes linear
space and allows for reporting the approximation with relative accuracy
epsilon in O(sqrt(1/epsilon)
log n) time; and the update
time is O(log2 n). The method uses the
tentative
prune-and-search strategy of Kirkpatrick and Snoeyink
Last update: August 27, 2003.