Local Doubling Dimension of Point Sets

Choudhary, Aruni; Kerber, Michael

Item

ITEM ACTIONSEXPORT

Add to Basket

Local TagsRelease HistoryDetailsSummary

Released

Conference 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

http://www.cccg.ca/proceedings/2015/03.pdf
(Any fulltext)

Fulltext (restricted access)

There are currently no full texts shared for your IP range.

Fulltext (public)

There are no public fulltexts stored in PuRe

Supplementary Material (public)

There is no public supplementary material available

Citation

Choudhary, A., & Kerber, M. (2015). Local Doubling Dimension of Point Sets. In Proceedings of the 27th Canadian Conference on Computational Geometry (pp. 156-164). Kingston: Queen’s University School of Computing.

Cite as: https://hdl.handle.net/11858/00-001M-0000-002C-501B-B

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.