Autonomous map construction is one of the most fundamental and significant issues in intelligent mobile robot research. While a variety of map construction methods have been proposed, most require some quantitative measurements of the environment and a mechanism of precise self-localization. This paper proposes a novel map construction method using only qualitative information about "how often two objects are observed simultaneously." This method is based on heuristics--"closely located objects are likely to be seen simultaneously more often than distant objects" and a well-known multivariate data analysis technique-multidimensional scaling. A significant feature of this method is that it requires neither quantitative sensor measurements nor information about the robot's own position. Simulation and experimental results demonstrated that this method is sufficiently practical for capturing a qualitative spatial relationship among identifiable landmark objects rapidly.