We develop novel algorithms based on interval analysis with theoretical guarantees, to augment the accuracy of cell phone geolocation by taking advantage of local variations of magnetic intensity. Thus, the sources of disturbances to magnetometer readings caused indoors are effectively used as beacons for localization. We construct a magnetic intensity map for an indoor environment by collecting magnetic field data over each floor tile. We then test the algorithms without position initialization and obtain indoor geolocation to within 2 m while slowly walking over a complex path of 80 m. The geolocation errors are smaller in the vicinity of large magnetic disturbances. Finally, we fuse the magnetometer measurement with inertial measurements on the cell phone to yield even smaller geolocation errors of under 50 cm for a moving user. Our theoretical results connect geolocation accuracy to combinations of sensor and map properties. (C) 2014 Elsevier Ltd. All rights reserved.