Localization is one of the fundamental problems for mobile robots. Hence, there are several related works carried out for both metric and topological localization. In this paper, we present a lightweight technique for on-line robot topological localization in a known indoor environment. This approach is based on the Generalized Voronoi Diagram (GVD). The core task is to build local GVD to match against the global GVD using adaptive descriptors. We propose and evaluate a concise descriptor based on geometric constraints around meeting points on GVD, while adopting Hidden Markov Model (HMM) for inference. Tests on real maps extracted from typical structured environment using range sensor are presented. The results show that the robot can be efficiently localized with minor computational cost based on sparse measurements. © 2013 IEEE.