hide
Free keywords:
Computer Science, Computational Geometry, cs.CG,Mathematics, Algebraic Topology, math.AT
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.
