Abstract This paper describes and analyzes a new technique for reasoning about uncertainty called constrained geometric approximation (CGA). We build upon recent work that has developed methods to explicitly represent a robot's knowledge as an element, called an information state, in an appropriately defined information space. The intuition of our new approach is to constrain the I-state to remain in a structured subset of the I-space, and to enforce that constraint using appropriate overapproximation methods. The result is a collection of algorithms that enable mobile robots with extreme limitations in both sensing and computation to maintain simple but provably meaningful representations of the incomplete information available to them. We present a simulated implementation of this technique for a sensor-based navigation task, along with experimental results for this task showing that CGA, compared to a high-fidelity representation of the un-approximated I-state, achieves a similar success rate at a small fraction of the computational cost.