= Treemap: An O(log n) Algorithm for Indoor Simultaneous Localization and Mapping =

{{attachment:figure101.jpg|alt mobile robot doing SLAM|width=300}}
{{attachment:figure603.jpg|alt mobile robot doing SLAM|width=300}}
{{attachment:figure605.jpg|alt mobile robot doing SLAM|width=300}}


Treemap has been developed by Udo Frese in his Ph.D. thesis. It is an extremely efficient (O(log n)) algorithm for SLAM that works by dividing the map into local regions and subregions. At each level of the hierarchy each region stores a matrix representing some of the landmarks contained in this region. On the level of finest subdivision, i.e. the lowest level, these matrices are naturally small because the regions are small and contain few landmarks only. On higher levels regions are large and contain many landmarks. For keeping the matrices stored at higher levels small only those landmarks are represented being observable from outside the region. This way it is ensured that even on high levels of hierarchy each matrix represents only few landmarks and computation is efficient. A measurement is integrated into a local subregion using O(k^2^) computation time for k landmarks in a subregion. When the robot moves to a different subregion a global update is necessary requiring only O(k^3^ log n) computation time. Furthermore, the proposed hierarchy allows nonlinear rotation of the matrix stored at a certain region. Thereby linearization problems can be removed. The asymptotic O(log n) expressions assume that the building mapped is topologically well-behaved as is usually the case for indoor environments.

 * [[attachment:fresetalk05treemap.pdf|overview talk]]
 * [[en/TreemapOLogNAlgorithm/Experiment1|real world experiment 1: small map with navigation]]
 * [[en/TreemapOLogNAlgorithm/Experiment2|real world experiment 2: large map mapping only]]

Meanwhile, the treemap algorithm has been redesigned and reimplemented. Refer to the [[en/ClosingAMillionLandmarksLoop|closing a million landmarks loop]] section for these developements.