R-Map: A hybrid map created by maximal rectangles

While there has been substantial research on the integration of grid-based and topological maps, no previous approach, to our knowledge, has considered constructing hybrid maps applying the maximal empty rectangle problem found in computational geometery. We propose a hybrid map, R-Map, which is built by extracting a topological information out of a grid map by a simple rule; Find the largest free rectangular area recursively in a given area. The experiment results show R-Map can produce a good representation of an environment, efficiently reducing space complexity with a limited number of rectangles and clearly showing free and non-free space.