A fast O(N) multiresolution polygonal approximation algorithm for GPS trajectory simplification.

Area of Science:

• Geoinformatics
• Computer Science

Background:

• Mobile phones generate extensive GPS trajectory data, leading to storage and processing challenges.
• Existing methods for GPS trajectory simplification often lack efficiency or accuracy.

Purpose of the Study:

• To develop a fast and accurate polygonal approximation algorithm for GPS trajectory simplification.
• To address the computational burden of rendering large GPS datasets in web browsers.

Main Methods:

• A bottom-up multiresolution polygonal approximation algorithm in 2-D space.
• Utilizes a priority-queue structure for efficient graph construction and curve initialization.
• Employs fine-tune algorithms to achieve desired quality levels.

Main Results:

• The proposed algorithm achieves linear time complexity for GPS trajectory simplification.
• Demonstrates faster processing speeds compared to existing methods.
• Provides a better approximation quality under the integral square synchronous distance error criterion.

Conclusions:

• The developed algorithm offers an efficient solution for simplifying large GPS trajectory datasets.
• It effectively reduces data storage and computational costs for web-based applications.
• The method presents a significant improvement in speed and approximation accuracy.