English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
Add to Basket
  Local TagsRelease HistoryDetailsSummary

Released
Paper

Local Doubling Dimension of Point Sets

MPS-Authors
/persons/resource/persons129030

Choudhary,  Aruni
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

/persons/resource/persons44759

Kerber,  Michael
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)

arXiv:1406.4822.pdf
(Preprint), 191KB

Supplementary Material (public)
There is no public supplementary material available
Citation

Choudhary, A., & Kerber, M. (2014). Local Doubling Dimension of Point Sets. Retrieved from http://arxiv.org/abs/1406.4822.


Cite as: https://hdl.handle.net/11858/00-001M-0000-0024-4779-1
Abstract
We introduce the notion of t-restricted doubling dimension of a point set in Euclidean space as the local intrinsic dimension up to scale t. In many applications information is only relevant for a fixed range of scales. We present an algorithm to construct a hierarchical net-tree up to scale t which we denote as the net-forest. We present a method based on Locality Sensitive Hashing to compute all near neighbours of points within a certain distance. Our construction of the net-forest is probabilistic, and we guarantee that with high probability, the net-forest is supplemented with the correct neighbouring information. We apply our net-forest construction scheme to create an approximate Cech complex up to a fixed scale; and its complexity depends on the local intrinsic dimension up to that scale.