We consider preprocessing a set S of n points in convex position
in the plane 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 among all points 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, for any 0 < ε < 1. 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.
The second data structure uses a new representation of nearest- and
farthest-point Voronoi diagrams of points in convex position. This
representation supports the insertion of new points in clockwise order using
only O(log n) amortized pointer changes, in addition to
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) amortized pointer changes per operation while
keeping O(log n)-time point-location queries.