Improved Dynamic Planar Point Location

Lars Arge, Gerth Stølting Brodal, and Loukas Georgiadis

In Proc. 47th Annual Symposium on Foundations of Computer Science, pages 305-314, 2006.

Abstract

We develop the first linear-space data structures for dynamic planar point location in general subdivisions that achieve logarithmic query time and poly-logarithmic update time.

Copyright notice

Copyright © 2006 by The Institute of Electrical and Electronics Engineers, Inc. All rights reserved.

Online version

focs06.pdf (184 Kb)

DOI

10.1109/FOCS.2006.40

BIBT_EX entry

@inproceedings{focs06,
  author = "Lars Arge and Gerth Stølting Brodal and Loukas Georgiadis",
  booktitle = "Proc. 47th Annual Symposium on Foundations of Computer Science",
  doi = "10.1109/FOCS.2006.40",
  isbn = "0-7695-2720-5",
  pages = "305-314",
  title = "Improved Dynamic Planar Point Location",
  year = "2006"
}