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.SoCG.2018.63
URN: urn:nbn:de:0030-drops-87769
URL: https://drops.dagstuhl.de/opus/volltexte/2018/8776/
Oh, Eunjin ;
Ahn, Hee-Kap
Point Location in Dynamic Planar Subdivisions
Abstract
We study the point location problem on dynamic planar subdivisions that allows insertions and deletions of edges. In our problem, the underlying graph of a subdivision is not necessarily connected. We present a data structure of linear size for such a dynamic planar subdivision that supports sublinear-time update and polylogarithmic-time query. Precisely, the amortized update time is O(sqrt{n}log n(log log n)^{3/2}) and the query time is O(log n(log log n)^2), where n is the number of edges in the subdivision. This answers a question posed by Snoeyink in the Handbook of Computational Geometry. When only deletions of edges are allowed, the update time and query time are just O(alpha(n)) and O(log n), respectively.
BibTeX - Entry
@InProceedings{oh_et_al:LIPIcs:2018:8776,
author = {Eunjin Oh and Hee-Kap Ahn},
title = {{Point Location in Dynamic Planar Subdivisions}},
booktitle = {34th International Symposium on Computational Geometry (SoCG 2018)},
pages = {63:1--63:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-066-8},
ISSN = {1868-8969},
year = {2018},
volume = {99},
editor = {Bettina Speckmann and Csaba D. T{\'o}th},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8776},
URN = {urn:nbn:de:0030-drops-87769},
doi = {10.4230/LIPIcs.SoCG.2018.63},
annote = {Keywords: dynamic point location, general subdivision}
}
|
Keywords: |
|
dynamic point location, general subdivision |
|
Collection: |
|
34th International Symposium on Computational Geometry (SoCG 2018) |
|
Issue Date: |
|
2018 |
|
Date of publication: |
|
08.06.2018 |
