License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2018.51
URN: urn:nbn:de:0030-drops-99991
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9999/
Oh, Eunjin
Point Location in Incremental Planar Subdivisions
Abstract
We study the point location problem in incremental (possibly disconnected) planar subdivisions, that is, dynamic subdivisions allowing insertions of edges and vertices only. Specifically, we present an O(n log n)-space data structure for this problem that supports queries in O(log^2 n) time and updates in O(log n log log n) amortized time. This is the first result that achieves polylogarithmic query and update times simultaneously in incremental planar subdivisions. Its update time is significantly faster than the update time of the best known data structure for fully-dynamic (possibly disconnected) planar subdivisions.
BibTeX - Entry
@InProceedings{oh:LIPIcs:2018:9999,
author = {Eunjin Oh},
title = {{Point Location in Incremental Planar Subdivisions}},
booktitle = {29th International Symposium on Algorithms and Computation (ISAAC 2018)},
pages = {51:1--51:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-094-1},
ISSN = {1868-8969},
year = {2018},
volume = {123},
editor = {Wen-Lian Hsu and Der-Tsai Lee and Chung-Shou Liao},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9999},
URN = {urn:nbn:de:0030-drops-99991},
doi = {10.4230/LIPIcs.ISAAC.2018.51},
annote = {Keywords: Dynamic point location, general incremental planar subdivisions}
}
|
Keywords: |
|
Dynamic point location, general incremental planar subdivisions |
|
Collection: |
|
29th International Symposium on Algorithms and Computation (ISAAC 2018) |
|
Issue Date: |
|
2018 |
|
Date of publication: |
|
06.12.2018 |
