초록 ▼

1. 분석자 서문
로봇, 기계설계, GIS, 전자회로, 몰핑과 같이 물체를 다루고자 하는 기계공학 또는 컴퓨터공학 등 대부분의 공학문제에서는 삼차원의 복잡한 형상을 가진 대상물체를 일단 메쉬형태로 단순화하는 접근방법이 일반적이다. 그 단순화된 메쉬를 모델링에 활용하기 위해 기하학적 정보를 측정하는 일, 특히 메쉬 표면 상에 있는 두 점 간의 최단거리를 구하는 문제는 단순히 물체의 치수를 측정하는 것뿐만 아니라 공구나 로봇의 최적이동경로, 유체의 흐름 분석, 교통흐름분석, 텍스처 매핑, 얼굴 인식 등에 있어서 많은 활용도를 가

1. 분석자 서문
로봇, 기계설계, GIS, 전자회로, 몰핑과 같이 물체를 다루고자 하는 기계공학 또는 컴퓨터공학 등 대부분의 공학문제에서는 삼차원의 복잡한 형상을 가진 대상물체를 일단 메쉬형태로 단순화하는 접근방법이 일반적이다. 그 단순화된 메쉬를 모델링에 활용하기 위해 기하학적 정보를 측정하는 일, 특히 메쉬 표면 상에 있는 두 점 간의 최단거리를 구하는 문제는 단순히 물체의 치수를 측정하는 것뿐만 아니라 공구나 로봇의 최적이동경로, 유체의 흐름 분석, 교통흐름분석, 텍스처 매핑, 얼굴 인식 등에 있어서 많은 활용도를 가진 고전적으로 중요한 주제이다. 이러한 최단경로 알고리즘의 관건은 빠른 시간 안에 값을 구하는 것, 즉 시간복잡도(time complexity)를 줄이는 것과 저장 공간을 최소화 하는 것, 즉 공간복잡도(space complexity)를 줄이는 것이다. 본 고에서는 대표적인 최단경로 알고리즘들을 소개하며 그 세부구성을 정확도, 가중치, 공간복잡도, 시간복잡도, 실용성 등의 다섯 가지 기준에 대해 비교하고자 한다.
2. 목차
1. 개요
2. 그래프 이론 접근법2.1. 기하학적 거리 가중(Euclidean cost metric)2.2. 추가적인 가중치가 부여되는 경우(weighted cost metric)
3. 미분기하학적 접근법(sample based approach)
4. 분석자 결론
References
3. 원문정보
Prosenjit Bose, Anil Maheshwari, Chang Shu, Stefanie Wuhrer/ A survey of geodesic paths on 3D surfaces/ Computational Geometry/ November 201
※ 이 자료의 분석은 특허청의 설인환님께서 수고해 주셨습니다.