Negative obstacles have long been a challenging aspect of autonomous navigation for ground vehicles. However, as terrestrial lidar sensors have become lighter and less costly, they have increasingly been deployed on small, low-flying UAV, affording an opportunity to use these sensors to aid in autonomous navigation. In this work, we develop an analytical model for predicting the ability of UAV or UGV mounted lidar sensors to detect negative obstacles. This analytical model improves upon past work in this area because it takes the sensor rotation rate and vehicle speed into account, as well as being valid for both large and small view angles. This analytical model is used to predict the influence of velocity on detection range for a negative obstacle and determine a limiting speed when accounting for vehicle stopping distance. Finally, the analytical model is validated with a physics-based simulator in realistic terrain. The results indicate that the analytical model is valid for altitudes above 10 m and show that there are drastic improvements in negative obstacle detection when using a UAV-mounted lidar. It is shown that negative obstacle detection ranges for various UAV-mounted lidar are 60–110 m, depending on the speed of the UAV and the type of lidar used. In contrast, detection ranges for UGV mounted lidar are found to be less than 10 m.