Maintaining the Union of Unit Discs Under Insertions with Near-Optimal Overhead

SoCG 2019
Issue: 129, Pages: 15
Published: Jun 17, 2019
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...
Paper Details
Title
Maintaining the Union of Unit Discs Under Insertions with Near-Optimal Overhead
Published Date
Jun 17, 2019
Journal
Issue
129
Pages
15
Citation AnalysisPro
  • Scinapse’s Top 10 Citation Journals & Affiliations graph reveals the quality and authenticity of citations received by a paper.
  • Discover whether citations have been inflated due to self-citations, or if citations include institutional bias.