Data Structures for Halfplane Proximity Queries and Incremental Voronoi Diagrams
<|reference_start|>Data Structures for Halfplane Proximity Queries and Incremental Voronoi Diagrams: 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 $\ell$ 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 $\ell$. We present two data structures for this problem. The first data structure uses $O(n^{1+\varepsilon})$ space and preprocessing time, and answers queries in $O(2^{1/\varepsilon} \log n)$ time, for any $0 < \varepsilon < 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 $\Theta(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.<|reference_end|>
@article{aronov2005data,
    title={Data Structures for Halfplane Proximity Queries and Incremental Voronoi
  Diagrams},
    author={Boris Aronov, Prosenjit Bose, Erik D. Demaine, Joachim Gudmundsson,
  John Iacono, Stefan Langerman, Michiel Smid},
    journal={arXiv preprint arXiv:cs/0512091},
    year={2005},
    archivePrefix={arXiv},
    eprint={cs/0512091},
    primaryClass={cs.CG cs.DS}
}