This paper presented a new DCT-based watermarking algorithm for vector digital maps. A watermark bit is embedded by modifying the relationship of several high-frequency coefficients in DCT domain. To enhance data accuracy and robustness of the watermark, we proposed a Double Error Estimation method. This method allowed watermarks to be embedded when the vertices with distortion are smaller than thresholds. Experiments show that the watermarks are resilient to random noise, general geometric transformation, data scrambling and cropping. The algorithm is blind and it is easy to implement.