  The Random Projection Tree structures proposed in [Freund-Dasgupta STOC08]
are space partitioning data structures that automatically adapt to various
notions of intrinsic dimensionality of data. We prove new results for both the
RPTreeMax and the RPTreeMean data structures. Our result for RPTreeMax gives a
near-optimal bound on the number of levels required by this data structure to
reduce the size of its cells by a factor $s \geq 2$. We also prove a packing
lemma for this data structure. Our final result shows that low-dimensional
manifolds have bounded Local Covariance Dimension. As a consequence we show
that RPTreeMean adapts to manifold dimension as well.
