## 2 Background  
Map construction is the process of generating street maps from moving objects' traces, such as GPS coordinates. The final output is usually represented as an embedded graph. Map-construction algorithms can be categorized into point clustering, incremental track insertion, and intersection linking [1].  
Point clustering regards trajectories as sets of points, and generates maps by clustering these points [8]. A K-means clustering algorithm is employed to cluster the input points [9]. The centers of the clusters are connected after the clusters have been refined. An image-processing technique is applied to generate a map [10]. The total length of the trajectory is calculated for each cell across the rectangular grid for all map areas. Then, Gaussian blur is applied to remove small gaps caused by GPS noise. Next, the polygon boundaries of the road area are extracted, and a road center-line is created. However, this algorithm is density based and its accuracy depends on the size of the grid cells created on the map. Furthermore, outliers in the datasets have a negative effect on the generation of maps in density-based algorithms.  
The incremental track-insertion algorithm inserts tracks into an empty graph based on map-matching ideas [11]. The incremental construction of the map, such as the addition or deletion of tracks, is based on distance measurements and vehicle headings [1]. For example, the previous research [4] proposes two steps in the map-construction algorithm. First, the algorithm identifies a portion of the trajectory that exists on the currently partitioned map. This partitioned map is generated using the Frechet-distance transformation method. The next step inserts inconsistencies into the current map by adding new boundary points and borders as needed. The algorithm requires only the time and \(\delta\) parameters to split the trajectory, where the \(\delta\) parameter is the minimum distance between roads and the minimum distance between two intersections. This algorithm has significant advantages when the trajectory added at all stages is correct, but the disadvantage of adding the wrong trajectory has a negative effect on the overall results. Similarly, study [12] proposes a map-construction algorithm that completes the graph in two steps: preprocessing and clarification. The preprocessing step reduces the straight part of the oversampled trajectory while dividing the wrong trajectory and preserving the sample of the high curvature. The clarification step decreases the effect of noise on the input trajectory by using a forced algorithm to clean the initial data.  
Lastly, intersection-linking algorithms first detect intersection vertices and then construct edges using these vertices [1]. Intersections are identified based on movement characteristics (speed, direction) or point density. For instance, study [13] identifies potential turning points according to changes in the direction and speed. Next, the cross node obtained from the input trajectory is connected to the edge. This algorithm is highly useful when the vertex is part of an intersection.  
These aforementioned methods predominantly focus on vehicle data to generate street maps. This study deals with ship movement data. Moreover, FDA has not yet been applied to construct maps. Our approach utilizes FDA to not only remove outliers from ship trajectories, but also to produce shipping routes. The following section explains the details of the proposed method.