Paper by Erik D. Demaine

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.

BibTeX

@InProceedings{DynamicVoronoi_LATIN2006,
  AUTHOR        = {Boris Aronov and Prosenjit Bose and Erik D. Demaine and
                   Joachim Gudmundsson and John Iacono and Stefan Langerman
                   and Michiel Smid},
  TITLE         = {Data Structures for Halfplane Proximity Queries and
                   Incremental Voronoi Diagrams},
  BOOKTITLE     = {Proceedings of the 7th Latin American Symposium on
                   Theoretical Informatics (LATIN 2006)},
  bookurl       = {http://www.latin06.org/},
  ADDRESS       = {Valdivia, Chile},
  MONTH         = {March 20--24},
  YEAR          = 2006,
  PAGES         = {80--92},

  copyright     = {Copyright held by the authors.},
  length        = {12 pages},
  papers        = {DynamicVoronoi_Algorithmica; DynamicVoronoi_CGW2005},
  replaces      = {DynamicVoronoi_CGW2005},
  doi           = {https://dx.doi.org/10.1007/11682462_12},
  dblp          = {https://dblp.org/rec/conf/latin/AronovBDGILS06},
  comments      = {This paper is also available as <A HREF="https://arXiv.org/abs/cs/0512091">arXiv:cs/0512091</A>, and from <A HREF="https://doi.org/10.1007/11682462_12">SpringerLink</A>.},
}

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³ 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²) 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/0512091, and from SpringerLink.

Copyright:

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)