Segment Dragging in Polygonal domain (2)

Haitao 선생님께서 키 문제를 풀어버려서 contribution이 날아갔다.

Problem

Polygonal domain $\mathcal{P}$와, free space 위의 정점 $s$가 주어졌다고 가정하자. shortest path to a segment query(SPSQ)는 free space 위의 간선 $\ell$이 주어지면 $s$에서 $\ell$까지의 최단 거리를 반환하는 문제이다. 짧게 쓰면 아래와 같다.

$$(\mathcal{P},s)\mapsto \left(\ell \mapsto \Vert {\pi }_{\mathcal{P}}(s,\ell )\Vert :=\underset{t\in \ell }{\min }\Vert {\pi }_{\mathcal{P}}(s,t)\Vert \right)$$

• 목표 : $\tilde{O}(n+h^2)$ preprocessing, storage & $O({\log }^{c}n)$ queries

Strategy

1. Extended Corridor & Extended Ocean

Chen, Wang의 Extended Corridor structure를 구성한다. [Chen, 2015]

• Polygonal domain triangulation - $O(\min (n\log n,n+h{\log }^{1+ϵ}h))$
• $O(h)$ 개의 (open, closed) hourglasses 계산하는 데 $O(h)$ (graph reduction, shortest path inside a simple polygon)
• $O(h)$ 개의 bay, canal (전체 복잡도 $O(n)$)
• $O(n+h\log h)$ Ocean(funnel, open hrgls, jctn tri) 계산
• Ocean은 $O(h)$개의 convex polygonal chain으로 구성

총 $O(n\log n)$ 시간 안에 $O(n)$ 크기의 자료구조로 만들 수 있다.

• 여기서 ray shooting 자료구조도 미리 만들어놓을 수 있다.
  • 근데 그러면 polylog 시간복잡도 계산이 필요하고, Agarwal 써도 무방함

2. $O(h)$ Pseudo-triangular Decomposition

Quickest Visibility query를 위한 자료구조를 참고한다. [Wang, 2019]

• $O(h)$개의 경로로 polygonal domain을 분할하는 게 핵심
• Shortest path map(SPM) : 단일 시작점 $s$에 대해 구성, 최단경로 길이 query 및 backtracing 가능
  • shortest path의 predecessor - partition
  • $O(h)$개의 bisection endpoint($\beta$)와 triple point($\tau$)
• Ocean에서 위 정점들까지의 경로들로 분할하면
  • 모든 파티션이 pseudo-triangle 꼴(또는 2개 연접)

3. Cell Ordering and Stabbing Query

Free space를 $O(h)$개의 pseudo-triangle로 분할하면 몇 가지 성질을 만족함.

• 각 cell 안에 있는 정점 또는 선분까지의 거리는 둘 이하의 cell root로부터의 거리와 일치함
• 한 선분과 cell의 교집합은 연결되어 있음(외부 공간으로 단절되지 않음)
• 모든 pseudo-triangle의 복잡도 합은 $O(n)$
• 등등

Ocean의 obstacle ${\mathcal{H}}_i$에 대해, 각 cell의 상대적인 거리를 매긴다. 도형에 접하는 반직선에 부딪히는 cell의 순서가 전체 순서에서 보존되도록 순서를 매길 수 있으며(Balanced tree), 각 obstacle마다 cell들의 순서를 주면 총 복잡도는 $O(h^2)$가 된다. ($O(h^2\log h)$ preprocessing, $O(h^2)$ storage)

접선의 자유도는 1($\theta$)임. theta가 주어졌을 때, 해당 접선에 포함된 cell의 목록을 segment tree로 관리할 수 있다. $O(\log n)$개의 cell 뭉텅이 tree가 주어지면, 각 뭉텅이의 convex hull로부터 거리 추정.

각 cell은 wavefront를 무더기로 가짐. 뭉텅이마다 convex hull 만들고 머시기 하고 있었는데 잘 기억이 안남.

4. Segment가 주어졌을 때

• segment가 bay 또는 canal을 지나는지 먼저 파악한다.
  • 만약 지나간다면 simple polygon 문제이므로 쉽게 풀 수 있음
  • 최대 $O(1)$번 발생
• $\ell$의 양 끝점을 $v_l,v_r$이라 하자.
  • 만약 $v_l,v_r$이 같은 cell $\Delta$에 포함되어 있으면 $\log \Delta$ 안에 자명한 해를 얻는다.
• $v_l,v_r$이 서로 다른 cell에 속하면
  • 우선 $v_l,v_r$ 포함된 각 cell에서의 최단거리를 구한다.
  • $\ell$을 위, 아래로 평행이동하여 부딪히는 장애물의 index(${\Gamma }_i$), 접선이 되는지 여부를 확인한다.
  • 평행이동한 선분이 접선이 아닌 경우 있을 수 있다. 도형의 convexity를 이용해 직선 수직방향으로 최대한 이동한 후, feasibility(ray shooting)를 확인한다.

5. Segment Dragging in Polygonal Domain

Lemma. 선분 $\ell$까지의 최단경로가 $\ell$에 수직하게 인접하면, $d(s,\ell )=\min ({\ell }^{\text{u}}+d(\ell ,{\ell }^{\text{u}}),{\ell }^{\text{d}}+d(\ell ,{\ell }^{\text{d}}))$ 이고, ${\ell }^{\text{u}},{\ell }^{\text{d}}$는 각각 $\ell$을 위, 아래로 적절히 최대한 평행이동한 선분을 의미한다.

$v_l$이 포함된 ${\Delta }_l$과의 배치 여부에 따라 3가지 경우.

1. ${\Delta }_l$에 인접한 장애물과 부딪히는 경우

이 경우에는 인접한 장애물의 tangential로 바꿔서 처리해도 된다.

2. ${\Delta }_l$와 disjoint한 장애물과 접하는 경우

마찬가지로 해당 장애물의 tangential로 생각한 뒤 거리를 계산하면 된다.

3. ${\Delta }_l$와 disjoint한 장애물에 접하지 않고 부딪히는 경우

골치아파지는 경우긴 한데, 이런 조건을 만족하려면 $v_l,v_r$이 평행이동하면서 pseuodtriangle의 gate를 지나가야 한다. Gate와 “먼저” 접하는 점 기준, 사다리꼴 영역의 emptiness에 대해 parametric search 사용

Rectangle intersection 참고.