# Fréchet Gap Distance
[Fréchet distance筆記](https://zhuanlan.zhihu.com/p/20159963)
[Fréchet distance論文](https://webspace.science.uu.nl/~kreve101/asci/ag-cfdbt-95.pdf)
## Introduction
* 找出兩條線有多「相似」的其中一個標準是「量測兩條線的距離」
* 其中一個量測距離數學式子是 Hausdorff-distance，但以下的例子有很小的Hausdorff-distance，卻一點也不「相似」：
會有這樣的情況是因為，Hausdorff-distance只考慮兩條曲線上點的集合，而沒有反應曲線的走向。
* 所以之後提出了一個擁有保向重參數化特性的演算法：Fréchet metric δ~F~
## Definition
* 令 V 為任意的 Euclidean vector space
* 一個曲線是一個連續的 mapping  且 a < b
* 一個polygon curve 則對於所有的 P[i, i+1]都是affine
* 令 f:[a, a']->V, f:[b, b']->V 為兩條曲線，則兩者的Fréchet distance定義為
其中 α 和 β 範圍於連續且單調增加的函數，其中α(0)=a，α(1)=a'，β(0)=b，且β(1)=b'。
* **inf**(S)，定義為小於等於在 S 中的所有數的最大實數。
* 例子：inf{1,2,3}=1
* δ~F~顯然是對稱的，且可以證明三角不等式成立，且在保向重參數化下是不變的。
> **decision problem**:
*Given*: polygon curves P and Q and some ε ≥ 0
*Decide*: whether δ~F~(P, Q) ≤ ε
## Computing Fréchet Distance
* 以下定義通用整篇論文：
```
令 P:[0,p] -> V, Q:[0,q] -> V 為兩條曲線。
其中 P 有 p 個邊，Q 有 q 個邊
```
Fig. 2.為 p=1, q=1 的例子:
定義 $F~ε~:=\{(s,t)\in[0,1]^2|d(P(s),Q(t))\leε\}$
描述 F~ε~ 為所有距離 ≤ ε 的 point pairs, 其中 s 在 P 上，t 在 Q 上。
Fig. 2.右邊稱為 free space diagram，F~ε~是白色區域。灰色區域的 point pairs 距離 > ε
---
將問題延伸(P和Q不只有一個線段)，也就是：
$F~ε~:=\{(s,t)\in[0,p]\times[0,q]|d(P(s),Q(t))\leε\}$
將 [0,p] x [0,q] 當作由 pq 個格子(**cells**) C~ij~ := [i-1,i] x [j-1,j] 組成，其中 1 ≤ i ≤ p, 1 ≤ j ≤ q。
很明顯地，F∩C~ij~ 與原定義相對應，表示相對於邊界 P(i-1)P(i) 和邊界 Q(j-1)Q(j) 的自由空間的交集。
# Folding Free-Space Diagrams: Computing the Fréchet Distance between 1-Dimensional Curves
大綱：利用free-space diagram解決Fréchet distance(狗繩問題)
>Fréchet distance就是狗绳距离：主人走路径A，狗走路径B，各自走完这两条路径过程中所需要的最短狗绳长度。
>The Frechet distance is a measure of similarity between two curves, P and Q. It is defined as the minimum cord-length sufficient to join a point traveling forward along P and one traveling forward along Q, although the rate of travel for either point may not necessarily be uniform.
[論文網址](https://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7241)
[影片網址](https://www.computational-geometry.org/SoCG-videos/socg17video/videos/1DFrechet.mp4)
## I Introduction
## why we can solve this problem by folding?
當對折時，便是Ｐ、Ｑ碰上了轉折點，也就是Ｐ或Ｑ轉向，相對轉折前的情況是相同的，沿著對折線兩邊的解是對稱的，因此可以用對折來解決問題。
因為我們將一維展開成二維，我們的Ｐ上任一點可以對應到Ｑ上所有點，所以我們可以忽略掉兩者的速度不同的問題。
## Contribution
* 這篇論文相信其中一條曲線重複訪問同一點的次數k是有限制的，而另一條沒有限制。這將帶來O(nk log n)的運算時間
* 而本篇論文運用他們發明的free-space diagram可以觀察到：將曲線折疊以找到更清楚的表示法，且時間複雜度能縮短到**O(n(k + log n))**
* 在1D中，k-packed曲線具有Θ(k)的厚度。
* near-linear approximation algorithms for k-packed curves: 用於解決高維空間的幾何問題。
* k-packed curves：將高維空間中的物體映射至低維空間。
後面有點難懂，之後再回來看
## Preliminaries
* 1D 曲線 P 以 n+1 個頂點 <p0, ..., pn> 表示
* 曲線會在每個頂點改變方向
* p~i~ $\in R$
* n = number of edges
* 以 |P| 表示 P 的幾何長度（路徑長）。
* p~i~表示第i 個折返點的絕對位置。
* 以 |p~i~| = $\sum_{j=1}^i$|p~j-1~ - p~j~| 表示到 pi 之前的線段總長。所以 |p~0~| = 0, |p~n~| = |P|
* 令 P 是一個連續函數 $P:[0,|P|]\to {\displaystyle \mathbb {R} }\ with\ P(|p_i|)=p_i$
* 曲線P的厚度 *ply* 是 $max_{r\in{\displaystyle \mathbb {R} }}|P^{-1}(r)|=max_{r\in{\displaystyle \mathbb {R} }}|\{t|t\in[0,|P|]\wedge P(t)=r
\}|$
ply
: r代表在座標上的絕對位置，t代表當位置在r時的路徑長，如下圖，當r = 8時，t = 8 or 10 or 20，有三個解，因此ply = 3。
free-space diagram
: free-space diagram F 代表兩條曲線的parameter space。
* [0, |P |] × [0, |Q|] diagram.
* point (s, t) $\in$ F: a pair of curves point P(s), Q(t)
* (s, t) $\in$ F is **free** if |P (s) − Q(t)| $\le$ $\epsilon$
* the union of free points is the free space of F.(白色區塊)
* 若一個monotone path從(0, 0)到(s, t)存在於free space, 則(s, t) $\in$ F is **reachable**
* monotone path: 訪問每個點但不與自身交叉的路徑，此外每個點的y座標必須嚴格遞增或遞減。
* 每條P的邊組成free-space diagram的column的寬，Q的邊為row的高。
* d~F~(P, Q) $\le \epsilon$ holds if and only if (|P|,|Q|) is reachable in F
**-5/7新增-**
`因為在1D兩條線不是以同向就是以反向移動，所以free space的boundaries只可能為斜率=1或-1的直線`
Fréchet distance的d~F~
: 給兩條polygon curve Ｐ和Ｑ，d~F~(P, Q)定義為在Ｐ、Ｑ上有兩個物體，都依不變的速率(但兩者的速率不盡相同)，沿著Ｐ和Ｑ移動，該移動的Ｐ、Ｑ之間最大距離便是d~F~(P, Q)。
## II Folding free-space diagrams
### 為何可以對折?
1. 挑選一個P的頂點 p~i~ 以及Q的任意點 q
2. 當一個點 p 在線段 p~i-1~p~i~ 上，另一點 p' 在 p~i~p~i+1~ 上，且 p 和 p' 距離p~i~的距離都相同。根據mininality, p=p'
3. 因此若 $|p-q|\le\epsilon$ iff $|p-q'|\le\epsilon$。p~i~對應free space diagram的一條垂直線，在此垂直線(折線)的兩邊是彼此的鏡射。
### 找出basic cell
將所有的row和column對折可以得到這張圖
再將所有的basic cell展開得到這張圖
### 所以有甚麼好處?
原本畫free space diagram要花二次的時間O(n^2^)
透過對折的操作可以縮短到線性時間(看第三節)
## III 證明
### Theorem 1
>令P跟Q是1D曲線且兩條線總共有n個頂點
令Q的厚度ply=k
確認是否 d~F~(P, Q) $\le \epsilon$ 的時間複雜度為 $O(n(k+log\ n))$
而計算 d~F~(P, Q) 在 $O(nklog n)$ 的時間內
對折所有的column，但不要對折row
我們得到infinite line和Q之間的free-space structure
考慮Q上的點q，其中對於某個r ∈ R，滿足$\parallel q-r\parallel$ ≤ ε
我們只考慮沿著infinite line的*maximaal interval*，每個interval都被Q上的兩條邊q~i-1~q~i~, q~j-1~q~j~所包圍，其中 i<j, |q~i-1~-r|>$\epsilon$, |q~j~-r|>$\epsilon$
1. 將free-space structure 分解成 vericle slab (分解花O(nk)時間)
1. 先用Linked list將events(Q的頂點,$\pm\epsilon$)按順序存起來(O(nk))
2. 用sweepline $s$ 由左往右掃，若maximal intervals的數量有變化->分割slab
(黃色虛線為events(?))
### Lemma 3.─free space structure S
1. 每個slab按順序存O(k)個Q的邊，這些邊界定了 maximal intervals，並且按順序儲存
2. 我們可以在O(logn)內找到包含一點 $r\in{\displaystyle \mathbb {R} }$的slab(藉由binary search)
---
### Lemma 4.─Reachability structure H
2. 計算並儲存free-space diagram的reachability
在O(nk)的時間內，我們可以確定對於Q中的每個邊界q~i−1~q~i~，free-space structure中可以達到的最右邊的點H(q~i−1~q~i~)。
從任何點（r，q）∈ (R × [0，|Q|])(向量空間)開始，其中 |r − q| ≤ ε，|r − q~i~| > ε且q ∈ q~i−1~q~i~。
3. 逐列遍歷 free-space diagram，持續追蹤在頂點p~i~處可抵達的Q的interval (Lemma6.)
### Lemma 5
目的：可以一次找到從(0,0)到(|P|,|Q|)的 monotone path.
方法：從目前在p~i-1~p~i~中的點(r, q)找到p~i~p~i+1~上的點(r', q')
1. (r, q)是Ｓ中一點
2. $r'' \ge r' \ge r$
3. q~i-1~q~i~對應到(r, q)射出垂直往上的光線碰到free-space structure的邊。
4. (r', q')是free-space structure從(r, q)到r'的highest reachable point
5. ((r' , q') = H(q~i−1~q~i~)) 或 ((r', q')的邊界斜率為正且r' = r'')
我們為 (r',q') 區分三種情況：
(1) 如果 (r',q') 不在free-space的邊界上，與 (r',q') 的定義矛盾，不成立。
(2) 如果 (r′,q′) 在向上傾斜的邊界上，則 r′′ = r′ 或者我們可以找到更高的reachable point。
(3) 如果 (r', q') 在向下傾斜的邊界上並且單調性阻止我們向左更高，則 (r', q') 實際上必須等於 H(q~i−1~q~i~)。
▲情況(2) - r'' > r'
▲情況(3)
### Lemma 6
given:
1. decomposition structure S
2. reachability structure H
3. sorted reachable intervals at pi
compute:
1. sorted reachable intervals at pi+1
2. time compexity: $O(log n + k)$
#### Proof sketch
我們用解構過的結構S找p~i+1~落在的slab(Theorem1步驟1)，此步驟只要O(logn)(Lemma 3.binary search)
令A為p~i+1~處的maximal intervals
令E為在p~i~的reachable intervals
我們用 Lemma4. 儲存的 H(E[j]) 來表示 highest reachable point。而儲存在 H 裡的資訊是每個interval E[j]之上的邊，此邊定義了E[j]的上界
我們同時沿著E和A走，分別使用index j 和 x，來尋找p~i+1~的interval
我們重複以下的操作：
1. 若E[j]的下界 > A[x]的上界，則x+1
2. 若H(E[j]) < A[x]的下界，則j+1
3. 若 |q-p~j-1~|$\le\epsilon$，q是在Q上代表E[j]下界的點。則我們可以從E[j]的q點畫一條直線到 interval A[x]，並記錄一個起點為q，終點為A[x]的reachable interval
4. 最後，如果都不符合前面1.~3.的情況，我們可以直達A[x]的下界，且A[x]是完全reachable的
做完 3. 和 4. 之後，我們按以下方式遞增數值：
* 如果A[x]的上界是向上傾斜的，我們就遞增j，直到找到一個值使得E[j]高於A[x](或是E的值用盡了)。
* 將x遞增一次(x+1)
在1.~4.中，每個case花Q(1)的時間，因此這會在 A(|A|+|E|) = O(k) 的時間內運行(Lemma2.)
包含我們對S的查詢，總會共花O(logn+k)
正確性來自於：我們收集了A[x]前的所有reachable intervals，而在E[j]之前的intervals到達不了A[x](跟以上)的區間。且A[x]之前的區間不能限制E[j]的高度 (via Lemma 5)。
### 影片筆記
(4:46) For any verticle line, the number of intersections with the boundary of the free space is at most twice the ply of A
ex: ply of Q = 3, intersections最多6
因此計算Frechet Distance只要O(nk) -> 有n個event, 每次檢查 O(2k) 個點
(6:09) we can maintain a set of reachable intervals on each vertical line, from which we can compute the reachable intervals on the next line.
翻譯機：我们可以在每条垂直线上保持一组可达区间，从中可以计算出下一行的可达区间。
下圖紅線為 reachable intervals
(6:20) To do this efficiently, we build a data structure for fast ray shooting queries.(Lemma5.)
# video
To compute the Fréchet Distance, we can make use of the free-space diagram.
For a given distance δ, we draw a 2-dimensional diagram, where each axis corresponds to the distance travelled along each curve, A and B. The free-space is the part of the diagram where the distance between the two points is at most δ.
Free-space diagrams were inspired by the notion of configuration space in, for instance, robotics, and were first introduced in 1995 by Helmut Vlt and Michael Godau as way to approach the Fréchet distance.
Their seminal work initiated quite a large amount of research into the computational complexity of the Fréchet distance.
The free-space diagram is a method to visually determine which segments of the curves are close enough to each other to allow simultaneous traversal within a given distance δ. Once we obtain the diagram, we can assess whether the Fréchet distance is smaller or larger than δ by searching for a y-monotone path within the free-space diagram.
We can compute the Fréchet distance by optimizing over δ, for instance, using parametric search.
Whether it is possible to compute the Fréchet distance distance in subquadratic time is still a major open question.
## But what does the free-space diagram look like in one dimension?(01:50)
When we think of curves, we tend to think of them living in spaces of two or more dimensions; however, mathematically, thre is no reason why a curve cannot be embedded in a one dimensional space.
Similarity between one dimensional curves is an important subject, and has applications in times series analysis and signal processing.
Since the Fréchet distance does not depend on the dimension of the ambient space, we can still use it to measure the similarity between two 1-dimensional curves.
It's like you and your dog walking back and forth on the same street!
A 1-dimensional curve is just a sequence if distances, that alternate left and right. And this restricted motion has a profound effect on the structure and visual appearance of the free-space diagram.
Let's do some geometry!
Because both curves either move in the same direction ot in opposite directions, the boundaries of the free-space diagram will always be lines with a slope of 1 or -1.
For instance, we draw...one free-space diagram.
The fact that the free-space diagram is so regular and can be drawn so compactly, might give us hope that one can break the quadratic-time barrier in this case.
## How do we use this to open things up?(03:35)
well, the short answer is we don't know. But we can solve the problem efficiently for curves of bounded ply!
The ply of spatial regions is an important concept in many geometric studies.
It's like with toilet paper. The ply of the roll of toilet paper is the number of sheets of paper that are stacked on top of each other. So for example, this particular roll has ply two.
It is hard to pinpiont the origin of such a natural notion, but we can at least say that Victor Klee described this concept in 1977 in his paper "Can the Union of n intervals be computed in less than logn steps?" where he called it depth. The term ply was first introduced in this context by Gray Miller, Shang-Hua Teng, William Thurston and Stephen Vavasis in 1977.
In general, the concept of ply does not make sense for curves. However, in 1-dimension it does!
The ply of curve A corresponds exactly with the ply of this piece of paper, when we fold if in only one direction!
For any vertical line, the number of intersections with the boundary of the free-space is at most twice the ply of A. The same holds for horizontal lines and the ply of B. In particular, this implies that when both A and B have bounded ply k, computing the Fréchet distance becomes quite trivial: the diagram now only has complexity k times n, so we can construct it explicitly. And by construct, I mean compute. we can compute the Fréchet distance between two 1-dimensional curves of bounded ply k in O(nk) time.
## Aren't there supposed to be gory technical details in this video?(05:15)
Studies have shown that video are more effective when they focus on more elementary material. However, we do not want to risk our viewers thinking that we are not doing serious science here.
Even when only one of the curves has bounded ply, we can make use of the special structure of the free-space diagram to solve the problem more efficiently. The key is to consider the free-space diagram between A and a line. Now, we can see the other curve, B, as a sequence of vertical lines, and we are looking for a monotone path moving back and forth between those lines, touching them. We can do this because the free-space is basically a sequence of slabs that are all cut out of the same base diagram. As if we are folding the diagram along the vertical lines.
As if we are folding the diagram along the vertical lines.
Because of this, we can maintain a set of reachable intervals on each vertical line, from which we can compute the reachable intervals on the next line. To do this efficiently, we build a data structure for fast ray shooting queries.
Ray-shooting data structures can efficiently answer questions of the type: If I shoot a ray from here in that direction, what do I hit? They are quite well understood: they date back to 1989 in computational geometry and even earlier in computer graphics.
By using the data structure appropriately, we can decide in O(nk) time whether the Fréchet distance between a ply k curve and any other curve is smaller. than delta.
## So. Once again. What was this about?(06:48)
We have shown that deciding whether the Fréchet distance is smaller than delta for two 1-dimensional curves , at least one of which has bounded ply, can be done faster than in quadratic time.
The question of whether the Fréchet distance between unrestricted 1-dimensional curves can be computed in sub quadratic time remains open. We would like to boldly conjecture that it can.
Sign in with Wallet
Connect another wallet