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 while keeping O(log n)-time
point-location queries.