**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”, in
*Proceedings of the 7th Latin American Symposium on Theoretical Informatics (LATIN 2006)*, Valdivia, Chile, March 20–24, 2006, pages 80–92. **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. **Copyright**:- Copyright held by the authors.
**Length**:- The paper is 12 pages.
**Availability**:- The paper is available in PostScript (1109k), gzipped PostScript (613k), and PDF (239k).
- See information on file formats.
- [Google Scholar search]
**Related papers**:- DynamicVoronoi_Algorithmica (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 17, 2018 by Erik Demaine.