As location-based services have become popular, thereby exposed user locations raised serious privacy concerns. A typical measure for location privacy is to report blurred locations and ensure that other users coexist in the reported region. However, additional knowledge about the user's maximum speed and the territorial information in user's vicinity can allow for the adversary to effectively compromise the user's location privacy. In this paper, we present an anonymization algorithm that effectively counters such attacks while achieving k -anonymity requirements as well as minimum acceptable cloaked region size. We evaluate our anonymization scheme using state-of-the-art simulators for both vehicular movements and pedestrian movements. The experimental results demonstrate the effectiveness and efficiency of our proposed algorithm.