Finding your place on a map as quickly as you could tell someone where you are

I have a new preprint, "Distance-Sensitive Planar Point Location" (arXiv:1602.00767, with Aronov, de Berg, Roeloffzen, and Speckmann) whose title and abstract may already be a bit intimidating. So I thought I would at least try to explain what it's about in simpler terms.

Point location is something you do every time you orient yourself on a map. You know where you are, in the world, and you try to figure out what that means about where you are on the map. Let's model the map mathematically as a unit square, subdivided into polygons. You already know the coordinates of a point in the square, but now you want to figure out which polygon contains that point. To do so, you might make a sequence of comparisons, for instance checking which side of one of the polygon edges you're on. You want to do as few comparisons as possible before getting the answer.

One limit on the number of comparisons you might need is entropy, a fancy word for the number of bits of information you need to send to someone else to tell them where you are. If you can solve point location in a certain number of comparisons, you can also say where you are by communicating the results of those comparisons. So, the entropy is no bigger than the time complexity of point location. We'd like to turn that around, by finding methods for point location that match any method you might come up with for communicating your location. For instance, if there are \( n \) different polygons on your map, you could name them by strings of \( \log_2 n \) bits, and communicate your location by saying one of those names. And it turns out that there are methods of point location that take only \( O(\log n) \) comparisons, so we can match this naming scheme by a point location method.

But there are other naming schemes that might do even better than that, and we'd like to also match them. For instance, you might be in some places more frequently than others. Most of the time, I'm in California, and when I'm outside California I'm more likely to be in states where I have relatives or that are the frequent sites of computer science conferences (say, Massachusetts) than others (say, Maine). So it would be more efficient on the average for me to tell people where I am using a naming scheme in which California has a very short name and South Dakota has a longer one. Several researchers, including Iacono, Arya, Malamatos, and Mount, have provided point location schemes that can match the complexity of any such naming scheme. But to achieve this, they require all of the polygons to have simple shapes like triangles, not complicated ones like the boundaries of some US states.

In our paper, we use a different idea. Instead of considering the popularity of different regions, we consider the distance to the nearest boundary. If you're far from the boundary of a region, it should be easy to tell where you are, and if you're close to the boundary you'll have to look more carefully. If your distance to the nearest boundary is \( d \), then you're inside a circle that doesn't cross any boundary and whose area is proportional to \( d^2 \). There can be only \( O(1/d^2) \) polygons that contain a circle that big, and you can communicate which one you're in by sending \( O(\log 1/d^2) \) bits of information (a name of one of those big polygons). A simple point location scheme based on a quadtree data structure turns out to match that bound.

That's a warmup to the main results of the paper, which combine popularity with distance to the boundary. If you're well within a polygon, at the center of a circle that's inside the polygon and has area proportional to it, then the time to find out where you are is proportional only to the length of the name of the polygon (in your favorite naming scheme) regardless of how complicated its shape is. But if you're closer to the boundary than that, then the time to locate yourself will be slower, by a number of steps that depends inverse-logarithmically on how close you are.

It would be nice to have a method that depends only on the lengths of the names of the polygons, without assuming they're all nicely shaped, and without depending on other quantities like the distance to the boundary. But that's not possible, as an example in our introduction details. For, if there are only two polygons on your map (say polygon 0 and polygon 1), then the lengths of both of their names are constant. If we want to match that by the complexity of a point location scheme, then we can only make a constant number of comparisons, and only solve location problems for which the shapes of the polygons are simple.

Comments: