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
Issue
129
Pages
15
Citation AnalysisPro
You’ll need to upgrade your plan to Pro
Looking to understand the true influence of a researcher’s work across journals & affiliations?
- 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.
Notes
History