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.2020.30
URN: urn:nbn:de:0030-drops-121882
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12188/
Go to the corresponding LIPIcs Volume Portal

Cheng, Siu-Wing ; Lau, Man-Kit

Dynamic Distribution-Sensitive Point Location

pdf-format:
LIPIcs-SoCG-2020-30.pdf (0.5 MB)

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.

BibTeX - Entry

@InProceedings{cheng_et_al:LIPIcs:2020:12188,
  author =	{Siu-Wing Cheng and Man-Kit Lau},
  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 =	{Sergio Cabello and Danny Z. Chen},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12188},
  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}
}

Keywords: dynamic planar point location, convex subdivision, linear decision tree
Collection: 36th International Symposium on Computational Geometry (SoCG 2020)
Issue Date: 2020
Date of publication: 08.06.2020

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