p = new data point start <- tera + corner if sbove(start, p) start <- start.opp loop start <- start.opp if !above(start ^ 01) start <- start ^01 else if !above(start ^ 01) start <- start ^01 else if !above(start ^ 10) start <- start ^01 else if !above(start ^ 11) start <- start ^01 else break forever 4-1 flip // insert p into tera enqueue Q 4 suspected corners a..d .opp while !empty(Q) c <- pop(Q) ; //c is corner of tetra if sphere(c) does contain p if p inside cone(c) 2-3 flip else if cp is an edge of tetra w {ef,fg,ge} then 3-2 flip (eg. take the edge ef out and put in ^cpg) if 4 tetra around a central point e are made of cpfg then 4-1 flip (rare, only happens if weights are considered cone c is the rectangular cone extending from corner c Data structure * maintain sign of plane's direction Vertex Opposite Plane Sphere a b c d