Abstract: To study the problem of integrity authentication for vector map data, a fragile watermarking algorithm for locating tampered entity groups is proposed. Firstly, each geographic entity is represented by the midpoint of its minimum bounding rectangles. On this basis, geographic entities are divided into groups using optimized k-means clustering algorithm. Then fragile watermarking is generated through building integrity authentication parameter and combining it with chaotic mapping. Finally, authentication information is embedded in the sorted coordinates. Watermarking detection corresponds to the embedding procedure. Whether the map data have been tampered could be determined by comparing the consistency of the extracted watermarking with the generated watermarking. Experimental results show that the proposed algorithm is able to preserve the accuracy of vector map data effectively and authenticate the integrity of vector map accurately at the same time. Furthermore, the algorithm shows favorable tamper localization ability.