DROPS

Document

DOI: 10.4230/LIPIcs.SoCG.2020.30

Dynamic Distribution-Sensitive Point Location

Authors: Siu-Wing Cheng and Man-Kit Lau

Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)

Abstract

We propose a dynamic data structure for the distribution-sensitive point location problem. Suppose that there is a fixed query distribution in ℝ², and we are given an oracle that can return in O(1) time the probability of a query point falling into a polygonal region of constant complexity. We can maintain a convex subdivision S with n vertices such that each query is answered in O(OPT) expected time, where OPT is the minimum expected time of the best linear decision tree for point location in S. The space and construction time are O(n log² n). An update of S as a mixed sequence of k edge insertions and deletions takes O(k log⁵ n) amortized time. As a corollary, the randomized incremental construction of the Voronoi diagram of n sites can be performed in O(n log⁵ n) expected time so that, during the incremental construction, a nearest neighbor query at any time can be answered optimally with respect to the intermediate Voronoi diagram at that time.

Cite as

Siu-Wing Cheng and Man-Kit Lau. Dynamic Distribution-Sensitive Point Location. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 30:1-30:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{cheng_et_al:LIPIcs.SoCG.2020.30,
  author =	{Cheng, Siu-Wing and Lau, Man-Kit},
  title =	{{Dynamic Distribution-Sensitive Point Location}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{30:1--30:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-143-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{164},
  editor =	{Cabello, Sergio and Chen, Danny Z.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.30},
  URN =		{urn:nbn:de:0030-drops-121882},
  doi =		{10.4230/LIPIcs.SoCG.2020.30},
  annote =	{Keywords: dynamic planar point location, convex subdivision, linear decision tree}
}

Document

DOI: 10.4230/LIPIcs.SoCG.2017.30

Adaptive Planar Point Location

Authors: Siu-Wing Cheng and Man-Kit Lau

Published in: LIPIcs, Volume 77, 33rd International Symposium on Computational Geometry (SoCG 2017)

Abstract

We present a self-adjusting point location structure for convex subdivisions. Let n be the number of vertices in a convex subdivision S. Our structure for S uses O(n) space and processes any online query sequence sigma in O(n + OPT) time, where OPT is the minimum time required by any linear decision tree for answering point location queries in S to process sigma. The O(n + OPT) time bound includes the preprocessing time. Our result is a two-dimensional analog of the static optimality property of splay trees. For connected subdivisions, we achieve a processing time of O(|sigma| log log n + n + OPT).

Cite as

Siu-Wing Cheng and Man-Kit Lau. Adaptive Planar Point Location. In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 30:1-30:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{cheng_et_al:LIPIcs.SoCG.2017.30,
  author =	{Cheng, Siu-Wing and Lau, Man-Kit},
  title =	{{Adaptive Planar Point Location}},
  booktitle =	{33rd International Symposium on Computational Geometry (SoCG 2017)},
  pages =	{30:1--30:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-038-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{77},
  editor =	{Aronov, Boris and Katz, Matthew J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2017.30},
  URN =		{urn:nbn:de:0030-drops-71897},
  doi =		{10.4230/LIPIcs.SoCG.2017.30},
  annote =	{Keywords: point location, planar subdivision, static optimality}
}

Search Results

Documents authored by Lau, Man-Kit

Dynamic Distribution-Sensitive Point Location

Abstract

Cite as

Adaptive Planar Point Location

Abstract

Cite as

Thanks for your feedback!

Could not send message