Data Structures for Halfplane Proximity Queries and Incremental Voronoi Diagrams

Boris Aronov, Prosenjit Bose, Erik D. Demaine, Joachim Gudmundsson, John Iacono, Stefan Langerman, Michiel Smid

    Research output: Contribution to journalArticle

    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(n1 + ε) space and preprocessing time, and answers queries in O(2 1 / εlog n) time, for any 0 < ε< 1. The second data structure uses O(nlog 3n) 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(n2) 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.

    Original languageEnglish (US)
    Pages (from-to)3316-3334
    Number of pages19
    JournalAlgorithmica
    Volume80
    Issue number11
    DOIs
    StatePublished - Nov 1 2018

    Keywords

    • Data structures
    • Flarbs
    • Trees
    • Voronoi diagrams

    ASJC Scopus subject areas

    • Computer Science(all)
    • Computer Science Applications
    • Applied Mathematics

    Fingerprint Dive into the research topics of 'Data Structures for Halfplane Proximity Queries and Incremental Voronoi Diagrams'. Together they form a unique fingerprint.

  • Cite this

    Aronov, B., Bose, P., Demaine, E. D., Gudmundsson, J., Iacono, J., Langerman, S., & Smid, M. (2018). Data Structures for Halfplane Proximity Queries and Incremental Voronoi Diagrams. Algorithmica, 80(11), 3316-3334. https://doi.org/10.1007/s00453-017-0389-y