도로 환경에서 Skyline을 계산하는 기하 알고리즘

본 논문은 도로 환경에서 주어진 자료점의 집합 P로부터 질의 집합 Q에 대해 이동에 필요한 소요 시간이 Skyline[1,2,3,4,5]의 성질을 만족하는 P의 부분 집합 S를 찾는 문제에 대해 연구한다. 본 논문은 단위 속력으로 수직, 수평 방향으로만 이동 가능한 2차원 공간에서 skyline을 찾는 문제에 대해 O(|P|log|P|) 시간 복잡도와 O(|P|) 공간 복잡도를 사용하는 알고리즘을 제시한다. 또한 이 평면상에 하나의 무한 길이의 수평 도로가 있을 때 skyline을 찾는 알고리즘을 제시한다. 도로상에서의 이동 속력이 무한일 때 모든 skyline S를 찾는데 O(|P|+|S|log|S|/log log|S|) 공간 복잡돌ㄹ 사용하는 알고리즘을 제시한다. 또한 도로상에서의 이동 속력이 상수일 때 모든 skyline을 찾는 O(|P||Q|log|Q|+|P|min{|S|, |Q|log|S|}+|P|log|P|) 시간 복잡도와 O(|P|+|S|log|S|/loglog|S|) 공간 복잡도를 사용하는 알고리즘을 제시한다. 또한 도로상에서의 이동 속력이 상수일 때 모든 skyline을 찾는 O(|P||S|log|Q|+|P|log|P|+|P||Q|) 시간 복잡도와 O(|P|) 공간 복잡도를 사용하는 알고리즘을 제시한다.