Matching two regions represented in bathymetric data that have some form of geographical overlapping is an important and challenging aspect in underwater mapping. It is important because of the possible error in estimating the geographical location of each point underwater. It is challenging due to the size of the acquired bathymetric data points. The matching could also play a vital role in the registration of underwater images and/or maps fusion, if both bathymetric and intensity scans are considered. Compared to the exhaustive search that requires polynomial time, O(n2), an efficient bathymetric matching algorithm is proposed in this work that finds several matchpoints in linear time, requiring thus O(n) computations. The paper thus presents a new algorithm that allows to compile the bathymetric data of the common areas of two submarine areas that have been sampled in underwater missions.