We study the flow of water on fat terrains, that is, triangulated terrains where the minimum angle of any triangle is bounded from below by a positive constant. We show that The worst-case complexity of the river network on such terrains is $\Theta(n^2)$. This improves the corresponding bounds for arbitrary terrains by a linear factor. We prove that in general similar bounds cannot be proven for Delaunay triangulations: these can have river networks of complexity $\Theta(n^3)$.
본 논문에서는 지형(terrain)에 관련된 문제들 중에 가장 중요한 문제 중 하나인 물의 흐름을 분석하는 문제를 다룬다. 흐름 분석의 가장 기본적인 문제는, 강 네트워크 (river network) 를 찾고, 주어진 점 q에 대하여, 그것의 분수계 (watershed)를 찾는 것이다. 실제 지형 위에서 직접 실제 흐름 정보를 측정하는 것은 시간이 오래 걸리고 많은 노력이 필요하기 때문에 지리 정보 시스템 (GIS) 연구자들은 정밀도가 높은 지형의 높이 정보를 이용해 흐름 정보를 계산해낸다.
GIS에서는 TIN (triangulated irregular network)를 지형 정보를 표현하기 위해 흔히 사용한다. TIN은 불규칙하게 분포된 점들에서 측정된 높이를 모으고 측정점들을 삼각분할한 뒤에 각각의 삼각형 안에 있는 점들의 높이를 보간하는 것으로 지형을 표현한 것이다.
우리는 TIN으로부터 분수계를 계산하기 위한 강 네트워크 자료구조의 복잡도에 관해 연구하였다. n 개의 점으로 구성된 TIN에서의 강 네트워크는 최악의 경우에 $\Theta(n^3)$의 복잡도를 가질 수 있음이 증명되었다 [2]: $\Theta(n)$ 개의 서로 다른 강이 각각 $\Theta(n^2)$의 복잡도를 가지는 경우이다. 이러한 최악의 경우는 실세계에서 잘 나타나지 않는다.
본 논문에서는 현실적인 지형 (realistic terrain)에서 강 네트워크가 어떠한 복잡도를 가지는지를 다루었다. 지형을 이루는 삼각형들의 모든 각이 어떠한 양의 상수 이상을 가질 때 그 지형을 fat terrain이라 부른다. 본 논문은 fat terrain의 경우에, 그리고 지형을 이루는 모든 삼각형이 둔각삼각형이 아닐 때에는 강 네트워크의 복잡도는 최악의 경우 $\Theta(n^2)$임을 보인다. 하지만 점들을 Delaunay 삼각분할한 경우에는 최악의 경우인 $\Theta(n^3)$의 복잡도를 지니는 강 네트워크가 존재할 수 있음을 보인다.