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.2019.26
URN: urn:nbn:de:0030-drops-104307
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/10430/
Agarwal, Pankaj K. ;
Cohen, Ravid ;
Halperin, Dan ;
Mulzer, Wolfgang
Maintaining the Union of Unit Discs Under Insertions with Near-Optimal Overhead
Abstract
We present efficient data structures for problems on unit discs and arcs of their boundary in the plane. (i) We give an output-sensitive algorithm for the dynamic maintenance of the union of n unit discs under insertions in O(k log^2 n) update time and O(n) space, where k is the combinatorial complexity of the structural change in the union due to the insertion of the new disc. (ii) As part of the solution of (i) we devise a fully dynamic data structure for the maintenance of lower envelopes of pseudo-lines, which we believe is of independent interest. The structure has O(log^2 n) update time and O(log n) vertical ray shooting query time. To achieve this performance, we devise a new algorithm for finding the intersection between two lower envelopes of pseudo-lines in O(log n) time, using tentative binary search; the lower envelopes are special in that at x=-infty any pseudo-line contributing to the first envelope lies below every pseudo-line contributing to the second envelope. (iii) We also present a dynamic range searching structure for a set of circular arcs of unit radius (not necessarily on the boundary of the union of the corresponding discs), where the ranges are unit discs, with O(n log n) preprocessing time, O(n^{1/2+epsilon} + l) query time and O(log^2 n) amortized update time, where l is the size of the output and for any epsilon>0. The structure requires O(n) storage space.
BibTeX - Entry
@InProceedings{agarwal_et_al:LIPIcs:2019:10430,
author = {Pankaj K. Agarwal and Ravid Cohen and Dan Halperin and Wolfgang Mulzer},
title = {{Maintaining the Union of Unit Discs Under Insertions with Near-Optimal Overhead}},
booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)},
pages = {26:1--26:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-104-7},
ISSN = {1868-8969},
year = {2019},
volume = {129},
editor = {Gill Barequet and Yusu Wang},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10430},
URN = {urn:nbn:de:0030-drops-104307},
doi = {10.4230/LIPIcs.SoCG.2019.26},
annote = {Keywords: lower envelopes, pseudo-lines, unit discs, range search, dynamic algorithms, tentative binary search}
}
|
Keywords: |
|
lower envelopes, pseudo-lines, unit discs, range search, dynamic algorithms, tentative binary search |
|
Collection: |
|
35th International Symposium on Computational Geometry (SoCG 2019) |
|
Issue Date: |
|
2019 |
|
Date of publication: |
|
11.06.2019 |
