Dynamic data structures for approximate Hausdorff distance in the word RAM

Timothy M. Chan, Dimitrios Skrepetos

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Pages (from-to)37-44
Number of pages8
JournalComputational Geometry: Theory and Applications
StatePublished - Jan 1 2017
Externally publishedYes


  • Approximation algorithms
  • Dynamic data structures
  • Hausdorff distance

ASJC Scopus subject areas

  • Computer Science Applications
  • Geometry and Topology
  • Control and Optimization
  • Computational Theory and Mathematics
  • Computational Mathematics


Dive into the research topics of 'Dynamic data structures for approximate Hausdorff distance in the word RAM'. Together they form a unique fingerprint.

Cite this