# Node-Based Optimization of GNSS Tomography with a Minimum Bounding Box Algorithm
## 3 New Node-Based Tomographic Approach
### Determination of a Tomographic Region
#### 3.1.1 Convex Hull of the Pierce Points  
In each of the tomographic planes, the Graham scan [29] is used to find the so-called convex hull of the pierce points by efficiently utilizing a stack to detect and remove concavities in the boundary. As shown in Figure 2, the Graham scan procedure mainly includes four steps: (1) Determination of the start point with the lowest y-coordinate. As shown in the top-left panel, the P\({}_{0}\) is the start point. If there is more than one point that exists with the lowest y-coordinate, the point with lowest x-coordinate is the start point. (2) All points except P\({}_{0}\) should be sorted in increasing order of the polar angle. The P\({}_{0}\) is the origin of the polar coordinate, which is so-called pole and the other points have the subscripts of unique sequence number serving as the index (i.e., P\({}_{1}\), P\({}_{2}\), P\({}_{3}\) and P\({}_{4}\)). (3) For each point, the approach needs to make sure that whether the two previously considered points (e.g., P\({}_{0}\) and P\({}_{1}\) in the top-left panel) to this point (e.g., P\({}_{2}\)) is a \"left turn\" or a \"right turn\" and these three points constitute a system to detect the points of the convex hull. \"Left turn\" means that along the direction of the first two points (e.g., P\({}_{0}\) to P\({}_{1}\)) of the system, the last point (e.g., P\({}_{2}\)) on the left side of the direction. Similarly for \"right turn\" the last point of these three points on the right side of the remaining two points' direction. If it is a left turn, the second-to-last point (e.g., P\({}_{1}\) in the top-left panel) is part of the convex hull. As shown in the top-right panel, the approach moves on to the next point in the sorted array and the detection system consists of P\({}_{1}\), P\({}_{2}\) and P\({}_{3}\). The same determination is then made for the system until a \"right turn\" is encountered. In the bottom-left panel, P\({}_{4}\) is a \"right turn\" and this means that the second-to-last point (P\({}_{3}\)) is not at the convex hull and should be removed from the array (stack). (4) Again, determining whether three points constitute a \"left turn\" or a \"right turn\" and this process will eventually return to the start point P\({}_{0}\) and the stack now contains the points on the convex hull in counterclockwise order (i.e., P\({}_{0}\), P\({}_{1}\), P\({}_{2}\) and P\({}_{4}\) in the bottom-right panel).  
Based on the above steps, the convex hull of the points can then be determined, which initially discretizes the tomographic region. First, a tomographic region for a particular epoch (top panel in Figure 3) is divided vertically into several horizontal planes with nonuniform vertical intervals from 300 to 3800 m. The blue points in the bottom panel represent the pierce points of GNSS signals (red lines). After the discretization of the tomographic region in the vertical direction, the convex hulls of the pierce points on all the tomographic planes (i.e., all the black loops in bottom panel) are then defined.  
In classical node parameterization approaches, the rectangular shape for the tomographic region is adopted (shown in Figure 1), from which the nodes' position can be determined easily. In contrast, the tomographic region constructed by the convex hull algorithm is irregular (shown in Figure 3). This irregularity leads to difficulty in uniformly presetting the distribution of the nodes. In order to determine the best balance between the proximity of the distribution of GNSS signals to the nodes and the complexity of the nodes' layout, the minimum bounding box algorithm is used for building the tomographic region. The procedure for this approach is discussed in the next section.