Let pi , pj , and pk be the three sites that generate this event (from left to right). We delete the arc for pj from the beach line. We create a new vertex in the Voronoi diagram, and tie the edges for the bisectors (pi , pj ), (pj , pk ) to it, and start a new edge for the bisector (pi , pk ) that starts growing down below. Finally, we delete any events that arose from triples involving this arc of pj , and generate new events corresponding to consecutive triples involving pi and pk (there are two of them). For example, suppose that prior to insertion we had the beach-line sequence p1 , pi , pj , pk , p2 . After the event we have the sequence p1 , pi , pk , p2 . We remove any events associated with the triples p1 , pi , pj and pj , pk , p2 . (The event pi , pj , pk has already been removed since we are processing it now.) We also consider the creation of new events for the triples p1 , pi , pk and pi , pk , p2 .