**Reference**:- Boris Aronov, Prosenjit Bose, Erik D. Demaine, Joachim Gudmundsson, John Iacono, Stefan Langerman, and Michiel Smid, “Data Structures for Halfplane Proximity Queries and Incremental Voronoi Diagrams”, Manuscript, December 2005.
**Abstract**:-
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*(*n*^{1+ε}) space and preprocessing time, and answers queries in*O*(2^{1/ε}log*n*) time. The second data structure uses*O*(n log^{3}*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*(*n*^{2}) 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. **Comments**:- This paper is also available as arXiv:cs.CG/0512091 of the Computing Research Repository (CoRR).
**Length**:- The paper is 15 pages.
**Availability**:- The paper is available in PostScript (1214k), gzipped PostScript (658k), and PDF (300k).
- See information on file formats.
- [Google Scholar search]
**Related papers**:- DynamicVoronoi_LATIN2006 (Data Structures for Halfplane Proximity Queries and Incremental Voronoi Diagrams)
- DynamicVoronoi_CGW2005 (Data Structures for Halfplane Proximity Queries and Incremental Voronoi Diagrams)

See also other papers by Erik Demaine.

Last updated September 3, 2017 by Erik Demaine.