In order for an autonomous unmanned ground vehicle (UGV) to drive in off-road terrain at high speeds, it must analyze and understand its surrounding terrain in realtime: it must know where it intends to go, where are the hazards, and many details of the topography of the terrain. Much research has been done in the way of obstacle avoidance, terrain classification, and path planning, but still so few UGV systems can accurately traverse off-road environments at high speeds autonomously. One of the most dangerous hazards found off-road are negative obstacles, mainly because they are so difficult to detect. We present algorithms that analyze the terrain using a point cloud produced by a 3D laser range finder, then attempt to classify the negative obstacles using both a geometry-based method we call the Negative Obstacle DetectoR (NODR) as well as a support vector machine (SVM) algorithm. The terrain is analyzed with respect to a large UGV with the sensor mounted up high as well as a small UGV with the sensor mounted low to the ground.