A static optimality transformation with applications to planar point location

Iacono John

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

    Abstract

    In the past ten years, there have been a number of data structures that, given a distribution of planar point location queries, produce a planar point location data structure that is tuned for the provided distribution. These structures all suffer from the requirement that the query distribution be provided in advance. For the problem of point location in a triangulation, a data structure is presented that performs asymptotically as well as these structures, but does not require the distribution to be provided in advance. This result is the 2-d analogue of the jump from the optimum binary search trees of Knuth in 1971 which required that the distribution be provided, to the splay trees of Sleator and Tarjan in 1985 where in the static optimality theorem it was proven that splay trees had the same asymptotic performance of optimum search trees without being provided the probability distribution.

    Original languageEnglish (US)
    Title of host publicationProceedings of the 27th Annual Symposium on Computational Geometry, SCG'11
    Pages21-26
    Number of pages6
    DOIs
    StatePublished - 2011
    Event27th Annual ACM Symposium on Computational Geometry, SCG'11 - Paris, France
    Duration: Jun 13 2011Jun 15 2011

    Publication series

    NameProceedings of the Annual Symposium on Computational Geometry

    Other

    Other27th Annual ACM Symposium on Computational Geometry, SCG'11
    CountryFrance
    CityParis
    Period6/13/116/15/11

    Keywords

    • Algorithms

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • Geometry and Topology
    • Computational 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