License
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://drops.dagstuhl.de/opus/volltexte/2018/9999/
Go to the corresponding LIPIcs Volume Portal


Oh, Eunjin

Point Location in Incremental Planar Subdivisions

pdf-format:
LIPIcs-ISAAC-2018-51.pdf (0.5 MB)


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
Seminar: 29th International Symposium on Algorithms and Computation (ISAAC 2018)
Issue Date: 2018
Date of publication: 27.11.2018


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI