We consider preprocessing a set S of n points in the plane
that are in convex position into a data structure supporting
queries of the following form:
given a point q and a directed line ℓ in the plane,
report the point of S that is farthest from
(or, alternatively, nearest to) the point q
subject to being to the left of line ℓ.
We present two data structures for this problem.
The first data structure uses O(n1+ε) space
and preprocessing time, and answers queries in
O(21/ε log n) time.
The second data structure uses
O(n log3 n)
space and polynomial preprocessing time,
and answers queries in O(log n) time.
These are the first solutions to the problem with O(log n)
query time and o(n2) space.
In the process of developing the second data structure,
we develop a new representation of nearest-point and farthest-point
Voronoi diagrams of points in convex position. This representation
supports insertion of new points in counterclockwise order using
only O(log n) amortized pointer changes,
subject to supporting O(log n)-time point-location queries,
even though every such update may make Θ(n) combinatorial changes
to the Voronoi diagram.
This data structure is the first demonstration that deterministically and
incrementally constructed Voronoi diagrams can be maintained in
o(n) pointer changes per operation.