> It's not fully private if it requires GPS connection though!!

How so? GPS is like FM radio: you send nothing, you only receive.

Apps like organic maps or comaps let you use the maps fully offline and you can compute itineraries without GPS when your need this (from point A to point B, with as many stops as you wish).

I strongly recommend you to seriously look into comaps or organic maps if you don't know them.

Now, "GPS isn't working or depletes my battery, what do I do?" is an interesting topic worth looking into. It seems you are trying to automate what we all do when GPS doesn't work well. I find that relatively easy in a city, not so much in a road on the countryside.

You are largely correct about everyday location privacy but I was thinking more in the adversarial direction (read military/ GPS denied zones) when I started this work. There have been news about GPS being denied/spoofed over european region. When your phone can't get the GPS signal, it would try to retrieve alternative signals (A-GPS, cellular network etc) - this is where an adversary could be listening for leaks. So GPS denial could effectively be a trigger and the follow ups after that trigger could lead to leaks.

They may be thinking of Google's coarse location feature where the handset checks SSIDs in the proximity against Googles database for fast lookup.