For obstacles, the most common map is an occupancy grid map. The environment is discretized into voxels (of arbitrary size) that are either free or have an obstacle. This is imprecise - a slightly better solution is to mark each voxel with the probability it has an obstacle. You can store this information efficiently in a K-DTree . Then you do some absolute thresholding to determine if the voxel is free or not.
Highly efficient for planning, but bad at representing small objects.