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.2017.30
URN: urn:nbn:de:0030-drops-71897
Go to the corresponding LIPIcs Volume Portal

Cheng, Siu-Wing ; Lau, Man-Kit

Adaptive Planar Point Location

LIPIcs-SoCG-2017-30.pdf (0.5 MB)


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).

BibTeX - Entry

  author =	{Siu-Wing Cheng and Man-Kit Lau},
  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 =	{Boris Aronov and Matthew J. Katz},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{},
  URN =		{urn:nbn:de:0030-drops-71897},
  doi =		{10.4230/LIPIcs.SoCG.2017.30},
  annote =	{Keywords: point location, planar subdivision, static optimality}

Keywords: point location, planar subdivision, static optimality
Collection: 33rd International Symposium on Computational Geometry (SoCG 2017)
Issue Date: 2017
Date of publication: 20.06.2017

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