Proximate planar point location

John Iacono, Stefan Langerman

    Research output: Chapter in Book/Report/Conference proceedingConference contribution


    A new data structure is presented for planar point location that executes a point location query quickly if it is spatially near the previous query. Given a triangulation T of size n and a sequence of point location queries A = q1, . . . qm, the structure presented executes qi in time O(log d(qi-1, qi)). The distance function, d, that is used is a two dimensional generalization of rank distance that counts the number of triangles in a region from qi-1 to qi. The data structure uses O(n log log n) space.

    Original languageEnglish (US)
    Title of host publicationProceedings of the Annual Symposium on Computational Geometry
    Number of pages7
    StatePublished - 2003
    EventNineteenth Annual Symposium on Computational Geometry - san Diego, CA, United States
    Duration: Jun 8 2003Jun 10 2003


    OtherNineteenth Annual Symposium on Computational Geometry
    Country/TerritoryUnited States
    Citysan Diego, CA


    • Planar point location

    ASJC Scopus subject areas

    • Chemical Health and Safety
    • Software
    • Safety, Risk, Reliability and Quality
    • Geometry and Topology


    Dive into the research topics of 'Proximate planar point location'. Together they form a unique fingerprint.

    Cite this