Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH scholarly article en Oh, Eunjin; Ahn, Hee-Kap License
when quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-87769


Point Location in Dynamic Planar Subdivisions



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

  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 =		{},
  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
Seminar: 34th International Symposium on Computational Geometry (SoCG 2018)
Issue date: 2018
Date of publication: 2018

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