Before revision: I.e. TSD construction takes with high probability {\cal O}( n \ln n) time and TSD size can be made worst case {\cal O}(n) with an expected rebuild cost of {\cal O}( 1). The proposed analysis technique also shows that the expected depth is {\cal O}( \ln n ), which partially solves a recent conjecture by\emph{ [  Hemmer et al. that is used in the CGAL implementation of the TSD [ .
After revision: I.e. TSD construction takes with high probability {\cal O}( n \ln n) time and TSD size can be made worst case {\cal O}(n) with an expected rebuild cost of {\cal O}( \log n), and iii) a construction time of {\cal O}( \ln n ), which partially solves a recent conjecture by\emph{ [ Hemmer et al. that is used in the CGAL implementation of the TSD [ .