To provide a map data creating device for creating a map data permitting to easily thin out an inner point data from a line, to provide a method therefor, a program therefor, and a recording medium therefor, and also to provide a map output device.

The binary tree map data creating and outputting device 1 of this invention creates a binary tree map data comprising: each coordinate value of a starting point and an end-point in a divided line; the greatest alienation degree among alienation degrees of inner points in the divided line between the starting point and the end-point of this divided line; and parent-child relationship information representing a parent-child relationship which is a correspondent relation between this divided line and the 1st and 2nd dividing lines produced from this divided line, while being made correspondent to each other.