This still leaves the point location time to improve. We can store the history of the splits and flips performed: each triangle stores a pointer to the two or three triangles that replaced it. To find the triangle that contains "v", we start at a root triangle, and follow the pointer that points to a triangle that contains "v", until we find a triangle that has not yet been replaced. On average, this will also take O(log "n") time. Over all vertices, then, this takes O("n" log "n") time. While the technique extends to higher dimension (as proved by Edelsbrunner and Shah), the runtime can be exponential in the dimension even if the final Delaunay triangulation is small.