This paper proposes a fast safe-region generation method for several kinds of vicinity queries including set k nearest neighbor (NN) queries, ordered kNN queries, reverse kNN queries, and distance range queries. When a user is driving a car on a road network, he/she wants to know about objects located in the vicinity of the car. However, the result changes according to the movement of the car, and therefore, the user needs to request up-to-date result to the server. On the other hand, frequent requests for up-to-date results cause heavy loadings on the server. To cope with this problem efficiently, the idea of the safe-region has been proposed, however, it takes long processing time in existing works. This paper proposes a fast generation method of the safe-region applicable to several types of vicinity queries. Through experimental evaluations, we demonstrate that the proposed method outperforms the existing algorithms in the processing time by one or two orders of magnitude.