. Thus, by applying union bounds on theΘ(n1/3k1/3)groups, we get that with probability atleast 1 (n

LetM,y()be matching and set of dual weights that are feasible. The left-most line is given by x = iδ andYi = {x = iδ+jθδ | 0 j < t 1}. For any vertical lineyi Y, any edge of length at most δ that crosses yi will have its end points betweenyi 1 and yi+1. Therefore, if yi is chosen as a vertical line forG, then µi will be an upper bound on the number of boundary vertices whose edges crossyi. Thus, ifYi is chosen as the set of vertical lines ofG, then µ(Yi) will be an upper bound on the number of boundary vertices created inGdue to the vertical lines.