dc.rights.license | CC-BY-NC-ND | |
dc.contributor.advisor | Löffler, Dr. M. | |
dc.contributor.advisor | van Kreveld, Prof. Dr. M. | |
dc.contributor.author | Hoog, I.D. van der | |
dc.date.accessioned | 2017-08-30T18:01:12Z | |
dc.date.available | 2017-08-30T18:01:12Z | |
dc.date.issued | 2017 | |
dc.identifier.uri | https://studenttheses.uu.nl/handle/20.500.12932/27088 | |
dc.description.abstract | We present an approximation data structure to maintain a set of \emph{fat} regions in $\mathbb{R}^2$ subject to fast insertions and deletions of the regions, stabbing queries, local replacement. Local replacement is a new concept where we replace a region with a region that is "similar" to the original region. We elaborate on earlier result obtained by Löffler, Strash and Simons which shows that it is possible to have a linear size data structure that supports insertions, deletions and stabbing queries in logarithmic time and local replacement in sub-logarithmic time, if the regions are disjoint. We also discuss another earlier result from Löffler and Khramtcova where they present a data structure that supports these operations for overlapping intervals in $\mathbb{R}^1$, where the time bounds for our desired operations depend on the maximum overlap (\emph{ply}) of the intervals. We prove that this approach cannot be extended to $\mathbb{R}^2$ and continue with introducing a data structure that supports approximate queries. Our data structure can support $\epsilon$-approximate stabbing queries, for $\epsilon = \frac{1}{2^m + 1}$ in $\mathcal{O}(m + \log(n))$ time and local replacement in $\mathcal{O}(2^{m}\log(\log(n)))$ time. Lastly we present a theorem that says that no reduction proof from the problem of stabbing queries with sub-logarithmic local replacement in $\mathbb{R}^2$ to binary search can exist. Our approximation bounds show that a logarithmic lower bound for stabbing queries with local replacement is likely, but our results show that proving this lower bound through a reduction to binary search or heap operations is infeasible. | |
dc.description.sponsorship | Utrecht University | |
dc.format.extent | 1206212 | |
dc.format.mimetype | application/pdf | |
dc.language.iso | en | |
dc.title | Dynamic Stabbing Queries with Sub-logarithmic Local Replacement for Overlapping Regions in R^2. | |
dc.type.content | Master Thesis | |
dc.rights.accessrights | Open Access | |
dc.subject.keywords | Stabbing, data, structure, reduction, algorithm, geometry, quadtrees | |
dc.subject.courseuu | Computing Science | |