<그림 1> <그림 2>
1. 개요
□ 연구목적
○ 명절 막바지에 나와 가족은 피곤한 몸을 이끌고 차를 탔다. 경기도 부근에 복잡한 도시에서 차에 기름이 떨어졌다는 소리가 들려왔다.
몇 시간 동안 달렸으니 그럴 만 했다. 하지만 복잡한 도시였던 터라 주유소를 찾는 것이 여간 어려운 일이 아니었다. 우리는 내비게이션 이라는 편리한 기구를 사용해 근처 주유소를 검색했다. 내비게이션이 검색해 놓은 주유소는 직진하여 반대 차선으로 U턴을 해야 했다.
기름을 빨리 넣어야 해서 내비게이션이 알려준 길을 따라 주유소로 가서 기름을 넣었다. 다시 U턴을 하여 길을 가던 도중 아까 U턴이 아닌 직진을 했을 때 조금은 먼 거리였지만 주유소가 있는 것을 ㅂ라 견했다. 이것이 문제였는데 그 지역에서 거리는 짧으나 차로 인해 돌아서 가는 경우와 조금은 더 멀지만 직진으로 한 번에 갈 수 있는 경우 중 내비게이션은 전자를 선택한다는 것이다.
○ <그림 1>을 보면 현재 차 주변에는 보이지 않는 (1)번 주유소와 (2)번 주유소가 존재한다. 주유소를 검색을 한다면 내비게이션은 당연히 유클리드 거리, 즉 직선거리가 짧은 (2)번 주유소를 검색해 줄 것이다.
그러나 차를 탄 이상 도로로만 가야하는 불편함이 있다. 다시 말해
<그림 2>에서 보면 실제 경로로는 (1)번 주유소가 더 가깝고 편리하
<그림 3>
다. 이는 실생활에서 우리에게 큰 불편함이자 내비게이션의 모순점이 다. 이 모순점이 우리 모두에게는 모티프가 되었다. 생활에서의 모순 점을 제거하고 실제 제품의 보안과 개발을 위한 연구를 고안했다.
○ 앞서 언급한 문제를 수학적으로 접근을 시도했다. ‘단순한 직선 거리 가 아닌, 좀 더 복잡한 거리를 어떻게 수학적으로 계산할까?’ ‘블록이 라는 장애물을 돌아서 가는 거리는 어떻게 계산할까?’와 같은 의문점 을 초점으로 검색이나 자문을 구해본 결과 ‘택시 거리’라는 개념을 접하게 되었다.
○ ‘택시 거리’는 <그림 3>에서 보는 바와 같이 바둑판 모양의 도로망을 가진 도시를 상상해 보았을 때, 점 A에서 점 B까지의 최단 거리를 구할 경우에 점 A에서 점 C를 거쳐 점 B로 가는 거리를 뜻한다.
이는 일명 ‘맨하탄 거리’라고도 불려진다. 이 ‘택시 거리’는 우리가 원하던 거리에 적합했고 또 수학적으로 알기 쉽게 표현되어 있었다.
결국, 우리 모두는 이 개념을 도입하기로 정했다.
□ 연구범위
○ 연구 분야 및 범위
- 본 연구는 ‘택시 기하학’ 이라는 수학적 분야와 그것을 응용하여 컴퓨 터 프로그램 상에 적용시키는 컴퓨터 공학 분야의 두 분야에 걸쳐 진행되었다. 수학 분야에서는 오직 ‘택시 기하학’에만 그 범위가 한정
되어 있다. 그리고 컴퓨터 공학의 분야에서는 내비게이션에서 도로상 의 길 찾기 알고리즘의 기본이 되는 R-tree, R*-tree와 같은 여러가지 트리의 개념과 다익스트라 알고리즘과 같은 여러 알고리즘들을 이해 하기 위한 넓은 범위의 학습이 진행되었다. 또한 가까운 주유소 찾기 알고리즘을 구현하기 위해 C언어의 기초와 응용적인 범위를 습득하 였다.
○ 연구 진행 단계
- 연구는 크게 5단계로 나누어 볼 수 있다.
- 1단계는 ‘자료 조사’와 ‘스터디’이다. 5명을 3명, 2명의 두 그룹으로 역할 분담을 하여 한 그룹은 ‘자료 조사’에 더 많은 시간을 투자하고 다른 그룹은 ‘C언어 스터디’에 더 많은 시간을 투자해서 효율적인 연구 진행을 하도록 했다.
- 2단계는 ‘알고리즘 연구’이다. 이 단계에서는 택시 기하학을 이용한 가까운 주유소 찾기 알고리즘을 구현하기 위해 필요한 여러 가지 알고리즘들에 대해 조사하고 연구한다. 또한 ‘다이아몬드 클러스터 링’ 기법을 계획하고 구현하기 위한 방법을 고안한다.
- 3단계는 ‘구현 및 실험’ 이다. 2단계에서 고안한 방법들을 실제로 컴퓨터 상에서 구현하는 것이다. 고등학교 범위의 수준에서 처음부터 모두 프로그래밍을 할 수 없으므로 기존에 교수님께서 작업하시던 R-tree 를 우리의 주제, 방법에 맞게 수정하는 방식으로 진행된다.
구현이 완료되면 실제로 어떻게 작동하는지 가상의 값을 주어 실험에 들어간다. 실험을 통해 우리가 구현한 여러 방법들에 어떤 차이가 있는지 비교, 분석하여 결론을 도출한다.
- 4단계는 ‘논문 및 특허 제출’ 이다. 도출한 결론을 토대로 논문을 작성하여 제출해보고, 결과가 좋으면 특허까지 신청하는 것이다.
- 5단계는 ‘실제 내비게이션에 적용’ 하는 단계이다. 4단계에서 좋은 평가와 결과를 받는다면 실제 내비게이션 업에 우리의 방법을 제시해 서 상용화 될 수 있게 할 것이다.
< 그림 4 – 내비게이션 경로 설정 과정>
2. 연구 수행 내용
□ 이론적 배경 및 선행 연구
○ 내비게이션 경로 찾기에 대한 기술 개요
< 그림 5 – 내비게이션이 작동하기까지의 과정 >
- 가중치나 거리가 동일한 경우에는 우회하는 경우가 발생함.
○ 가장 가까운 주유소 찾기를 위한 컴퓨터 알고리즘 - R*-tree
* 삽입 알고리즘
▸ 중간 노드의 사각형 영역이 최소로 증가하도록 하여 간접적 으로 겹치는 영역을 줄인다. 삽입할 리프 노드에 오버플로우
가 발생했을 때, 리프 노드에서 분할이 일어나고 계속해서 상위노드에도 분할이 일어난다. 이때, 강제적으로 최대 엔트 리수의 30%정도의 엔트리를 재삽입.
* 삭제 알고리즘
▸ 객체를 삭제한 후 그 노드의 엔트리 수가 최소 엔트리 수에 미달하면 그 노드를 삭제하고 그 노드의 엔트리들을 재삽입.
* 분할 알고리즘
▸ 지수 함수 비용 알고리즘
▸ 2차 함수 비용 알고리즘
▸ 선형 비용 알고리즘
* 장점
▸ R-trees의 삽입 알고리즘이 영역의 면적만을 고려하는데 비해 R*-trees의 삽입 알고리즘은 영역의 면적뿐만 아니라, 둘레, 겹치는 영역의 크기를 모두 고려하여 공간 객체를 삽입할 최 적의 리프 노드를 선택한다.
▸ 기억 장소 이용률 최적화 및 강제 재삽입을 통하여 영역 사 각형의 형태를 정사각형에 가깝게 하고, 노드 간에 겹치는 영역을 줄이며 기억 장소 효율을 개선한다.
▸ 삽입, 삭제 연산 시 부모 노드의 사각형을 효율적으로 확장 이 가능하다.
- 보로노이 다각형
* 유클리드 공간(左)과 택시 공간(右)에서의 보로노이 다각형
▸ 거리만을 고려해서 가장 가까운 주유소를 찾을 경우 각 주유 소를 기준으로 한 보로노이 다각형이 단서가 될 수 있다.
▸ 지금까지는 우리가 사용하고 있는 유클리드 거리를 이용해서 구역을 나눴는데, 차량 및 교통 경로로 이동할 시에는 도로 나 보도블록 등 때문에 모순이 생기므로 이때는 택시거리를 이용해서 구역을 나눠야 한다.
▸ 그림 8과 그림 9는 택시공간에서의 두 점에서 같은 거리에 있는 점들의 집합을 나타내고 있다.
▸ 그림 8에서 점 과 점 에 이르는 거리가 같은 점의 집합은 두 번 꺾인 직선의 모양을 이룬다.
▸ 그림 9는 점 과 점 를 두 정점으로 하는 경우를 보여준다. 여기에서 두 점에 이르는 거리가 같은 점들은 직
선 의 일부( 일 때)와 검게 칠해진 부분
{ ≤ ≥ or ≥ ≤ }에 속해 있다.
▸ 이로써 두 정점에 이르는 거리가 같은 점의 집합은 두 정점 을 양 끝점으로 하는 선분의 수직이등분선이라는 명제가 택 시공간에서는 거짓임을 알 수 있다.
○ 그래프를 이용한 도로상의 최단 경로를 찾는 알고리즘.
- 다익스트라 알고리즘(Dijkstra Algorithm)
* 시작점에서 볼 때 더 짧은 거리의 정점으로 가고, 그 정점에서 더 짧은 곳으로, 더 짧은 곳으로 가는 알고리즘. 단, 이미 한번 지나간 점은 다시 가지 않는다. 빠르고, 단순하지만, 간선의 값이 음수이면 실행이 되지 않는다.
□ 연구주제의 선정
○ 처음 본 프로젝트를 시작하려고 계획했을 때의 주제는 ‘택시 기하학과 유클리드 기하학의 차이점의 분석과 여러 가지 도형의 비교’ 였다.
이 주제는 교내 R&E 프로젝트 활동을 위해 설정했던 것으로 주제가 매우 포괄적이고 여러 방면으로 접근이 가능했다. 그런데 이 주제를 제출했을 때 프로젝트 담당 선생님이 창의재단의 STEAM R&E에 주제를 제출해보라는 조언을 해주셔서 처음에 정했던 수학적 주제를 실생활에 적용시켜 새로운 분야에서 더 구체적으로 연구해 보기로 결정했다. ‘택시 기하학’이라는 수학적 주제를 실생활 문제 개선에 적용시키기란 쉽지 않았다. 마땅한 주제를 찾지 못하고 고민하던 중 에 팀원 중 한명이 내비게이션의 길찾기 미숙으로 길을 헤맸던 경험 을 이야기 하면서 그 분야에 ‘택시 기하학’을 적용시켜서 개선해 보는 것이 어떻겠냐고 의견을 제시했다. 우리는 ‘컴퓨터 공학’이라는 분야
에 큰 관심과 흥미가 없었기에 처음에는 막막하고 불가능하다고 했지 만 교수님께서 프로그래밍이나 알고리즘 등의 여러 가지 컴퓨터 지식 을 가르쳐 주시겠다고 하셔서 ‘내비게이션 시스템 개선’을 목적으로 연구를 시작하게 되었다.
□ 연구 방법
○ 인터넷과 도서 등을 활용하여 택시 기하학에 대한 개념 및 기초 지식, 내비게이션 시장 현황 및 기능에 대한 자료 조사를 함.
○ 내비게이션에서 도로 상의 길 찾기 알고리즘의 기본이 되는 트리 (R-tree, R*-tree)와 그래프 이론을 연구함.
○ 택시기하학을 이용한 가까운 주유소 찾기 알고리즘을 직접 컴퓨터 프로그래밍으로 구현하기 위해 교수님으로부터 C언어를 배움.
○ 각국의 여러 논문을 통해 생소하거나 처음 보는 이론에 대하여 공부하 고 이를 택시 기하에 적용시킬 수 있는 방안에 대해 연구하고 토의함.
○ 연구 결과로 도출된 새로운 알고리즘들을 모두 C 언어로 직접 구현한 후 두 가지 알고리즘에 대하여 위치 데이터를 집어넣어서 실험을 통해 알고리즘의 정확성과 효율성을 검증함.
○ 우리에게 생소하거나 접근하기 어려운 컴퓨터 알고리즘 지식과 관련 해서는 전문가 특강을 통해 지식을 습득한 후 계속 연구를 실시함.
- 특히 택시 기하학을 이용한 위치 데이터 클러스터링 알고리즘의 기반 이 되는 지식은 전문가 자문 교수님의 특강을 통해 습득하기로 함.
○ 내비게이션 회사를 직접 방문해서 내비게이션의 구성 요소, 주로 쓰이는 알고리즘과 개요에 대해 설명을 듣고 택시 기하학을 이용한 내비게이션 알고리즘의 개선 방안에 대해 토의함.
□ 연구 활동 및 과정
○ 가설설정
- 기존에 사용하던 유클리드-기하학적-거리 이용 내비게이션보다 새 로 개발한 taxi 기하학을 이용하여 내비게이션 프로그램을 구성한 것이 시간적, 메모리 크기에 있어서도 더 효율적이다.
○ 실험설계
- 현재 다양한 분야에서 쓰이고 있는 내비게이션 알고리즘을 분석 - 알고리즘에서 유클리드 기하학을 기반으로 하고 있는 로직을 찾음 - 찾은 로직에서 유클리드 기하학적 거리를 어떻게 바꾸어야할지 구상 - 찾은 로직에서 유클리드 기하학적 거리를 택시기하적 거리로 바꿈 - 바꾼 로직을 알고리즘에 삽입하여 실행 후, 기존의 것과 비교·분석
○ 실험 과정
- 설계한 대로, 우선 내비게이션 알고리즘을 분석한다. 그 중에서 유클 리드 기하학을 이용한 로직을 발견했다. 그 중에서, 어떤 로직을 고쳐 야 효율을 높이고 좀 더 간단하게 만들 수 있는지 구상을 했다. 결국, 고쳐야할 부분을 원하고자 하는 사각형을 형성하는 로직인 random_range함수, overlap 매크로 함수 등으로 정했다.
- 택시 기하학을 이용한 새로운 알고리즘의 원리 * Taxi R-tree (Diamond-tree)의 구현
▸ 기존의 유클리드 R-tree 구성 방식
: “점 P로 부터 택시 거리로 반경 3km 이내의 모든 주유소를 검색하 라”라는 query가 입력되면 기존의 R-tree에서는 노드 R1과 R2를 모두 검색해야 한다.
: Range query인 반경 3Km는 택시 공간에서는 다이아몬드 형태가 된다.
- Taxi R-tree (Diamond-tree) 구성 방식
* R-tree를 구성하는 MBR(Minimum Bounding Rectangle)이 query 범위에 해당하는 택시원(다이아몬드)과 평행하다.
* Euclid MBR을 45도 회전 이동한 것과 같다.
*“점 P로 부터 택시 거리로 반경 3km 이내의 모든 주유소를 검색하라”라는 query가 입력되면 노드 R1과 R2는 qeury 반경과 overlap이 없으므로 검색할 필요가 없다.
- Taxi R-tree 구현(기존 방식)
* 기본적인 구현 방식 및 원리는 상기한 Taxi R-tree 구현 방안과 같이, Rotated TAXI R-tree를 만드는 방법을 사용 하였다.
* Rotated TAXI R-tree가 되기 위해서는 주유소, 즉 점이 다이아몬드 형태로 분포되어야 한다. 따라서 점을 분포시키는 random_range함 수를 변형시켰다.
- 기존의 overlap 매크로 함수
- 수정 후, 다이아몬드 overlap매크로 함수
- 기존 random_range함수
- 수정된 random_range함수
○ 시행착오
- 처음에 목표한대로 알고리즘을 짜던 도중, 예상치 못한 문제에 막혔
다. 유클리드 기하학을 이용한 거리를 사용하는 MBR을 택시 거리를 이용한 거리를 바꾸는데 너무 복잡하고 시간이 오래 걸린 것이다.
○ 극복
- 결국 의논한 끝에, 하나하나 바꾸지 말고, 처음부터 45도를 돌려 기존 의 하던 방식처럼 정사각형을 만든 뒤 다시 돌리게 되면, 택시거리로 바뀐다는 점을 이용하기로 했다.
- Taxi R-tree 구현 방안(수정 보완)
* 기존의 R-tree 에서 x, y axes를 45도 회전하면 TAXI R-tree 와 같은 모양이 되고, 기존의 R-tree에서 도메인 영역은 정사각형이나 Rotated TAXI R-tree에서는 다이아몬드가 된다.
* 기존 R-tree를 이용하면 Query window는 택시원인 다이아몬드가 되나 Rotated TAXI R-tree에서는 정사각형이 된다.
* 이때 택시 반경은 Query Point P로부터 정사각형의 코너까지의 거리 이므로, 정사각형의 가로, 세로 길이는 2*택시반경/이다.
- Overlap b/w Diamond and Rectangle * Filter step
▸우선 Diamond의 MBR(Minimum Bounding Rectangle)과
Rectangle 간의 overlap을 체크한다.
* Refinement step
▸Filter step을 통과한 candidate rectangle에 대해 false overlap을 한 번 더 검사하여 걸러낸다.
* False overlap의 경우는 rectangle의 모든 꼭짓점이 diamond의 한 변 바깥쪽에 있다.
○ Taxi R-tree (Diamond-tree)의 프로그래밍 - 프로그래밍 방안
* 복잡한 구조의 R-tree를 전부 스스로 프로그래밍하기엔 프로그래밍 지식이 부족하다고 판단, R&E 활동을 도와주신 전문가 교수님께서 만드셨던 R-tree를 Taxi R-tree 등 구현에 필요한 방향으로 개조하 여 사용했다.
* 프로그래밍시 사용 언어는 C언어이고, 컴파일러는 비주얼 C++ 6.0을 사용했다.
* 실험할 때는 교수님께서 만드셨던 R-tree가 리눅스에서 만들어진 프로그램으로 윈도우에서 제대로 동작하지 않는 문제가 발생하여 리눅스 페도라 운영체제에서 gcc를 통해 실험하였다.
- Taxi R-tree 구현
* Range query 인 반경 3Km는 택시 공간에서는 다이아몬드 형태가 되므로 일반적 R-tree에서의 사각형 영억을 검사하는 OVERLAP 매 크로에서 다이아몬드 영역을 검사하는 매크로로 수정하였다.
* 다이아몬드 OVERLAP의 기본적 원리는 Overlap b/w Diamond and Rectangle, 즉 Filter step과 Refinement step을 걸치는 방법을 사용 하였으며, 그중 Filter step은 수정 전의 사각형 OVERLAP을 사용하 였다. Refinement step에 사용된 원리는 아래 그림과 같이 부등식의 영역을 활용하였다.
3. 연구 결과 및 시사점
□ 연구 결과
○ 내비게이션과 관련된 이론 조사
- 내비게이션 시장 현황과 시중에 출시된 제품 스펙, 내비게이션 경로탐색 알고리즘의 순서, 보로노이 다각형, 트리, 그래프 이론, 다익스트라 알고리즘 등 연구를 위해 알아야 할 것들을 역할을 분담하여 조사하였다.
○ 실험에 필요한 프로그래밍 언어 학습
- 내비게이션 알고리즘을 직접 프로그래밍하여 실험하기 위해 전문가 교수님의 자문을 받아 프로그래밍 언어를 학습받음
- 처음엔 BASIC을 배우려 했으나 기존의 R-tree가 C언어로 되어있었기 때문에 BASIC으로 프로그램을 구현하려면 처음부터 모두 코딩을 해야 했기 때문에 C언어를 배우기로 결정
○ 내비게이션 업체 방문
- 위치기반 전문업체 ‘휴빌론’을 찾아가 위치기반 서비스에 관한 수업을 듣고, 연구 활동에 대한 조언을 들음
○ 가까운 주유소 찾기 알고리즘 및 R-tree 프로그래밍
- 전문가 교수님께 배운 프로그래밍 언어를 활용하여 교수님께서 프로그래밍하셨던 R*-tree를 우리 연구 활동에 적합하게 개조 - 기존 R-tree와 TAXI R-tree의 두가지 방면으로 프로그래밍하여 실험에 활용
○ 기존 R-tree와 Taxi R-tree 비교 실험
- 두 트리에 대해 범위 내의 주유소를 찾는 윈도우 쿼리를 실행하였다.
- 전체 영역의 1/4, 1/8부터 1/1024까지 다양한 범위에 대해 각 범위당 10번씩 테스트하여 평균값을 내었고, 이러한 과정을 4번 실행하였다.
- 각 트리의 효율은 검사 시의 트리 노드의 접근 횟수를 기준으로 잡았다. 그런데 R-tree의 노드들은 우선 메인 메모리 버퍼에 저장된 다. 따라서 버퍼 접근 횟수가 트리 노드 접근 횟수와 같다. 버퍼 접근
횟수가 적을수록 좋은 트리라고 가정하였다.
- 이러한 실험 결과를 그래프로 표시한다. 세로축은 버퍼 접근 횟수, 가로축은 검색 범위(size 1/4의 경우 전체 영역의 1/4를 의미)를 나타낸다. diamond가 결과가 더 좋을 것이라고 예측한 Taxi R-tree이고, rectangle이 기존의 유클리드 R-tree이다.
○ 기존 R-tree와 Taxi R-tree 비교 실험 결과 - 실험 1
영역의 1/4, 1/8의 범위에서는 Taxi R-tree가 효율이 좋고, 1/32 이하의 범위에서는 기존 R-tree가 미세하게 효율이 좋다.
- 실험 2
항상 Taxi R-tree가 효율이 좋으나, 1/16 이하의 범위에서는 그
차이가 미미하다.
- 실험 3
실험 1과 전체적으로 비슷한 결과가 나왔다.
- 실험 4
실험 2와 비슷한 결과가 나왔다.
○ 실험 결과 정리
- 범위를 넓게 잡을수록 Taxi R-tree의 효율이 더 좋았다.
- 범위가 좁아질수록 둘의 효율이 크게 차이나지 않는 것으로 나타났다.
- 예상했던 것처럼 좁은 범위에서도 더 좋은 효율을 보이지는 않았지만, 기존 유클리드 R-tree보다 좋은 효율을 보임에는 틀림이 없다.
○ 연구 결론
- 택시기하학을 R-tree에 적용함으로써 더 좋은 효율을 얻어낼 수 있다.
- 우리가 사는 세상을 유클리드평면보다 택시평면에 가깝다고 가정했 을 때, 기존의 R-tree보다는 TAXI R-tree를 사용하는 것이 효율적일 수 있다는 결론을 얻을 수 있다.
- 하지만 좁은 범위에서의 성능 향상이 원했던 만큼 이루어지지 않은 점에서 아쉬웠고, 더 연구해야할 필요성을 느꼈다.
□ 시사점
○ 기존 유클리드 기하학과 택시기하학을 비교, 분석하는 과정을 통해 비유클리드 기하학에 관한 지식과 유클리드 기하학의 한계를 다른 방법으로 해결하는 방법에 대해 생각해보는 계기를 가졌다.
○ 클러스터링 알고리즘 및 트리를 연구하고, 시중에 출시된 내비게이션 을 조사함으로써 우리 주변의 지리 정보를 어떻게 저장하고, 불러와 활용하는지에 관하여 학습하였다.
○ R-tree 및 알고리즘을 프로그래밍 하기 위해 프로그래밍 언어를 학습하고, 다익스트라 알고리즘 등 내비게이션과 관련된 이론을 배 워 내비게이션 알고리즘에 관하여 알게 되었다.
○ 연구 결과로 얻은 TAXI R-tree는 넓은 범위에서의 버퍼 읽음 횟수 측면에서 기존의 R-tree보다 뛰어난 측면을 보였다. 따라서 지리적 데이터의 택시평면으로서의 특성이 필요한 경우 TAXI R-tree는 R-tree의 좋은 개선안이 될 수 있을 것이다.
4. 홍보 및 사후 활용
□ 내비게이션 탑재 및 실용화
○ 위치기반 서비스 업체 ‘휴빌론’을 방문하여 실제 내비게이션에 탑재 및 실용화의 가능성을 검토했으나, 최적화 등의 문제로 시장에 서 직접 활용하기는 힘들 것으로 보인다.
○ 따라서 당장에 실용화하기는 불가능하나 후에 이 점을 보완하여 실제 로 실용화까지 가능한 택시 R-tree 알고리즘을 목표로 후속 연구를 추진할 계획을 가지고 있다.
○ 내비게이션에 직접 활용하기에는 무리가 따르더라도, 알고리즘 상으 로는 문제가 없기에 콜택시를 부른 사람과 가장 가까운 택시를 찾는 등의 다른 방면에서 활용 가능한 다른 실용화 방안을 검토하고 있다.
□ 논문집 게재
○ 자문 교수님의 의견에 따르면 연구 결과가 조금 단순하고 미흡한 면이 있지만, 조금 더 추가적인 연구를 한다면 좋은 결과를 얻을 수 있겠다는 기대를 갖고 후에 추가적으로 연구를 진행하겠다.
○ 추가 연구의 결과가 좋다면 논문으로서 이론적 가치는 충분하다고 판단되므로 교수님의 도움을 받아 겨울 방학 기간에 논문을 집필하여 국내 또는 해외의 논문지에 게재하겠다.
5. 참고문헌
□ 논문 및 자료
○ N. Beckmann, H.-P. Kriegel, R. Schneider and B. Seeger, "The R*-tree : An Efficient and Robust Access Method for Points and Rectangles," ACM SIGMOD Conference, 1990.
○ N. Roussopoulos, S. Kelley and F. Vincent, "Nearest Neighbor Queries," ACM SIGMOD Conference, 1995.
○ 장경윤, "택시기하 (Taxicab-geometry) : 교사와 학생을 위한 비유 클리트 기하학," 대한수학교육학회논문지, 제4권, 1호, 1994
○ Antonin Guttman, “R-TREES: A DYNAMIC INDEX STRUCTURE FOR SPATIAL SEARCHING,” ACM SIGMOD Conference, 1984.
○ Voronoi diagram, Wikipedia,
http://en.wikipedia.org/wiki/Voronoi_diagram
○ Shashi Shekhar, Ranga Raju Vatsavai, Xiaobin Ma, and JinSoung Yoo, "Chapter 3. Navigation System: A Spatial Database," Location-based Services, The Morgan Kaufmann Series in Data Management Systems, 2004.
