| 1 |
1
보로노이 다이어그램을 적용한 도로 전체 네트워크에서, 보로노이 셀의 경계지점 간의 최소거리 행렬을 포함하는 경계선 최소거리 정보를 저장하는 저장부; 및,
상기 저장부에 저장된 경계선 최소거리 정보를 이용하여 소정 개수의 최근접점(nearest neighbor) 질의를 처리한 후 상기 처리된 질의 결과에 해당하는 POI를 제공하는 최근접 질의 처리부
를 포함하는 보로노이 다이어그램을 기반으로 한 최근접점 탐색 시스템
|
| 2 |
2
제1항에 있어서,
상기 저장부는;
상기 전체 네트워크에서 보로노이 셀의 경계지점을 포함한 셀 정보를 저장하는 셀 정보 저장부와,
상기 보로노이 셀 내부의 POI(point of interest)와 노드 간의 최소거리 및, POI와 경계지점 간의 최소거리를 포함한 셀 최소거리 정보를 저장하는 셀 최소거리 저장부와,
상기 전체 네트워크에서 경계지점 간의 최소거리 행렬을 포함한 경계선 최소거리 정보를 저장하는 경계선 최소거리 저장부
를 포함하는 보로노이 다이어그램을 기반으로 한 최근접점 탐색 시스템
|
| 3 |
3
제2항에 있어서,
상기 최근접 질의 처리부는;
기 설정된 경로 상에서 소정 개수의 최근접점의 POI를 요청하는 질의에 따라 상기 저장부에 저장된 셀 정보, 셀 최소거리 정보, 경계선 최소거리 정보를 근거로 상기 질의 지점을 기준으로 인접한 최근접점을 검색하는 최근접점 질의 알고리즘을 제공하는 것을 특징으로 하는 보로노이 다이어그램을 기반으로 한 최근접점 탐색 시스템
|
| 4 |
4
보로노이 다이어그램을 적용한 도로 전체 네트워크에서, 보로노이 셀의 경계지점 간의 최소거리 행렬을 포함하는 경계선 최소거리 정보를 유지하는 단계;
상기 경계선 최소거리 정보를 이용하여 임의의 질의 지점에 해당하는 소정 개수의 최근접점(nearest neighbor)을 검색하는 단계; 및,
상기 질의 지점에 대하여 검색된 최근접점에 해당하는 POI를 제공하는 단계
를 포함하는 보로노이 다이어그램을 기반으로 한 최근접점 탐색 방법
|
| 5 |
5
제4항에 있어서,
상기 전체 네트워크에 대하여 보로노이 셀의 경계지점을 포함한 셀 정보와, 각 보로노이 셀 내부의 POI(point of interest)와 노드 간의 최소거리 및, POI와 경계지점 간의 최소거리를 포함한 셀 최소거리 정보를 유지하는 단계
를 더 포함하는 보로노이 다이어그램을 기반으로 한 최근접점 탐색 방법
|
| 6 |
6
제5항에 있어서,
상기 전체 네트워크에 대한 경계선 최소거리 정보를 유지하는 단계는;
서로 다른 두 경계지점을 지정하는 단계와,
상기 지정된 두 경계지점 간에 가능한 적어도 하나의 거리 행렬을 생성하는 단계와,
상기 생성된 적어도 하나의 거리 행렬 중 최소의 거리 값을 갖는 상기 두 경계지점 간의 최소거리 행렬을 설정하는 단계
를 포함하는 보로노이 다이어그램을 기반으로 한 최근접점 탐색 방법
|
| 7 |
7
제6항에 있어서,
상기 두 경계지점에 대한 적어도 하나의 거리 행렬 중 최소거리 행렬을 설정하는 단계는,
상기 지정된 두 경계지점을 포함하는 에지를 검색하는 단계와,
상기 에지를 구성하는 노드 간의 최소거리와, 상기 노드와 경계지점 간의 거리를 산출하는 단계와,
상기 산출된 노드 간의 최소거리 및, 상기 노드와 경계지점 간의 거리를 이용하여 각 거리 행렬에 대해 상기 두 경계지점 간의 거리를 산출하는 단계와,
상기 경계지점 간의 거리가 산출된 거리 행렬 중 최소 거리를 갖는 거리 행렬을 상기 두 경계지점 간의 최소거리 행렬로 설정하는 단계
를 포함하는 보로노이 다이어그램을 기반으로 한 최근접점 탐색 방법
|
| 8 |
8
제7항에 있어서,
상기 각 거리 행렬에 대한 두 경계지점 간의 거리는,
수식 1에 의해 산출되는 것을 특징으로 하는 보로노이 다이어그램을 기반으로 한 최근접점 탐색 방법
|
| 9 |
9
제5항에 있어서,
임의의 질의 지점에 대한 소정 개수의 최근접점을 검색하는 단계는;
상기 질의 지점을 포함하는 보로노이 셀을 검색하여 상기 검색된 보로노이 셀 내의 POI를 첫 번째 최근접점으로 설정하는 단계와,
상기 셀 정보와 셀 최소거리 정보 및 상기 경계선 최소거리 정보를 이용하여 상기 질의 지점과 이웃하는 보로노이 셀을 대상으로 상기 질의지점과 최소거리를 가지는 POI를 차례로 검색하여 다음 최근접점으로 설정하는 단계
를 포함하는 보로노이 다이어그램을 기반으로 한 최근접점 탐색 방법
|
| 10 |
10
제9항에 있어서,
상기 질의지점과 최소거리를 가지는 POI를 차례로 검색하여 다음 최근접점으로 설정하는 단계는,
상기 질의 지점을 포함하는 보로노이 셀을 검색하고 상기 검색된 보로노이 셀의 경계지점에서 상기 질의 지점까지의 거리(A)를 산출하는 단계와,
상기 저장된 경계선 최소거리 정보를 근거로, 상기 질의 지점을 포함하는 보로노이 셀과 이웃하는 보로노이 셀의 경계지점 간의 최소거리(B)를 검색하는 단계와,
상기 이웃하는 보로노이 셀에 해당하는 셀 최소거리 정보를 근거로, 상기 이웃하는 보로노이 셀의 경계지점과 상기 이웃하는 보로노이 셀의 POI 지점 간의 최소거리(C)를 검색하는 단계와,
상기 산출 또는 검색된 (A), (B), (C) 거리 값들을 이용하여 상기 질의지점에서 상기 POI 지점까지의 최소거리를 산출하는 단계
를 포함하는 보로노이 다이어그램을 기반으로 한 최근접점 탐색 방법
|
| 11 |
11
제10항에 있어서,
상기 질의지점을 포함하는 보로노이 셀의 경계지점에서 상기 질의 지점까지의 거리(A)를 산출하는 단계는,
상기 질의 지점을 포함하는 에지의 두 노드가 서로 다른 보로노이 셀을 가질 경우, 상기 질의 지점을 포함하는 보로노이 셀의 경계지점에서 상기 각 노드까지의 거리를 계산하여 그 중 최소거리를 갖는 거리를 상기 (A) 거리로 선택하는 것을 특징으로 하는 보로노이 다이어그램을 기반으로 한 최근접점 탐색 방법
|
| 12 |
12
제11항에 있어서,
상기 질의 지점을 포함하는 보로노이 셀의 경계지점에서 상기 질의지점까지의 거리(A)는,
수식 2에 의해 산출되는 것을 특징으로 하는 보로노이 다이어그램을 기반으로 한 최근접점 탐색 방법
|
| 13 |
13
제10항에 있어서,
상기 질의지점에서 상기 POI 지점까지의 최소거리는,
수식 3에 의해 산출되는 것을 특징으로 하는 보로노이 다이어그램을 기반으로 한 최근접점 탐색 방법
|
| 14 |
14
제10항에 있어서,
상기 질의지점과 최소거리를 가지는 POI를 차례로 검색하여 다음 최근접점으로 설정하는 단계는,
상기 셀 정보와 셀 최소거리 정보 및 상기 경계선 최소거리 정보를 근거로, 상기 질의 지점을 기준으로 순차적으로 POI를 확장하면서 각 POI에 대하여 상기 질의지점에서 POI 지점까지의 최소거리를 산출하는 단계와,
상기 산출된 질의지점에서 POI 지점까지의 최소거리를 최근접점을 결정하기 위한 최소 힙(minimum heap)에 삽입하여 거리 순으로 상기 질의 지점에 대한 최근접점을 결정하는 단계
를 더 포함하는 보로노이 다이어그램을 기반으로 한 최근접점 탐색 방법
|
| 15 |
15
제4항 내지 제14항 중 어느 한 항의 방법을 실행하기 위한 프로그램이 기록되어 있는 것을 특징으로 하는 컴퓨터에서 판독 가능한 기록 매체
|
