Distribution-sensitive point location in convex subdivisions

Sébastien Collette, Vida Dujmović, John Iacono, Stefan Langerman, Pat Morin

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

    Abstract

    A data structure is presented for point location in convex planar subdivisions when the distribution of queries is known in advance. The data structure has an expected query time that differs from the optimal one by only lower order terms in the linear comparison tree model.

    Original languageEnglish (US)
    Title of host publicationProceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms
    Pages912-921
    Number of pages10
    StatePublished - 2008
    Event19th Annual ACM-SIAM Symposium on Discrete Algorithms - San Francisco, CA, United States
    Duration: Jan 20 2008Jan 22 2008

    Publication series

    NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

    Other

    Other19th Annual ACM-SIAM Symposium on Discrete Algorithms
    CountryUnited States
    CitySan Francisco, CA
    Period1/20/081/22/08

    ASJC Scopus subject areas

    • Software
    • Mathematics(all)

    Fingerprint Dive into the research topics of 'Distribution-sensitive point location in convex subdivisions'. Together they form a unique fingerprint.

  • Cite this

    Collette, S., Dujmović, V., Iacono, J., Langerman, S., & Morin, P. (2008). Distribution-sensitive point location in convex subdivisions. In Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (pp. 912-921). (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).