Performance Analysis of Route Segmentation Algorithm in Identifying Perimeter Area Around Travel Route

Navigation apps such as Google Maps have no direct way to search for Points of Interest (POI) along an entire travel route, only around a single point. The existing RouteBoxer approach runs at O(n³) complexity, making it slow for long routes. This study proposes RouteSegmentation: generating perimeter polygons (a rectangle plus a half-circle) along each route segment, then merging them via polygon union operations, at O(n) complexity.

There is no efficient way to identify the perimeter area along an entire travel route (rather than a single point) for POI search, because the existing RouteBoxer approach is too slow (O(n³)) for routes with many points.

RouteSegmentation builds a perimeter polygon along each route segment (a rectangle capped with a half-circle), then merges all polygons into one continuous perimeter area using three compared union strategies: Overlay Union, Unary Union, and Cascaded Union.

Tested on a 10.1 km route in Malang City (350 points from the Google Maps Directions API), split into 70 route subsets ranging from 5 to 350 points. Each subset was measured 30 times (2,100 measurements total) on an Android emulator (4-core CPU, API 34).

Segment generation averaged under 1 millisecond. Unary Union and Cascaded Union both outperformed Overlay Union in execution time and memory usage, a statistically significant result (Wilcoxon test, p<0.001).

Introduces RouteSegmentation as an O(n) alternative to RouteBoxer for identifying the perimeter area along a travel route, enabling POI search along an entire route rather than just around a single point.

Unpredictable garbage collector behavior affected the accuracy of memory measurements during the experiment.