Aarhus University Seal

External Memory Planar Point Location with Logarithmic Updates

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

  • Department of Computer Science
Point location is an extremely well-studied problem both in internal memory models and recently also in the external memory model. In this paper, we present an I/O-efficient dynamic data structure for point location in general planar subdivisions. Our structure uses linear space to store a subdivision with N segments. Insertions and deletions of segments can be performed in amortized O(logB N) I/Os and queries can be answered in O(logB2 N) I/Os in the worst-case. The previous best known linear space dynamic structure also answers queries in O(logB2 N) I/Os, but only supports insertions in amortized O(logB2 N) I/Os. Our structure is also considerably simpler than previous structures.
Original languageEnglish
Title of host publicationProceedings of the twenty-fourth annual symposium on Computational geometry
EditorsMonique Teilaud
Number of pages8
PublisherAssociation for Computing Machinery
Publication year2008
ISBN (print)978-1-60558-071-5
Publication statusPublished - 2008
EventACM Symposium on Computational Geometry - College Park, MD, United States
Duration: 9 Jun 200811 Jun 2008
Conference number: 24


ConferenceACM Symposium on Computational Geometry
LandUnited States
ByCollege Park, MD

    Research areas

  • dynamic strucutre, external memory, planar subdivisions, point location

See relations at Aarhus University Citationformats

ID: 10560948