Cutting redundant points from a route made one map algorithm almost 88 times quicker.
Map applications answer more questions than directions. A travel app also wants to know what sits near the road you are about to take, so it can suggest a restaurant, a fuel station, or a landmark. On an Android map, that surrounding area search is handled by an algorithm called RouteBoxer, and it has a scaling problem.
RouteBoxer receives a list of geographic points that describe a path, plus a distance to search away from it. It lays a grid of rectangles over the area that covers the whole path, then walks along the path and marks every rectangle the route passes near. The result is a set of boxes the app can query for nearby places.
The cost scales with the number of points it has to traverse. Feed it a recording from a phone that captured a coordinate every second, and the grid work becomes unacceptably slow.
The researchers inserted a simplification step ahead of the search. The Douglas-Peucker algorithm redraws a path using fewer points while keeping its shape, discarding coordinates that sit close to a straight line between their neighbours. A curvy recorded track becomes a handful of well placed corners.
The measured effect was large. Simplification removed up to 99 percent of the points in a path. The original RouteBoxer calculation ran up to 87.8 times faster. Precision stayed above 92.6 percent, meaning the boxes still covered the route well enough to be useful.
The lesson generalises beyond this one algorithm. When a routine is slow because of how much it receives, the cheapest fix is often to send it less rather than to rewrite it.
Aryo Pinandito and Chandrawati Putri Wulandari (2021). Integrating Douglas-Peucker Line Simplification into Routeboxer Algorithm on a Map-Based Android Application. Proceedings of the 5th International Conference on Sustainable Information Engineering and Technology.
