I'm surprised that GPS and geofences has nothing to do with internet connections. I installed an App (EgiGeoZone) from the playstore, and made many geofences to get notifications. When my internet was on it was working well, but when my internet was turned off, I would receive notifications from various places that were not geofenced. Maybe you can give me some clue on how to improve precision without internet connection ? That would be very helpfull. Thanks for your comment :)