JACM23 - A New Algorithm for Euclidean Shortest Paths in the Plane

本文关注的问题为计算几何学中的经典问题，即「在平面上给定一组两两不相交的多边形障碍物，寻找两点之间避开所有障碍物的欧几里得最短路径」，简单理解就是「含多边形障碍物的两点最短路问题」。

令 $n$ 表示所有障碍物的顶点数，$h$ 表示障碍物的总数，针对该问题的主要算法发展历程如下所示：

	Time Complexity	Space Complexity
Hershberger and Suri, SIAM J. COMPUT. 1999	$O(n\log n)$	$O(n\log n)$
Wang, SODA 2021	$O(n\log n)$	$O(n)$
Wang, JACM 2023	$O(n+h\log h)$	$O(n)$

本篇工作将时间复杂度从之前的 $O(n\log n)$ 提升到了 $O(n+h\log h)$，基于的前提条件为「在算法开始执行之前，已经为自由空间（即除去所有障碍物后的平面部分）构建了一个三角剖分」。

三角剖分 (Triangulation) 即一种将平面分割成不重叠的三角形的方法，且这些三角形覆盖整个自由空间。

当 $n\ll h$ 时，本文所提算法对比先前方法提升较明显（最坏情况下 $h=\Theta(n)$），例如如下场景：

此外，如果将三角剖分的时间也算上的话，时间复杂度将会变为 $O(n+h\log^{1+\epsilon}h)$，for any constant $\epsilon>0$.

Introduction

首先形式化一下问题：

令 $\mathcal{P}$ 为一组包含 $h$ 个平面上两两不相交的多边形障碍物，共有 $n$ 个顶点；
令 $\mathcal{F}$ 为自由平面 (Free Space)，即原始平面减去所有障碍物的内部空间；
给定 $\mathcal{F}$ 中的两个点 $s$ 和 $t$，问题被形式化为「在 $\mathcal{F}$ 中找到从 $s$ 到 $t$ 的欧几里得最短路径」。

上述问题有两个变体：

Single shortest path problem：$s$ 和 $t$ 都已在 input 中给出
Single-source-shortest-paths：$s$ 是给定的源点，$t$ 是 query 点，需要建立数据结构高效解决每次不同的 query

该问题有两种常用的方法：

Visibility Graph Method
- 该方法需要先构建 Visibility 图，即包含障碍物所有顶点以及起点和终点的图，并连接节点间与障碍物不相交的边。构建完 Visibility 图后，可以直接运行 Dijkstra 最短路算法完成求解。
- 该类方法的复杂度为 $O(n \log n + K)$，其中 $K$ 表示 Visibility 图中边的数量，在最坏情况下 $K=\Omega(n^2)$。
- 此类方法只能用于 Single shortest path problem.
Continuous Dijkstra Method
- 基本思想是模拟从源点出发的 Wavefront 在自由空间中的传播。Wavefront 可以想象为一组以源点为中心、不断扩展的同心圆，表示到源点的等距离点集。
- 在传播过程中，算法会构建最短路径图 (Shortest Path Map)，即 $SPM(s)$。当给定一个目标点 $t$ 时，$s$ 与 $t$ 之间的最短距离可以在 $O(\log n)$ 内计算得到。
- $O(n^{3/2+\epsilon})$ time, Mitchell, SoCG 1993
- $O(n\log n)$ time, $O(n\log n)$ space, Hershberger and Suri, FOCS 1993
- 此类方法也可以解决 Single-source-shortest-paths，即使用 $O(n)$ space (SODA’21) 构建 $SPM(s)$，并在 $O(\log n)$ 时间内解决每次 query。

$SPM(s)$ 构建完成后，$\mathcal{F}$ 将会被切分为多个区域，$s$ 距区域内每个点的最短路都将经过该区域的根结点（对于 Wavefront 来说，即圆心），如下图所示：

Main Result

$O(n+h\log h)$ time
- Match $\Omega(n+h\log h)$ lower bound
- Space: $O(n)$
- Compute a shortest path map $SPM(s)$
- Assumption: a triangulation of the space is given
  - Triangulation: $O(n+h\log^{1+\epsilon}h)$ time, Bar-Yehuda and Chazelle, IJCGA 1994
Main idea
- Follow Hershberger and Suri’s main algorithm framework
- Continuous Dijkstra’s approach
- Use a smaller conforming subdivision of the free space
- Use Wang’s technique to reduce the space to O(n)

Review of the HS algorithm (Hershberger and Suri)

The difficulty of continuous Dijkstra: how to maintain the wavefront (consisting of all points with the same distance from s)
- a sequence of wavelets, each centered at an obstacle vertex, called a generator (shortest path from s to every point of the wavelet through its generator)
- a wavefront is represented by a list of generators

A conforming subdivision $S$ of the free space (the HS algorithm)

HS 算法的基础是需要先将一个复杂的几何区域（即自由平面）切分为多个简单区域的集合（如四边形区域），如下图所示。这个过程称为 Conforming subdivision，具体所使用的算法为 quad-tree-style subdivision of the plane（四叉树划分）。

下图中展示的是 1-conforming subdivision of free space，即 $d(e,f)\geq \max(1|e|,1|f|)$. HS 算法基于的则是 2-conforming subdivision, 即 $d(e,f)\geq \max(2|e|,2|f|)$.

Well-covering region $U(e)$ 的定义要求它包含透明边 $e$, 并且它的边界与 $e$ 之间的距离满足一定的最小距离约束条件, 即其他边与 $e$ 的距离至少是 $2 \times \max \{|e|,|f|\}$ 。换句话说，边界上的边与 $e$ 的距离足够大，以便波前在 $U(e)$ 内部不会被远离它的其他边过早影响。

通过定义 $U(e)$，可以确保只需要考虑该区域内的波前扩展，而无需处理更远区域的波前。因此，$U(e)$ 提供了一个局部的计算空间，简化了复杂的全局波前交互问题。

在满足这些条件的前提下, 算法倾向于选择面积最小的区域 $U(e)$, 以便最有效地进行计算。这意味着, 对于每个透明边 $e$ 来说, 虽然理论上可以有多个区域满足 $U(e)$ 的定义, 但算法会选择一个面积最小、最紧凑的区域来优化计算。

Using $S$ to guide the wavefront expansion

Bisector events

Bisector 是两个 wavelets 之间的角平分线，而 Bisector events 则代表 wavelets 的消失，通常有如下两种情况。

Reducing time to $O(n+h\log h)$

Reduce the problem to the convex case by a corridor structure
Solve the convex case: all obstacles are convex
By generalizing the HS algorithm

令 $V$ 表示每个障碍物上 X 和 Y 轴上达到极值的顶点 (Rectilinear Extreme Vertices) 集合，$|V|=O(h)$，如下图中黄色点所示。

计算 a conforming subdivision $S(V)$ of $V$ 的时间复杂度为 $O(h\log h)$，其中 $S(V)$ 的大小为 $O(h)$.
$V$ 中顶点将每个 obstacle boundary 切分为最多四个 convex chains（如下图红线所示），其总数也为 $O(h)$.

在本文算法中，each convex chain 被视作一个 “unit”. Insert these convex chains into $S(V)$ to obtain a comforming subdivision $S(F)$ of the free space, 时间复杂度为 $O(n+h\log h)$.

Conforming subdivision $S(F)$ of the free space (the new algorithm)

Each cell of $S(F)$ is a square or a square annulus (i.e., an outer square with an inner square hole).
Each vertex of $V$ is contained in the interior of a square cell and each square cell contains at most one vertex of $V$.
The boundary $\partial c$ of each cell $c$ in $S$ consists of $O(1)$ transparent edges (非障碍物的边) and $O(1)$ convex chains.

Wavelet of a convex chain

A generator is a couple $\alpha=(A,a)$，其中 $A$ 是 elementary chain，$a$ 是 $A$ 上的一个障碍物点
Wavelet is not of $O(1)$ size anymore, but can be implicitly determined
A wavelet generated by a generator $\alpha = (A,a)$ at time $\tau$ is a contiguous set of reachable points $q$ such that $d(\alpha, q) = \tau$ and $d(\alpha’, q) \geq \tau$ for all other generators $\alpha’$ in the wavefront.
A wavalet actually consists of a contiguous sequence of circular arcs centered at the obstacle vertices（如下图所示）.

A bisector of two convex chains

Bisector is not of $O(1)$ size anymore, can be implicityly determined by the two convex chains.
The bisector between the wavelets of two generators $\alpha$ and $\alpha’$ , denoted by $B(\alpha,\alpha’)$, consists of points $q$ with $d(\alpha, q)=d(\alpha’,q)$.
如下图所示，$B(\alpha, \alpha’)$ has multiple pieces each of which is a hyperbola defined by two obstacle vertices $v\in \alpha$ and $v’\in \alpha’$ such that the hyperbola consists of all points that have two shortest paths from $s$ with $v$ and $v’$ as the anchors, respectively.

Issues: some operations on bisectors may not be solved in $O(1)$ time
- Compute the intersection of two bisectors
- Compute the intersection between a bisector and an obstacle
This algorithm: $O(\log n)$ time using the tentative prune-and-search technique (Kirkpatrick and Snoeyink, 1995)

Wavefront propagation in a cell of $S(F)$

Sweep a line from bottom upwards and process events

Wavefronts of the other three edges of the cell will be obtained after all events are processed

Wavefront propagation in a non-empty cell of $S(F)$

The left/right side of the cell is a convex chain on the boundary of an obstacle
A new generator may be created at the tangent point $q’$

Reducing the general case to the convex case

If the convex hulls of all obstacles are disjoint:

compute the convex hulls
compute shortest path map outside convex hulls
extend map into those pockets (障碍物凸壳内的空白部分) through their gates（绿色边）
- the key subproblem

The key subproblem: Extend the shortest path map into a pocket through its gate cd

$m$: number of vertices of the map on cd
$N$: number of vertices of the pocket
$G$: number of vertices on the generators
$O(m \log m+N+G)$ time and $O(m+N+G)$ space to extend the map into the pocket
Over all pockets
- $\sum m=O(h)$
- $\sum N=O(n)$
- $\sum G=O(n)$
Total complexity for all pockets: $O(n+h \log h)$ time and $O(n)$ space