**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
*Abstracts from the 15th Annual Fall Workshop on Computational Geometry*, Philadelphia, Pennsylvania, November 18–19, 2005, pages 51–52. **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. **Length**:- The abstract is 2 pages.
**Availability**:- The abstract is available in PostScript (237k), gzipped PostScript (110k), and PDF (128k).
- See information on file formats.
- [Google Scholar search]
**Related papers**:- DynamicVoronoi_Algorithmica (Data Structures for Halfplane Proximity Queries and Incremental Voronoi Diagrams)
- DynamicVoronoi_LATIN2006 (Data Structures for Halfplane Proximity Queries and Incremental Voronoi Diagrams)

See also other papers by Erik Demaine.

Last updated January 18, 2021 by Erik Demaine.