Expected asymptotically optimal planar point location

John Iacono

    Research output: Contribution to journalArticle

    Abstract

    Given a fixed distribution of point location queries among the triangles in 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. The data structure is a simple variation of Kirkpatrick's classic planar point location structure [D.G. Kirkpatrick, SIAM J. Comput. 12 (1) (1983) 28-35], and has linear construction costs and space requirements.

    Original languageEnglish (US)
    Pages (from-to)19-22
    Number of pages4
    JournalComputational Geometry: Theory and Applications
    Volume29
    Issue number1
    DOIs
    StatePublished - Sep 2004

    Keywords

    • Distribution-sensitive data structures
    • Point location

    ASJC Scopus subject areas

    • Computer Science Applications
    • Geometry and Topology
    • Control and Optimization
    • Computational Theory and Mathematics
    • Computational Mathematics

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

  • Cite this