Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT
Zur Ablage hinzufügen
  Lokale TagsFreigabegeschichteDetailsÜbersicht

Freigegeben
Konferenzbeitrag

Local Doubling Dimension of Point Sets

MPG-Autoren
/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;

Externe Ressourcen

http://www.cccg.ca/proceedings/2015/03.pdf
(beliebiger Volltext)

Volltexte (beschränkter Zugriff)
Für Ihren IP-Bereich sind aktuell keine Volltexte freigegeben.
Volltexte (frei zugänglich)
Es sind keine frei zugänglichen Volltexte in PuRe verfügbar
Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

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.


Zitierlink: https://hdl.handle.net/11858/00-001M-0000-002C-501B-B
Zusammenfassung
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.