Optimal planar point location

John Iacono

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

    Abstract

    Given a fixed distribution of point location queries among the regions of a triangulation of the plane, a data structure is presented that achieves, within constant multiplicative factors, the entropy bound on the expected point location query time.

    Original languageEnglish (US)
    Title of host publicationProceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms
    Pages340-341
    Number of pages2
    StatePublished - 2001
    Event2001 Operating Section Proceedings, American Gas Association - Dallas, TX, United States
    Duration: Apr 30 2001May 1 2001

    Publication series

    NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

    Other

    Other2001 Operating Section Proceedings, American Gas Association
    CountryUnited States
    CityDallas, TX
    Period4/30/015/1/01

    Keywords

    • Algorithms
    • Theory

    ASJC Scopus subject areas

    • Software
    • Mathematics(all)

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

  • Cite this

    Iacono, J. (2001). Optimal planar point location. In Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms (pp. 340-341). (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).