Techniques for providing access point (AP) vicinity information are disclosed. In one example, the techniques include determining a first set of vicinity information corresponding to signal values for an AP at a set of grid points for the coverage area of the AP, encoding the first set of AP vicinity information based at least on a difference between AP vicinity information values for adjacent grid points to generate a second set of AP vicinity information, and providing the second set of AP vicinity information to a device. In one example, the techniques include receiving, for a set of grid points, a first set of AP vicinity information that is compressed based at least on a difference between AP vicinity information values for adjacent grid points, and performing decompression to obtain a second set of AP vicinity information corresponding to signal values for an AP at the set of grid points.