How to determine the exact location on a map

November 14, 2023

Designing algorithmic foundations for handling movement data under uncertainty.

Our interactions with the world inherently include movement, and with the growing number and types of trackers, movement data are ubiquitous. However, measurements made by most trackers have an inherent imprecision that may affect the results of analyses. Measurements are also taken periodically, so the location between the measurements is uncertain. During his PhD Aleksandr Popov studied the algorithmic foundations of handling movement data under uncertainty. He defended his thesis on October 12.

The goal of his research was to design efficient algorithms with provable guarantees on their running time and correctness that transparently incorporate movement data uncertainty. The focus lied on trajectories with a specific type of uncertainty: measurement imprecision.

We encounter this in everyday life. Let’s say you’re waiting for a friend who shared their location with you via an app. You likely can follow a dot with a large circle around it on the map; the app is uncertain about your friend’s precise location, so it shows you the most likely area. This imprecision is present in all location data from your phone. For instance, when you are using your phone to help you navigate to a certain destination, the app takes your imprecise data, runs some algorithms, and puts your most likely location on the map. Occasionally, after some time and more data, it calculates that this location is incorrect, and you will see your location on the map suddenly shift a street over.

PhD student Alexander Popov

Google Maps timeline

These are examples of dealing with imprecise data points. We can also think about entire sequences of imprecise data points, and how to analyze them: compare them or simplify them, for instance. Take your Google Maps timeline. If you allowed Google to track your location, you have access to a sequence of locations (which are the result of Google processing your uncertain location data). In other words, you have a sparse sequence of estimated points for a certain period of time.

To create your trajectory for the day, Google needs to extrapolate your position between the consecutive data points, which is why you will sometimes see unnaturally straight lines in your past trajectories. Through more complex methods, the trajectory could look more realistic. In addition, if you look at raw location data, you will find that each measurement comes with a circle around it: the bigger the circle, the less precisely your location was determined.

In particular, Popov studied similarity of imprecise trajectories under an established distance metric called the Fréchet distance. Computing similarity is a fundamental problem, applied as a building block in many analysis tasks, like simplification or clustering. Popov also worked on the problem of simplifying imprecise trajectories, to omit some unimportant measurement without distorting the shape of the path too much. In addition, he studied two related problems that deal with uncertainty: one is related to matching many trajectories to a (city) map efficiently, and the other one relates to visibility in an uncertain setting, to determine if there was a direct line of sight between two objects in an uncertain setting.

Finally, he considered the problem of visibility between sets of points or line segments inside a polygon, showing how to preprocess the polygon to efficiently count how many fixed entities can be seen from a query object. While not directly applicable for imprecise trajectories, this work is a step towards studying visibility under imprecision.

Title of PhD thesis: Algorithms for Imprecise Trajectories

Supervisors: prof. dr. K.A. Buchin (TU Dortmund), prof.dr. Bettina Speckmann (TU/e), dr. ir. Marcel Roeloffzen (TU/e) and Kevin Buchin