We design a set of algorithms to construct and visualise unambiguous Gauss maps for a large class of triangulated polyhedral surfaces, including surfaces of non-convex objects and even non-manifold surfaces. The resulting Gauss map describes the surface by distinguishing its domains of positive and negative curvature, referred to as curvature domains. These domains are often only implicitly present in a polyhedral surface and cannot be revealed by means of the angle deficit. We call the collection of curvature domains of a surface the Gauss map signature. Using the concept of the Gauss map signature, we highlight why the angle deficit is sufficient neither to estimate the Gaussian curvature of the underlying smooth surface nor to capture the curvature information of a polyhedral surface. The Gauss map signature provides shape recognition and curvature characterisation of a triangle mesh and can be used further for optimising the mesh or for developing subdivision schemes.