Dynamic data structures for approximate Hausdorff distance in the word RAM

Timothy M. Chan; Dimitrios Skrepetos

doi:10.1016/j.comgeo.2016.08.002

Dynamic data structures for approximate Hausdorff distance in the word RAM

Research output: Contribution to journal › Article › peer-review

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(n^5/6polylogn) time and worked only in a semi-online setting. The model of computation is the word RAM model.

Original language	English (US)
Pages (from-to)	37-44
Number of pages	8
Journal	Computational Geometry: Theory and Applications
Volume	60
DOIs	https://doi.org/10.1016/j.comgeo.2016.08.002
State	Published - Jan 1 2017
Externally published	Yes

Keywords

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

Online availability

10.1016/j.comgeo.2016.08.002

Library availability

Discover UIUC Full Text

Cite this

@article{8632ebc1cf6f4033a7f6cf9b0ace5bf5,

title = "Dynamic data structures for approximate Hausdorff distance in the word RAM",

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.",

keywords = "Approximation algorithms, Dynamic data structures, Hausdorff distance",

author = "Chan, {Timothy M.} and Dimitrios Skrepetos",

note = "Publisher Copyright: {\textcopyright} 2016 Elsevier B.V.",

year = "2017",

month = jan,

day = "1",

doi = "10.1016/j.comgeo.2016.08.002",

language = "English (US)",

volume = "60",

pages = "37--44",

journal = "Computational Geometry: Theory and Applications",

issn = "0925-7721",

publisher = "Elsevier",

}

TY - JOUR

T1 - Dynamic data structures for approximate Hausdorff distance in the word RAM

AU - Chan, Timothy M.

AU - Skrepetos, Dimitrios

PY - 2017/1/1

Y1 - 2017/1/1

N2 - 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.

AB - 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.

KW - Approximation algorithms

KW - Dynamic data structures

KW - Hausdorff distance

UR - http://www.scopus.com/inward/record.url?scp=84994152023&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84994152023&partnerID=8YFLogxK

U2 - 10.1016/j.comgeo.2016.08.002

DO - 10.1016/j.comgeo.2016.08.002

M3 - Article

AN - SCOPUS:84994152023

SN - 0925-7721

VL - 60

SP - 37

EP - 44

JO - Computational Geometry: Theory and Applications

JF - Computational Geometry: Theory and Applications

ER -

Dynamic data structures for approximate Hausdorff distance in the word RAM

Abstract

Keywords

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this