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 (Formula presented.) 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 (Formula presented.). We present two data structures for this problem. The first data structure uses (Formula presented.) space and preprocessing time, and answers queries in (Formula presented.) time, for any (Formula presented.). The second data structure uses (Formula presented.) space and polynomial preprocessing time, and answers queries in (Formula presented.) time. These are the first solutions to the problem with (Formula presented.) query time and (Formula presented.) 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 (Formula presented.) amortized pointer changes, in addition to (Formula presented.)-time point-location queries, even though every such update may make (Formula presented.) 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 (Formula presented.)-time point-location queries.

Additional Metadata
Keywords Data structures, Flarbs, Trees, Voronoi diagrams
Persistent URL dx.doi.org/10.1007/s00453-017-0389-y
Journal Algorithmica
Aronov, B. (Boris), Bose, P, Demaine, E.D. (Erik D.), Gudmundsson, J. (Joachim), Iacono, J. (John), Langerman, S. (Stefan), & Smid, M. (2017). Data Structures for Halfplane Proximity Queries and Incremental Voronoi Diagrams. Algorithmica, 1–19. doi:10.1007/s00453-017-0389-y