Fast Construction of Nets in Low Dimensional Metrics, and Their Applications

Simple item page
dc.creatorHar-Peled, Sariel
dc.creatorMendel, Manor
dc.date2004-09-29
dc.date2005-08-22
dc.date.accessioned2026-07-07T06:26:51Z
dc.date.available2026-07-07T06:26:51Z
dc.descriptionWe present a near linear time algorithm for constructing hierarchical nets in finite metric spaces with constant doubling dimension. This data-structure is then applied to obtain improved algorithms for the following problems: Approximate nearest neighbor search, well-separated pair decomposition, compact representation scheme, doubling measure, and computation of the (approximate) Lipschitz constant of a function. In all cases, the running (preprocessing) time is near-linear and the space being used is linear.
dc.description41 pages. Extensive clean-up of minor English errors
dc.identifierhttps://arxiv.org/abs/cs/0409057
dc.identifierhttp://arxiv.org/abs/cs/0409057
dc.identifierSIAM J. Comput. 35(5):1148-1184, 2006
dc.identifierdoi:10.1137/S0097539704446281
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/97239
dc.subjectData Structures and Algorithms
dc.subjectComputational Geometry
dc.titleFast Construction of Nets in Low Dimensional Metrics, and Their Applications
dc.typetext

Files

Collections

arXiv