Before revision:  It is well known that this point location structure has {\cal O}(n) expected size and {\cal O} (n \ln n) expected construction time.
After revision:  It is well known that this point location structure has {\cal O}(n) expected size. Moreover, searching takes w.h.p. {\cal O} (n \ln n) expected construction time.