The algorithm given in this chapter to partition a simple polygon into monotone pieces constructs a doubly-connected edge list for the parti- tioned polygon. During the algorithm, new edges are added to the DCEL (namely, diagonals to get rid of split and merge vertices). In general, adding an edge to a DCEL cannot be done in constant time. Discuss why adding an edge may take more than constant time, and argue that in the polygon-partitioning algorithm we can add a diagonal in O(1) time nevertheless.