Dynamization of the trapezoid method for planar point location

Yi Jen Chiang, Roberto Tamassia

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

    Abstract

    We present a fully dynamic data structure for point location in a monotone subdivision, based on the trapezoid method. The operations supported are insertion and deletion of vertices and edges, and horizontal translation of vertices. Let n be the current number of vertices of the subdivision. Point location queries take O(logn) time, while updates take O(log2n) time. The space requirement is O(n log n). This is the first fully dynamic point location data structure for monotone subdivisions that achieves optimal query time.

    Original languageEnglish (US)
    Title of host publicationProceedings of the Annual Symposium on Computational Geometry
    PublisherAssociation for Computing Machinery
    Pages61-70
    Number of pages10
    ISBN (Print)0897914260
    DOIs
    StatePublished - Jun 1 1991
    Event7th Annual Symposium on Computational Geometry, SCG 1991 - North Conway, United States
    Duration: Jun 10 1991Jun 12 1991

    Publication series

    NameProceedings of the Annual Symposium on Computational Geometry

    Other

    Other7th Annual Symposium on Computational Geometry, SCG 1991
    CountryUnited States
    CityNorth Conway
    Period6/10/916/12/91

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • Geometry and Topology
    • Computational Mathematics

    Fingerprint Dive into the research topics of 'Dynamization of the trapezoid method for planar point location'. Together they form a unique fingerprint.

    Cite this