Enhancing the Efficiency of Navigation Systems: Dijkstra Algorithm Optimization Through Integration of Douglas-Peucker Line Simplification Technique
Muhammad Yasir Anshari Haq, Riswan Septriayadi Sianturi, Aryo Pinandito · 2023
Smartphones have grown popular in the current digital era among people. Map-based applications are one of many that are used daily by people to acquire information about specific locations. Google Maps and Waze are two popular examples of map-based applications for travel and navigation, as they provide detailed information while the user navigates from one point to another. One of the most commonly used algorithms in map-based applications is the Dijkstra algorithm. Although the Dijkstra algorithm can determine the shortest route between two points, there is an issue when the selected route involves a large number of data points that need to be processed. The more data points involved, the longer it takes to do a route calculation in the Dijkstra algorithm. This can lead to a degradation in system performance, especially on smartphones with limited resources. To address this issue, the Douglas-Peucker algorithm is proposed as a solution to reduce the number of points involved in the calculation using the line simplification technique. Line simplification means reducing unnecessary points that are considered unimportant. This study suggested that integrating the Douglas-Peucker line simplification technique before Dijkstra could improve the system performance more than the system without integrating line simplification in terms of reducing both memory usage and the time required to compute the solution.