Segment Dragging in Polygonal domain (1)

Problem Definition

2차원 공간에서의 polygonal domain $\Gamma =\{{\Gamma }_1,{\Gamma }_2,\cdots ,{\Gamma }_h\}$를 생각하자. 더 정확히 말하자면, $h$개의 서로 겹치지 않는 다각형 장애물이 있고, 이 도형들이 가진 정점의 총 갯수는 ${\sum }_i|{\Gamma }_i|=n$이라 가정한다.

어떤 선분 $s$가 주어졌을 때, 선분을 수직 방향으로 평행이동해서 (위, 아래로) 가장 먼저 닿는 다각형의 index와 교차하는 점을 구하여라. ($\tilde{O}(n+h^2)$ preprocessing / storage, $O({\log }^{c}n)$ query)

Related Works

Segment dragging query는, 주어진 선분을 움직여서 가장 먼저 마주치는 점을 찾는 문제이다. 1988년 Chazelle이 horizontal segment에 대한 dragging query를 $O(n\log n)$ preprocessing, $O(n)$ storage로 $O(\log n)$ 시간 안에 답하는 알고리즘을 소개했다.

Simplex range searching은 주어진 정점들 중 도형이 포함하는 정점을 나열하는 문제이다. 고차원 공간에서 가장 기본적인 도형(simplex)을 사용하여, 이 문제를 풀면 그 이상으로 복잡한 다면체(ex. 사각형, 정육면체 등)로 해법을 확장할 수 있다.

Parametric Searching

주어진 직사각형 $\mathcal{R}$이 $\Gamma$와 겹치는 여부를 확인하는 결정 알고리즘 $A$가 있다고 치자. 결정 알고리즘의 각 실행 분기는 다각형 $\Gamma$에 의해 결정되는 ($\mathcal{R}$의 변수에 대한) 다항식의 부호로 결정된다면, 이 문제에 Parametric search를 사용하여 실행 시간을 결정할 수 있다.

Case 1. 어떤 다각형 도형 ${\Gamma }_i$가 $\mathcal{R}$에 포함될 때

각 도형의 내점(interior point) $p_i\in {\Gamma }_i$를 뽑는다. (3개의 연속한 점 $q_1,q_2,q_3\in V({\Gamma }_i)$ → $q_2$에서 $\frac{q_1+q_3}{2}$ 방향으로 ${\Gamma }_i$ 안에서 ray shooting → query와 answer의 중점. Simple polygon 안에서 이 과정은 $O(|{\Gamma }_i|)$ 시간안에 수행)

만일 $\mathcal{R}$이 ${\Gamma }_i$를 포함한다면, ${\Gamma }_i$의 내점인 $p_i$ 또한 $\mathcal{R}$에 포함된다. 한편, $p_i$가 $\mathcal{R}$에 포함되지만 ${\Gamma }_i$가 $\mathcal{R}$에 포함되지 않을 수 있는데, 이 경우에는 반드시 $\mathcal{R}$이 ${\Gamma }_i$의 간선과 교차하므로 Case 2에서 반드시 다뤄지게 된다. (그렇지 않을 경우 모순이 발생한다.)

이 문제는 $h$개의 정점이 주어진 삼각형 $\Delta$ 내부에 없는지 판단하는 simplex range emptiness 문제로부터 환원 가능하다. Cole, Yap 두 사람이 두 가지 자료구조를 만들었는데, 그 중 하나가 $O(n^2/\log n)$ 전처리 후 $O(\log n\log \log n)$ 안에 쿼리 가능하다.

Case 2. 어떤 다각형 도형 ${\Gamma }_i$가 $\mathcal{R}$과 교차할 때

Ray shooting으로 해결할 수 있다. 사각형의 네 꼭지점이 장애물 안에 포함되어 있는지 먼저 확인하고($O(\log n)$), 시계 방향으로 ray shooting을 실행하여 네 광선이 모두 사각형 밖으로 나가는 것과 동치이다. Chen, Wang은 2015년에 $O((n+h^2){\log }^{c}n)$ 시간 안에 전처리를 마치고 $O(\log n)$ 안에 쿼리 가능한 ray shooting 자료구조를 설계하였다.

합하면?

두 메소드 모두 parametric search를 사용할 수 있다. 자료구조를 구성하는 데 걸리는 시간은 $O((n+h^2){\log }^{c}n)$이다. 두 query 모두 실행 시간이 logarithmic이므로, 병렬화하지 않고 parametric search를 실행해도 큰 문제가 없으며 parametric search를 실행하는 데 드는 query 시간 복잡도는 $O((\log n\log \log n{)}^2)$이다.

이걸로 풀고자 하는 문제는 다음 이 시간에…

References

[1] Goswami, P. P., Das, S., & Nandy, S. C. (2004). Triangular range counting query in 2D and its application in finding k nearest neighbors of a line segment. Computational Geometry, 29(3), 163-175.

[2] Chazelle, B. (1988). An algorithm for segment-dragging and its implementation. Algorithmica, 3(1-4), 205-221.

[3] Benbernou, N. M., Ishaque, M., & Souvaine, D. L. (2008, August). Data structures for restricted triangular range searching. In 20th Annual Canadian Conference on Computational Geometry (pp. 15-18).

[4] Cole, R., & Yap, C. K. (1984). Geometric retrieval problems. Information and Control, 63(1-2), 39-57.

[5] Chen, D. Z., & Wang, H. (2015). Visibility and ray shooting queries in polygonal domains. Computational Geometry, 48(2), 31-41.