Safety risk evaluation is critical in autonomous vehicle applications. This research aims to develop, implement, and validate new safety monitoring methods for navigation in Global Navigation Satellite System (GNSS)-denied environments. The methods quantify uncertainty in sensors and algorithms that exploit the complementary properties of light detection and ranging (LiDAR) and inertial measuring units (IMU). This dissertation describes the following four contributions. First, we focus on sensor augmentation for landmark-based localization. We develop new IMU/LiDAR integration methods that guarantee a bound on the integrity risk, which is the probability that the navigation error exceeds predefined acceptability limits. IMU data improves LiDAR position and orientation (pose) prediction and LiDAR limits the IMU error drift over time. In addition, LiDAR return-light intensity measurements improve landmarks recognition. As compared to using the sensors individually, tightly-coupled IMU/LiDAR not only increases pose estimation accuracy but also reduces the risk of incorrectly associating perceived features with mapped landmarks. Second, we consider algorithm improvements. We derive and analyze a new data association method that provides a tight bound on the risk of incorrect association for LiDAR feature-based localization. The new data association criterion uses projections of the extended Kalman filter's (EKF) innovation vector rather than more conventional innovation vector norms. This method decreases the integrity risk by improving our ability to predict the risk of incorrect association. Third, we depart from landmark-based approaches. We develop a spherical grid-based localization method that leverages quantization theory to bound navigation uncertainty. This method is integrated with an iterative EKF to establish an analytical bound on the vehicle's pose estimation error. Unlike landmark-based localization which requires feature extraction and data association, this method uses the entire LiDAR point cloud and is robust to extraction and association failures. Fourth, to validate these methods, we designed and built two testbeds for indoor and outdoor experiments. The indoor testbed includes a sensor platform installed on a rover moving on a figure-eight track in a controlled lab environment. The repeated figure-eight trajectory provides empirical pose estimation error distributions that can directly be compared with analytical error bounds. The outdoor testbed required another set of navigation sensors for reference truth trajectory generation. Sensors were mounted on a car to validate our algorithms in a realistic automotive driving environment. / Doctor of Philosophy / Advances in computing and sensing technologies have enabled large scale demonstrations of autonomous vehicle operations including pilot programs for self-driving cars on public roads. However, a key question that has yet to be answered is about how safe these vehicles really are. "Autonomously" driving millions of miles (with a trained safety driver taking over control to prevent potential collisions) is insufficient to prove fatality rates matching human performance, i.e., lower than 1 per 100,000,000 miles driven. The safety of an autonomous vehicle depends on the safety of its individual subsystems, components, connected infrastructure, etc. In this research, we evaluate the safety of the navigation subsystem which uses sensor information to determine the vehicle's location and orientation. We focus on light detection and ranging (LiDAR)and inertial measuring units (IMU). A LiDAR provides a point cloud representation of the environment by measuring distances to surrounding objects using beams of infrared light (laser beams) sent at regular angular intervals. An IMU measures the acceleration and angular velocity of the vehicle. We assume that a map of the environment is available. In the first part of this research, we extract recognizable objects from the LiDAR point cloud and match them with those in the map: this process helps estimate the vehicle's position and orientation. We identify the process' limitations that include incorrectly matching sensed and mapped landmarks. We develop new methods to quantify their impacts on localization errors, which we then reduce by incorporating additional IMU data. In the second part of this dissertation, we design and evaluate a new approach specifically aimed at provably increasing confidence in landmark matching, thereby improving vehicle navigation safety. Third, instead of isolating individual landmarks, we use the LiDAR point cloud as a whole and match it directly with the map. The challenge with this approach was in efficiently and accurately quantifying the confidence that can be placed in the vehicle's navigation solution. We tested these navigation methods using experimental data collected in a controlled lab environment and in a real-world scenario.