Sensor-based construction of different geometric structures has been an important development in the domain of autonomous robot navigation. This paper presents a hardware-efficient scheme to construct one such geometric structure, namely, the generalized Voronoi diagram (GVD), using a prediction-and-correction strategy. In this paper, an architecture to construct the GVD for an indoor environment with multiple obstacles whose geometry and location are not known beforehand is presented. A feature of the proposed approach is that it does not involve operations that are expensive in hardware. Furthermore, no explicit angle computation circuitry is needed. An efficient architecture based on hardware reuse is presented. The design is shown to be space efficient and fits in a low-end field-programmable gate-array (FPGA) device (with a small number of system gates). Detailed experiments with a mobile robot fabricated locally with a Xilinx XC2S200E FPGA and eight ultrasonic sensors onboard validate the efficacy of the proposed approach for static as well as dynamic environments. © 2008 IEEE.