 In many randomized algorithms in computational geometry , the algorithm maintains a history DAG representing the version history of a <unk> structure over the course of a sequence of changes to the structure . For instance in a randomized incremental algorithm for Delaunay triangulation , the triangulation changes by replacing one triangle by three smaller triangles when each point is added , and by " flip " operations that replace pairs of triangles by a different pair of triangles . The history DAG for this algorithm has a vertex for each triangle constructed as part of the algorithm , and edges from each triangle to the two or three other triangles that replace it . This structure allows point location queries to be answered efficiently : to find the location of a query point q in the Delaunay triangulation , follow a path in the history DAG , at each step moving to the replacement triangle that contains q . The final triangle reached in this path must be the Delaunay triangle that contains q . 
