Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4949141 | Computational Geometry | 2017 | 8 Pages |
Abstract
We give a fully dynamic data structure for maintaining an approximation of the Hausdorff distance between two point sets in a constant dimension d, a standard problem in computational geometry. Our solution has an approximation factor of 1+ε for any constant ε>0 and expected update time O(logâ¡Ulogâ¡logâ¡n), where U is the universe size, and n is the number of the points. The result of the paper greatly improves over the previous exact method, which required O(n5/6polylogn) time and worked only in a semi-online setting. The model of computation is the word RAM model.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Timothy M. Chan, Dimitrios Skrepetos,