This article presents a new algorithm to recognize natural distinctive places such as corridors, halls, narrowings, corridors with open doors on the left side etc., from indoor environments using Hidden Markov Models. The environment is modelled as a graph. This graph is obtained from a Voronoi Diagram from measurements of laser scanner. The characteristics of Voronoi Diagram (nodes, number of edges adjacent to nodes, slope of edges etc. ) are used to learn and recognize the different places.