1 |
1
사용자로부터 요청된 질의지점을 포함하는 질의영역을 설정하는 설정부;
보로노이 다이어그램을 적용한 보로노이 셀 중에서, 상기 질의영역에 포함되는 제1 이웃 보로노이 셀을 식별하는 탐색부;
상기 제1 이웃 보로노이 셀과 상기 질의영역 간의 최대거리를 산출하는 산출부; 및
상기 탐색부에서 상기 산출된 최대거리를 이용하여 상기 제1 이웃 보로노이 셀에 인접한 제2 이웃 보로노이 셀이 탐색되면, POI 후보 집합으로서 상기 탐색된 제2 이웃 보로노이 셀을 상기 사용자에게 제공하는 제공부
를 포함하는, 보로노이 다이어그램을 이용한 최근접점 탐색 시스템
|
2 |
2
제1항에 있어서,
상기 설정부는,
클로킹 알고리즘을 이용하여 상기 질의지점을 포함하는 질의영역을 설정하는, 보로노이 다이어그램을 이용한 최근접점 탐색 시스템
|
3 |
3
제1항에 있어서,
보로노이 다이어그램을 적용한 보로노이 셀에 포함된 POI 정보를 저장하는 저장 테이블
을 더 포함하고,
상기 탐색부는,
상기 저장 테이블을 참조하여 상기 질의영역에 포함되는 제1 이웃 보로노이 셀을 식별하는, 보로노이 다이어그램을 이용한 최근접점 탐색 시스템
|
4 |
4
삭제
|
5 |
5
제1항에 있어서,
상기 탐색부는,
상기 산출된 최대거리를 기준으로 오름차순 정렬하고, 정렬된 제1 이웃 보로노이 셀 중 첫번째에서 k(k는 1보다 큰 자연수)번째 최대거리를 이용하여 상기 제1 이웃 보로노이 셀에 인접한 제2 이웃 보로노이 셀을 탐색하는, 보로노이 다이어그램을 이용한 최근접점 탐색 시스템
|
6 |
6
제1항에 있어서,
상기 설정부는,
상기 사용자로부터 탐색할 POI 개수를 수신하고, 상기 수신된 POI 개수를 'k'로 설정하고,
상기 탐색부는,
상기 산출된 최대거리 중에서 상기 k번째 최대거리를 이용하여 상기 제1 이웃 보로노이 셀에 인접한 제2 이웃 보로노이 셀을 탐색하는, 보로노이 다이어그램을 이용한 최근접점 탐색 시스템
|
7 |
7
제1항에 있어서,
상기 산출부는,
상기 질의영역과 상기 탐색한 제2 이웃 보로노이 셀 간의 최소거리를 산출하고,
상기 탐색부는,
상기 산출된 최대거리 중에서 k 번째 최대거리 보다 작거나 같은 최소거리를 가지는 제2 이웃 보로노이 셀을 상기 제1 이웃 보로노이 셀에 포함시키는, 보로노이 다이어그램을 이용한 최근접점 탐색 시스템
|
8 |
8
제1항에 있어서,
상기 탐색부는,
상기 식별된 제1 이웃 보로노이 셀에 포함된 POI를 상기 POI 후보 집합에 포함시키는, 보로노이 다이어그램을 이용한 최근접점 탐색 시스템
|
9 |
9
제1항에 있어서,
상기 산출부는,
상기 질의영역과 상기 탐색한 제2 이웃 보로노이 셀 간의 최소거리를 산출하고,
상기 탐색부는,
상기 보로노이 다이어그램을 적용한 보로노이 셀 중에서, 상기 산출된 최대거리 중에서 k 번째 최대거리 보다 작거나 같은 최소거리를 가지는 제2 이웃 보로노이 셀에 인접한 보로노이 셀을 상기 제2 이웃 보로노이 셀에 포함시키는, 보로노이 다이어그램을 이용한 최근접점 탐색 시스템
|
10 |
10
사용자로부터 요청된 질의지점을 포함하는 질의영역을 설정하는 단계;
보로노이 다이어그램을 적용한 보로노이 셀 중에서, 상기 질의영역에 포함되는 제1 이웃 보로노이 셀을 식별하는 단계;
상기 제1 이웃 보로노이 셀과 상기 질의영역 간의 최대거리를 산출하는 단계;
상기 산출된 최대거리를 이용하여 상기 제1 이웃 보로노이 셀에 인접한 제2 이웃 보로노이 셀을 탐색하는 단계; 및
POI 후보 집합으로서 상기 탐색된 제2 이웃 보로노이 셀을 상기 사용자에게 제공하는 단계
를 포함하는, 보로노이 다이어그램을 이용한 최근접점 탐색 방법
|
11 |
11
제10항에 있어서,
보로노이 다이어그램을 적용한 보로노이 셀에 포함된 POI 정보를 저장 테이블에 저장하는 단계
를 더 포함하고,
상기 질의영역에 포함되는 제1 이웃 보로노이 셀을 식별하는 단계는,
상기 저장 테이블을 참조하여 상기 질의영역에 포함되는 제1 이웃 보로노이 셀을 식별하는 단계
를 포함하는 보로노이 다이어그램을 이용한 최근접점 탐색 방법
|
12 |
12
삭제
|
13 |
13
제10항에 있어서,
상기 제1 이웃 보로노이 셀에 인접한 제2 이웃 보로노이 셀을 탐색하는 단계는,
상기 산출된 최대거리를 기준으로 오름차순 정렬하는 단계; 및
상기 정렬된 제1 이웃 보로노이 셀 중 첫번째에서 k(k는 1보다 큰 자연수)번째 최대거리를 이용하여 상기 제1 이웃 보로노이 셀에 인접한 제2 이웃 보로노이 셀을 탐색하는 단계
를 포함하는, 보로노이 다이어그램을 이용한 최근접점 탐색 방법
|
14 |
14
제10항에 있어서,
상기 질의영역과 상기 탐색한 제2 이웃 보로노이 셀 간의 최소거리를 산출하는 단계;
상기 산출된 최대거리 중에서 k 번째 최대거리 보다 작거나 같은 최소거리를 가지는 제2 이웃 보로노이 셀을 상기 제1 이웃 보로노이 셀에 포함시키는 단계; 및
상기 제1 이웃 보로노이 셀에 포함된 POI를 상기 POI 후보 집합에 포함시키는 단계
를 더 포함하는, 보로노이 다이어그램을 이용한 최근접점 탐색 방법
|
15 |
15
제10항에 있어서,
상기 질의영역과 상기 탐색한 제2 이웃 보로노이 셀 간의 최소거리를 산출하는 단계; 및
상기 보로노이 다이어그램을 적용한 보로노이 셀 중에서, 상기 산출된 최대거리 중에서 k 번째 최대거리 보다 작거나 같은 최소거리를 가지는 제2 이웃 보로노이 셀에 인접한 보로노이 셀을 상기 제2 이웃 보로노이 셀에 포함시키는 단계
를 더 포함하는, 보로노이 다이어그램을 이용한 최근접점 탐색 방법
|