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 \| \pi_\mathcal{P}(s, \ell) \| := \min_{t \in \ell}\| \pi_\mathcal{P}(s, t) \| \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 + \epsilon} 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로 바꿔서 처리해도 된다.

  1. $\Delta_l$와 disjoint한 장애물과 접하는 경우

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

  1. $\Delta_l$와 disjoint한 장애물에 접하지 않고 부딪히는 경우

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

Rectangle intersection 참고.