External memory planar point location with logarithmic updates

Lars Arge, Gerth Stølting Brodal, and S. Srinivasa Rao

In Proc. 24st Annual ACM Symposium on Computational Geometry, pages 139-147, 2008.

Abstract

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.

Copyright notice

Copyright © 2008 by the Association for Computer Machinery, Inc.

Online version

socg08.pdf (175 Kb)

DOI

10.1145/1377676.1377699

BIBTEX entry

@inproceedings{socg08,
  author = "Lars Arge and Gerth St{\o}lting Brodal and S. Srinivasa Rao",
  booktitle = "Proc. 24st Annual ACM Symposium on Computational Geometry",
  doi = "10.1145/1377676.1377699",
  isbn = "978-1-60558-071-5",
  pages = "139-147",
  title = "External memory planar point location with logarithmic updates",
  year = "2008"
}