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
Go to the corresponding LIPIcs Volume Portal

Oh, Eunjin

Point Location in Incremental Planar Subdivisions

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


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

  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 =		{},
  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

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