An optimal vertex adjustment method is presented for vertex-based shape coding. The method optimally shifts the vertices, selected by a conventional vertex selection method, within the window that satisfies the allowable maximum distortion using a Viterbi algorithm. Experimental results show that the proposed method reduces the approximation distortion of the contour by similar to 30% for the same rate over a wide range of distortion, compared with the conventional method.