가시성 그래프
Visibility graph계산 기하학 및 로봇 모션 계획에서 가시성 그래프는 일반적으로 유클리드 평면의 점 및 장애물 집합에 대해 분할할 수 없는 위치를 그래프로 나타낸 것이다.[1] 그래프의 각 노드는 점 위치를 나타내며, 각 에지는 점 사이의 가시적 연결을 나타낸다. 즉, 두 위치를 연결하는 선 세그먼트가 장애물을 통과하지 못하면 그래프에서 그 사이에 가장자리가 그려진다. 위치 세트가 일렬로 놓여 있을 때, 이것은 순서 시리즈로 이해할 수 있다. 따라서 가시성 그래프는 시계열 분석 영역으로 확장되었다.
적용들
가시성 그래프는 평면의 다각형 장애물 집합 중에서 유클리드 최단 경로를 찾는 데 사용될 수 있다: 두 장애물 사이의 최단 경로는 장애물의 정점을 제외하고 직선 세그먼트를 따르므로 유클리드 최단 경로는 노드가 시작하는 가시성 그래프에서 최단 경로가 된다.목적지 지점과 장애물의 정점.[2] 따라서 유클리드 최단 경로 문제는 가시성 그래프를 구성하고 Dijkstra 알고리즘과 같은 최단 경로 알고리즘을 그래프에 적용하는 두 가지 간단한 하위 문제로 분해될 수 있다. 장애물에 비해 불가결한 크기를 가진 로봇의 움직임을 계획하기 위해, 로봇의 크기를 보상하기 위해 장애물을 확장한 후 유사한 접근법을 사용할 수 있다.[2] 로자노-페레즈 & 웨슬리(1979)는 닐 닐슨이 1969년 셰이키 로봇의 모션 계획에 대해 연구한 유클리드 최단 경로에 대한 가시성 그래프 방법을 예로 들며, 1973년 러시아 수학자 M. B. 이그나트예프, F. M. 쿨라코프, A의 이 방법에 대한 설명을 인용하기도 한다. M. 포크로브스키.
가시성 그래프는 또한 라디오 안테나 배치 계산에 사용하거나 가시성 그래프 분석을 통해 건축 및 도시 계획 내에서 사용되는 도구로 사용될 수 있다.
선에 놓여 있는 위치 집합의 가시성 그래프는 시계열의 그래프 이론적 표현으로 해석할 수 있다.[3] 이 특별한 경우는 시계열, 동적 시스템, 그래프 이론 사이에 다리를 만든다.
특성화
단순 폴리곤의 가시성 그래프는 폴리곤의 정점을 포인트 위치로 하고, 폴리곤의 외관은 유일한 장애물로 한다. 단순 다각형의 가시성 그래프는 반드시 해밀턴 그래프여야 한다. 폴리곤의 경계는 가시성 그래프에서 해밀턴 사이클을 형성한다. 모든 가시성 그래프가 단순한 다각형을 유도하는 것은 아니라고 알려져 있다. 사실, 단순 다각형의 가시성 그래프는 소수의 특수 등급의 그래프의 특성을 가지고 있지 않다.[4]
관련 문제
미술관 문제는 이 세트에서 다른 모든 비점수 점들이 보일 정도로 작은 점 집합을 찾는 문제다. 미술관 문제의 특정 형태는 가시성 그래프에서 지배적인 집합을 찾는 것으로 해석될 수 있다.
폴리곤이나 곡선으로 된 계통의 이탄젠트는 접촉점에서 두 개의 이탄젠트를 관통하지 않고 두 개의 이탄젠트를 만지는 선이다. 폴리곤 집합의 비트엔젠트는 폴리곤의 정점을 노드로 하고 폴리곤 자체를 장애물로 하는 가시성 그래프의 서브셋을 형성한다. 유클리드 최단 경로 문제에 대한 가시성 그래프 접근방식은 유클리드 최단 경로의 경우, 유클리드 최단 경로의 경우 비탄젠트를 따라 장애물의 경계로 들어가거나 나갈 수 있기 때문에 모든 가시성 가장자리를 사용하는 대신 이탄젠트에서 그래프를 구성하여 속도를 높일 수 있다.[5]
참고 항목
메모들
- ^ Niu, Hanlin; Savvaris, Al; Tsourdos, Antonios; Ji, Ze (2019). "Voronoi-Visibility Roadmap-based Path Planning Algorithm for Unmanned Surface Vehicles". Journal of Navigation. 72 (04): 850–874. doi:10.1017/S0373463318001005. ISSN 0373-4633.
- ^ a b 데 버그 외 (2000), 섹션 5.1 및 5.3; 로자노-페레즈 & 웨슬리(1979년).
- ^ Lacasa, Lucas; Luque, Bartolo; Ballesteros, Fernando; Luque, Jordi; Nuño, Juan Carlos (2008). "From time series to complex networks: The visibility graph". Proceedings of the National Academy of Sciences. 105 (13): 4972–4975. arXiv:0810.0920. doi:10.1073/pnas.0709247105. PMC 2278201. PMID 18362361.
- ^ Ghosh, S. K. (1997-03-01). "On recognizing and characterizing visibility graphs of simple polygons". Discrete & Computational Geometry. 17 (2): 143–162. doi:10.1007/BF02770871. ISSN 0179-5376.
- ^ 데 버그 외 (2000), 페이지 316.
참조
- de Berg, Mark; van Kreveld, Marc; Overmars, Mark; Schwarzkopf, Otfried (2000), "Chapter 15: Visibility Graphs", Computational Geometry (2nd ed.), Springer-Verlag, pp. 307–317, ISBN 978-3-540-65620-3.
- Lozano-Pérez, Tomás; Wesley, Michael A. (1979), "An algorithm for planning collision-free paths among polyhedral obstacles", Communications of the ACM, 22 (10): 560–570, doi:10.1145/359156.359164, S2CID 17397594.
