With the popularity of location-based services and the abundant use of smartphones and GPS-enabled devices, the need to outsource spatial data has grown rapidly in recent years. Meanwhile, the rapid trend of cloud storage and cloud computing services has provided a flexible and cost-effective platform for hosting business and home data, while also allowing for many location-based applications. However, in this database outsourcing paradigm, authentication of query results on the client remains a difficult problem. In this work, we focus on the subcontracted spatial database model (OSDB) and propose an efficient scheme, called VN-Auth, that allows the client to verify the correctness and integrity of the result set. Our approach is based on the neighbourhood information derived from the Voronoi diagram of the underlying spatial data set and can handle fundamental spatial query types such as nearest neighbor and range queries as well as more advanced query types such as inverse k Nearest neighbor, nearest neighbor Neighbour and space. We evaluated VN-Auth based real-world datasets using mobile devices (Google Droid smartphones with Android OS) as query clients. Compared with current approaches to the prior art (ie methods based on Merkle Hash Trees), our experiments show that VN-Auth produces significantly smaller verification objects and is more computationally efficient, especially For queries with low selectivity.