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.51
URN: urn:nbn:de:0030-drops-72198
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7219/
Go to the corresponding LIPIcs Volume Portal

Oh, Eunjin ; Ahn, Hee-Kap

Dynamic Geodesic Convex Hulls in Dynamic Simple Polygons

pdf-format:
LIPIcs-SoCG-2017-51.pdf (0.6 MB)

Abstract

We consider the geodesic convex hulls of points in a simple polygonal region in the presence of non-crossing line segments (barriers) that subdivide the region into simply connected faces. We present an algorithm together with data structures for maintaining the geodesic convex hull of points in each face in a sublinear update time under the fully-dynamic setting where both input points and barriers change by insertions and deletions. The algorithm processes a mixed update sequence of insertions and deletions of points and barriers. Each update takes O(n^2/3 log^2 n) time with high probability, where n is the total number of the points and barriers at the moment. Our data structures support basic queries on the geodesic convex hull, each of which takes O(polylog n) time. In addition, we present an algorithm together with data structures for geodesic triangle counting queries under the fully-dynamic setting. With high probability, each update takes O(n^2/3 log n) time, and each query takes O(n^2/3 log n) time.

BibTeX - Entry

@InProceedings{oh_et_al:LIPIcs:2017:7219,
  author =	{Eunjin Oh and Hee-Kap Ahn},
  title =	{{Dynamic Geodesic Convex Hulls in Dynamic Simple Polygons}},
  booktitle =	{33rd International Symposium on Computational Geometry (SoCG 2017)},
  pages =	{51:1--51: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 =		{http://drops.dagstuhl.de/opus/volltexte/2017/7219},
  URN =		{urn:nbn:de:0030-drops-72198},
  doi =		{10.4230/LIPIcs.SoCG.2017.51},
  annote =	{Keywords: Dynamic geodesic convex hull, dynamic simple polygons}
}

Keywords: Dynamic geodesic convex hull, dynamic simple polygons
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