한국정보통신학회 논문지 (Journal of the Korea Institute of Information and Communication Engineering)
Current Result Document :
| 한글제목(Korean Title) |
광선 슈팅 문제를 위한 볼록 레이어 트리 |
| 영문제목(English Title) |
A Convex Layer Tree for the Ray-Shooting Problem |
| 저자(Author) |
김수환
Soo-Hwan Kim
|
| 원문수록처(Citation) |
VOL 21 NO. 04 PP. 0753 ~ 0758 (2017. 04) |
한글내용
(Korean Abstract) |
광선 슈팅 문제는 주어진 기하 객체들에 대해서 직선을 따라서 이동하는 광선이 처음으로 부딪히는 객체의 점을 찾는 문제이다. 광선은 보통 질의의 형태로 주어지기 때문에, 이 문제의 일반적인 해법은 다음과 같다. 먼저, 전처리 과정으로, 주어진 객체들에 대한 자료구조를 구축한다. 그 다음, 이 자료구조를 이용하여 각 질의에 대한 답을 빠르게 구한다. 본 논문에서는 축 상에 놓인 수직 선분들 집합에 대한 광선 슈팅 문제를 고려한다. 본 논문에서는 입력으로 주어진 n개의 수직 선분들에 대해 볼록 레이어 트리라고 부르는 새로운 자료구조를 제시한다. 이것은 수직 선분들의 볼록 외피들의 레이어로 구성되는 이진 트리이다. 이 트리는 O(nlogn) 시간과 O(n) 공간의 알고리즘으로 구축되며 구현이 용이하다. 또한 이 자료구조를 사용하여 각 질의를 O(nlogn) 시간에 수행하는 알고리즘을 제시한다.
|
영문내용
(English Abstract) |
The ray-shooting problem is to find the first intersection point on the surface of given geometric objects where a ray moving along a straight line hits. Since rays are usually given in the form of queries, this problem is typically solved as follows. First, a data structure for a collection of objects is constructed as preprocessing. Then, the answer for each query ray is quickly computed using the data structure. In this paper, we consider the ray-shooting problem about the set of vertical line segments on the -axis. We present a new data structure called a convex layer tree for n vertical line segments given by input. This is a tree structure consisting of layers of convex hulls of vertical line segments. It can be constructed in O(nlogn) time and O(n) space and is easy to implement. We also present an algorithm to solve each query in O(nlogn) time using this data structure.
|
| 키워드(Keyword) |
이진 트리
계산기하학
볼록 외피
광선 슈팅
Binary tree
Computational geometry
Convex hull
Ray-shooting
|
| 파일첨부 |
PDF 다운로드
|
