地球上水上或陆地上最长直线路径（2018）

# 地球表面最长直线航行或陆地行进路径
来源：https://arxiv.org/html/1804.07389
Rohan Chabukswar††thanks:ChabukR@utrc\.utc\.com Kushal Mukherjee††thanks:KushMukh@in\.ibm\.com 所属单位：IBM Research India

###### 摘要
近年来，人们对于确定地球上无需触及陆地可航行的最长距离，以及反向问题——确定无需遇到大型水域可行驶的最长距离——产生了一定兴趣。其基本形式是一个优化问题，由于岛屿、湖泊以及海岸线的分形特性而变得复杂混沌。本文提出一种使用分支定界算法计算这两种路径的方法。

## 1 引言
2012年12月29日，Reddit用户kepleronlyknows在r/MapPorn板块发布了一张地图（图1：https://arxiv.org/html/1804.07389#S1.F1）\[1 (https://arxiv.org/html/1804.07389#bib.bib1)\]，显示了从巴基斯坦到俄罗斯东部无需触及陆地可航行的地球表面最长直线。这引发了广泛关注，并导致后续用户试图证明或反驳该结果，同时关于求解在陆地上不遇到大型水体可行驶最长距离的反向问题也展开了讨论。

![图1：kepleronlyknows在r/MapPorn发布的原始地图](图1)
从基本形式看，这两个问题都是二维空间中的优化问题——然而，由于岛屿（对于最长可航行路径）和湖泊（对于最长可行驶路径）的存在，目标函数是不连续的。全局最优解需要对整个二维空间进行穷举搜索，这在时间和内存方面都是不可忽视的障碍。按照美国国家海洋和大气管理局ETOPO1地球表面地形模型提供的1弧分分辨率（赤道处约1.855公里），需考虑233,280,000个大圆才能找到全局最优解，且每个大圆需处理21,600个独立点——总计需要验证惊人的5,038,848,000,000个点。

### 1.1 先前工作
除了kepleronlyknows发现的最长可航行路径外，Reddit用户Groke也发布了一条从挪威到南极洲的无陆地直线路径\[2 (https://arxiv.org/html/1804.07389#bib.bib2)\]，该路径短于从巴基斯坦到俄罗斯东部的路径。YouTube用户David Cooke声称\[3 (https://arxiv.org/html/1804.07389#bib.bib3)\]发现了一条更长的路径（"库克航道"），从魁北克到不列颠哥伦比亚，但该路径后来在航海图平台GeoGarage的博客文章中被证实\[4 (https://arxiv.org/html/1804.07389#bib.bib4)\]并非直线。

IT/GIS咨询服务公司的Guy Bruneau计算得出\[5 (https://arxiv.org/html/1804.07389#bib.bib5)\]一条从中国东部到利比里亚西部的路径为两点间直线行驶且不穿过任何大洋或主要水体的最长距离。然而，该路径穿过了死海（可被视为主要水体），因此不满足最初设定的约束条件。

## 2 问题陈述
因此，为证明或反驳kepleronlyknows的结果，并找到陆地上不穿越大型水体的最长直线路径，作者开始系统性地寻求问题的全局最优解。

建立问题所需的全球陆地/水体数据并非 readily available。最终使用的数据集是ETOPO1全球地形模型\[6 (https://arxiv.org/html/1804.07389#bib.bib6)\]，将任何负海拔视为水域，正海拔视为陆地。尽管这在一般情况下并不完全准确，但在缺乏实际数据的情况下，这是最接近真实地形的免费可用近似。

### 2.1 ETOPO1全球地形模型
ETOPO1是1弧分分辨率的地球表面全球地形模型，整合了陆地地形和海洋测深数据。它基于众多全球和区域数据集构建，提供“冰面”（南极和格陵兰冰盖表面）和“基岩”（冰盖底部）两种版本。适用于本问题的是“冰面”版本，因为可航行路径不应触及冰层，且从技术上讲冰层可供车辆行驶。

### 2.2 优化
问题的真正关键在于全局求解优化问题。在初步尝试对路径进行暴力搜索未果后，作者决定采用分支定界算法。

## 3 问题形式化
形式化问题的第一步是实现枚举地球上不同直线路径的方法。为此需注意所有直线路径都位于一个大圆上。每个大圆可包含与陆地-水域边界的所有交点一样多的路径，但由于我们仅关注每个大圆中最长的路径（陆地或水域），枚举所有大圆即可。这可以通过观察任何大圆（赤道本身除外）与赤道相交于两个对跖点且成特定角度来系统性地完成。除赤道这一特例外，可通过选择与赤道交点的经度（“原点”）以及大圆在该点与赤道的夹角（“航向”）来枚举，两者均可在0°至360°之间选择。但这会使得每个大圆被计数四次，因此实际选择可限制在每个参数0°至180°之间。大圆上的每个点可通过该点在大圆平面内相对于参考向量（可任意设为原点）的角度来定位。该角度φ的范围是0°至360°。

因此，由原点δ和航向α定义的任何大圆可表示为GC(δ,α)。

为匹配以米为单位的各经纬度高程给出的ETOPO1数据集，每个大圆GC(δ,α)上的点φ需转换为纬度β和经度λ，这可通过基本球面三角学实现：
β = arcsin(sinα sinφ),  (1)
λ = δ + atan2(cosα sinφ, cosφ),  (2)
其中atan2(y,x)是四象限反正切函数。

遍历每个由(β,λ)定义的大圆，所遇到的地形高度r_{(δ,α)}(φ), φ∈(-180°,180°]由下式给出：
r_{(δ,α)}(φ) = etopo1(arcsin(sinα sinφ), δ + atan2(cosα sinφ, cosφ))  (3)
例如，如图2所示，GC(163°44′,151°22′)同时穿过挑战者深渊（11°20′N,142°12′E，距原点24°12′角距离）和珠穆朗玛峰（27°59′N,86°56′E，距原点78°22′角距离）。

![图2：穿过地球最低点和最高点的大圆](图2)
沿该大圆遇到的地形高度r_{(163°44′,151°22′)}(φ), φ∈(-180°,180°]如图3a所示。

![图3a：实际地形](图3a)
![图3b：陆地/水域分类](图3b)
图3：沿穿过地球最低点和最高点大圆的地形高度。根据每条大圆的地形高度，可应用海平面以上正负高度表示陆地和水域的假设来分类大圆的每个点：
land_{(δ,α)}(φ) = 
  1 若 r_{(δ,α)}(φ) > 0
  0 若 r_{(δ,α)}(φ) < 0
  不确定 若 r_{(δ,α)}(φ) = 0. (4)
在搜寻最长水域路径时，保守地将不确定情况（r_{(δ,α)}(φ)=0）视为陆地；在搜寻最长陆地路径时则视为水域。对于示例大圆，land_{(163°44′,151°22′)}(φ), φ∈(-180°,180°]如图3b所示。

分类完成后，即可轻松确定大圆中最长的陆地和水域路径，它们构成了需要最大化的目标函数。

## 4 分支定界法
分支定界法是求解组合优化问题的方法，尤其适用于能为解空间中子集的目标函数确定边界的情况。

对于本文讨论的问题，我们继续用唯一标识大圆的角度对GC(δ,α)表示。一个解集指一组大圆轨迹，它们与赤道交于纬度δ_min至δ_max之间，航向范围为α_min至α_max。我们将该集合表示为[δ_min,δ_max]×[α_min,α_max]。每个大圆GC(δ,α)有对应的长度l(δ,α)，定义为沿大圆可航行且不触及陆地的最大距离。

### 4.1 松弛技术
下一个任务是获取所有大圆中δ∈[δ_min,δ_max]、α∈[α_min,α_max]条件下，最长连续水域段l(δ,α)的上界。

###### 定理1
将GC((δ_min+δ_max)/2,(α_min+α_max)/2)视为δ∈[δ_min,δ_max]、α∈[α_min,α_max]大圆集合的代表，则该代表大圆与集合中任何其他大圆的最大角距离始终不超过
‖(δ_max−δ_min)/2‖ + ‖(α_max−α_min)/2‖.

###### 证明
令θ=(α_max+α_min)/2, Δθ=α_max−α_min, Δφ=δ_max−δ_min。利用球面三角学，它们之间的最大角距离为
arccos(cos(Δθ)·cos²(Δφ/2)+cos(2θ)·sin²(Δφ/2)).
这在实际应用中较复杂，但最大偏差出现在θ=90°时，且理论上界为√(Δθ²+Δφ²)（当Δθ,Δφ→0°时）。即使Δθ,Δφ=45°，该极限的精度也达2.62%。由于已知‖Δθ‖+‖Δφ‖≥√(Δθ²+Δφ²)，角距离始终被该值限制，即
‖(δ_max−δ_min)/2‖ + ‖(α_max−α_min)/2‖.  ∎

将大圆GC((δ_min+δ_max)/2,(α_min+α_max)/2)视为大圆集合的代表。根据定理1，代表大圆与集合中任何其他大圆的最大距离始终不超过R·(‖(δ_max−δ_min)/2‖+‖(α_max−α_min)/2‖)，其中R为地球半径。

我们方法的创新之处在于评估最长连续水域段上界的方法。设存在大圆GC(δ_o,α_o)，其中δ_o∈[δ_min,δ_max]且α_o∈[α_min,α_max]，它具有最长的连续水域段。
l(δ_o,α_o) = max_{δ∈[δ_min,δ_max],α∈[α_min,α_max]} l(δ,α). (5)
这意味着：
l(δ,α) ≤ max_{δ∈[δ_min,δ_max],α∈[α_min,α_max]} l(δ,α), ∀δ∈[δ_min,δ_max],α∈[α_min,α_max]. (6)
进一步考虑地球，其海域向陆地侵蚀了距离ε。在这个新地球（ε-侵蚀地球）上，陆地面积从各侧缩减了距离epsilon。所有距海域距离在ε以内的陆地部分都被ε-地球上的海域覆盖。