External Memory Planar Point Location with Logarithmic Updates

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

In Algorithmica, volume 63(1), pages 457-475, 2012.

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

© Springer-Verlag Berlin Heidelberg 2011. All rights reserved.

Online version

algorithmica12.pdf (222 Kb)

DOI

10.1007/s00453-011-9541-2

BIBTEX entry

@article{algorithmica12,
  author = "Lars Arge and Gerth Stølting Brodal and S. Srinivasa Rao",
  doi = "10.1007/s00453-011-9541-2",
  issn = "0178-4617",
  journal = "Algorithmica",
  number = "1",
  pages = "457-475",
  title = "External Memory Planar Point Location with Logarithmic Updates",
  volume = "63",
  year = "2012"
}

Other versions