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: Chapter in Book/Report/Conference proceedingConference contribution


    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 I 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(n1+ε) space and preprocessing time, and answers queries in O(21/ε log n) time. The second data structure uses O(n log3 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(n2) 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.

    Original languageEnglish (US)
    Title of host publicationLATIN 2006
    Subtitle of host publicationTheoretical Informatics - 7th Latin American Symposium, Proceedings
    Number of pages13
    StatePublished - 2006
    EventLATIN 2006: Theoretical Informatics - 7th Latin American Symposium - Valdivia, Chile
    Duration: Mar 20 2006Mar 24 2006

    Publication series

    NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
    Volume3887 LNCS
    ISSN (Print)0302-9743
    ISSN (Electronic)1611-3349


    OtherLATIN 2006: Theoretical Informatics - 7th Latin American Symposium

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • General Computer Science


    Dive into the research topics of 'Data structures for halfplane proximity queries and incremental Voronoi diagrams'. Together they form a unique fingerprint.

    Cite this