External Memory Planar Point Location with Logarithmic Updates |
| |
Authors: | Lars Arge Gerth Stølting Brodal S Srinivasa Rao |
| |
Affiliation: | 1. MADALGO (Center for Massive Data Algorithmics—A Center of the Danish National Research Foundation), Department of Computer Science, Aarhus University, IT Parken, Aabogade 34, 8200, Aarhus N, Denmark 2. School of Computer Science and Engineering, Seoul National University, 599 Gwanakro, Gwanak-Gu, Seoul, 151-744, Republic of Korea
|
| |
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(log? B N) I/Os and queries can be answered in $O(\log_{B}^{2} N)$ I/Os in the worst-case. The previous best known linear space dynamic structure also answers queries in $O(\log_{B}^{2} N)$ I/Os, but only supports insertions in amortized $O(\log_{B}^{2} N)$ I/Os. Our structure is also considerably simpler than previous structures. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|