**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”,
*Algorithmica*, to appear. **Abstract**:-
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*(*n*^{1 + ε}) space and preprocessing time, and answers queries in*O*(2^{1/ε}log n) time, for any 0 < ε < 1. 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.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. **Comments**:- This paper is also available as arXiv:cs.CG/0512091 of the Computing Research Repository (CoRR) and from SpringerLink.
**Length**:- The paper is 17 pages.
**Availability**:- The paper is available in PDF (400k).
- 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 July 15, 2018 by Erik Demaine.