Doctor of Philosophy(PhD) / This thesis is concerned with the theoretical and practical development of a surface-based mapping algorithm for reliable and robust localization and mapping in prior unknown and unstructured environments. A surface-based map consists of a set of compressed surfaces, processed and represented without geometrical modelling. Each surface in the surface-based map represents an object in the environment. The ability to represent the exact shapes of objects via individual surfaces during the mapping process makes the surface-based mapping algorithm valuable in a number of navigation applications, such as mapping of prior unknown indoor and outdoor unstructured environments, target tracking, path planning and collision avoidance. The ability to unify representations of the same object taken from different viewpoints into a single surface makes the algorithm capable of working in multi-robot mapping applications. A surface-based map of the environment is build incrementally by acquiring the 3D range image of the scene, extracting the objects' surfaces from the 3D range image, aligning the set of extracted surfaces relative to the map and unifying the aligned set of surfaces with surfaces in the map. In the surface unification process the surfaces representing the same object are unified to make a single surface. The thesis introduces the following new methods which are used in the surface-based mapping algorithm: the extraction of surfaces from 3D range images based on a scanned surface continuity check; homogenization of the representation of the non-homogenously sampled surfaces; the alignment of the surface set relative to a large set of surfaces based on surface-based alignment algorithm; evaluating the correspondence between two surfaces based on the overlap area between surfaces; unification of the two surfaces belonging to the same object; and surface unification for a large set of surfaces. The theoretical contributions of this thesis are demonstrated with a series of practical implementations in different outdoor environments.