최단 경로 그래프
Shortest-path graph
수학 및 지리 정보 과학에서 최단 경로 그래프는 유클리드 평면의 점 집합에서 정의된 비방향 그래프다.최단 경로 그래프는 유추된 가장자리를 차지한 최단 경로가 포인트 세트로 대표되는 부정확한 영역을 차지한 최단 경로와 대략적으로 일치하도록 점 세트 사이의 가장자리를 추론하는 아이디어로 제안된다.최단 경로 그래프의 에지 세트는 단일 파라미터 t t 1에 따라 달라진다.가장자리의 무게가 매개변수 t ≥ 1의 힘으로 상승된 유클리드 길이로 정의되는 경우 가장자리는 끝점 사이의 최소 무게 경로인 경우에만 최단 경로 그래프에 나타난다.[1]
최단 경로 그래프의 속성
구성 파라미터 t가 무한대로 넘어가면 최단 경로 그래프가 포인트 세트의 최소 스패닝 트리가 된다.그래프는 포인트 세트의 가브리엘 그래프를 서브그래프로 나타내므로 딜라우나이 삼각측량도 서브그래프다.[1]
참조
- ^ a b de Berg, Mark; Meulemans, Wouter; Speckmann, Bettina (2011). "Delineating imprecise regions via shortest-path graphs". Proceedings of the 19th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems - GIS '11. Vol. 19. pp. 271–280. doi:10.1145/2093973.2094010. ISBN 9781450310314. S2CID 2359926. Retrieved 2 September 2019.
