1 Search Results for "Karsin, Ben"

Document
DOI: 10.4230/LIPIcs.ISAAC.2019.58
External Memory Planar Point Location with Fast Updates

Authors: John Iacono, Ben Karsin, and Grigorios Koumoutsos

Published in: LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019)

Abstract
We study dynamic planar point location in the External Memory Model or Disk Access Model (DAM). Previous work in this model achieves polylog query and polylog amortized update time. We present a data structure with O(log_B^2 N) query time and O(1/B^(1-epsilon) log_B N) amortized update time, where N is the number of segments, B the block size and epsilon is a small positive constant, under the assumption that all faces have constant size. This is a B^(1-epsilon) factor faster for updates than the fastest previous structure, and brings the cost of insertion and deletion down to subconstant amortized time for reasonable choices of N and B. Our structure solves the problem of vertical ray-shooting queries among a dynamic set of interior-disjoint line segments; this is well-known to solve dynamic planar point location for a connected subdivision of the plane with faces of constant size.
Cite as

John Iacono, Ben Karsin, and Grigorios Koumoutsos. External Memory Planar Point Location with Fast Updates. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 58:1-58:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{iacono_et_al:LIPIcs.ISAAC.2019.58,
  author =	{Iacono, John and Karsin, Ben and Koumoutsos, Grigorios},
  title =	{{External Memory Planar Point Location with Fast Updates}},
  booktitle =	{30th International Symposium on Algorithms and Computation (ISAAC 2019)},
  pages =	{58:1--58:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-130-6},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{149},
  editor =	{Lu, Pinyan and Zhang, Guochuan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.58},
  URN =		{urn:nbn:de:0030-drops-115548},
  doi =		{10.4230/LIPIcs.ISAAC.2019.58},
  annote =	{Keywords: point location, data structures, dynamic algorithms, computational geometry}
}
  • Refine by Author
  • 1 Iacono, John
  • 1 Karsin, Ben
  • 1 Koumoutsos, Grigorios

  • Refine by Classification
  • 1 Theory of computation → Computational geometry
  • 1 Theory of computation → Data structures design and analysis
  • 1 Theory of computation → Models of computation

  • Refine by Keyword
  • 1 computational geometry
  • 1 data structures
  • 1 dynamic algorithms
  • 1 point location

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2019

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact