Report
Dynamic Planar Point Location in External Memory
| العنوان: | Dynamic Planar Point Location in External Memory |
|---|---|
| المؤلفون: | Munro, J. Ian, Nekrich, Yakov |
| سنة النشر: | 2019 |
| المجموعة: | Computer Science |
| مصطلحات موضوعية: | Computer Science - Data Structures and Algorithms |
| الوصف: | In this paper we describe a fully-dynamic data structure for the planar point location problem in the external memory model. Our data structure supports queries in $O(\log_B n(\log\log_B n)^3))$ I/Os and updates in $O(\log_B n(\log\log_B n)^2))$ amortized I/Os, where $n$ is the number of segments in the subdivision and $B$ is the block size. This is the first dynamic data structure with almost-optimal query cost. For comparison all previously known results for this problem require $O(\log_B^2 n)$ I/Os to answer queries. Our result almost matches the best known upper bound in the internal-memory model. Comment: extended version of a SoCG'19 paper |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/1903.06601 |
| رقم الانضمام: | edsarx.1903.06601 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |