A static optimality transformation with applications to planar point location

John Iacono, Wolfgang Mulzer

    Research output: Contribution to journalArticle

    Abstract

    Over the last decade, there have been several data structures that, given a planar subdivision and a probability distribution over the plane, provide a way for answering point location queries that is fine-tuned for the distribution. All these methods suffer from the requirement that the query distribution must be known in advance. We present a new data structure for point location queries in planar triangulations. Our structure is asymptotically as fast as the optimal structures, but it requires no prior information about the queries. This is a 2-D analogue of the jump from Knuth's optimum binary search trees (discovered in 1971) to the splay trees of Sleator and Tarjan in 1985. While the former need to know the query distribution, the latter are statically optimal. This means that we can adapt to the query sequence and achieve the same asymptotic performance as an optimum static structure, without needing any additional information.

    Original languageEnglish (US)
    Pages (from-to)327-340
    Number of pages14
    JournalInternational Journal of Computational Geometry and Applications
    Volume22
    Issue number4
    DOIs
    StatePublished - Aug 2012

    Keywords

    • Point location
    • entropy
    • static optimality

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • Geometry and Topology
    • Computational Theory and Mathematics
    • Computational Mathematics
    • Applied Mathematics

    Fingerprint Dive into the research topics of 'A static optimality transformation with applications to planar point location'. Together they form a unique fingerprint.

  • Cite this