선택한 단어 수는 입니다.
최소 단어 이상 선택하여야 합니다.
최소 단어 이상 선택하여야 합니다.
선택한 단어 수는 30입니다.
최대 10 단어까지만 선택 가능합니다.
최대 10 단어까지만 선택 가능합니다.
문제 정의
- 도 연구가 계속 진 행 되 고 있다[1, 2, 3]. 본 논문에 서 는단순 다각형 내부에서 발생하는 최 단 경로 문제를 다룬다. 다각형 내부에 위치한 두 점 사이의 최단 경로는 다각형의 외부를 지나지 않는 경로 중에서 길이가 가장 짧은 경 로를 말한다.
- 특정 한 부류의 다각형에서 삼각분할 없이 최단 경로를 구하기 위해서는 다각형의 특성을 잘 고려해야 한다. 본 논문에서는 별형 다각형이나 에지가시 다각형을 포함하는 다각형 부류인 선분가시 다각형에 대해서 삼각분할이나 복잡한 자료구조의 구축 없이 두 점 사이의 최단 경로를 구하는 알고리즘을 제시 한다. 선분가시 다각형에서 다각형 내부를 전부 볼 수 있는 선분을 경 비 선분(guard segment) 또는 가시 선분(visiblesegment)이 라고 부른다.
- 본 논문에서는 선분가시 다각형 의 두 점 사이의 최단경로를 구하는 선형 시간 알고리즘을제시했다. 최단 경로를 구하는 기존의 알고리즘은 매우 복잡한 과정으로알려진 삼각분할을 전처리과정으로 수행해야 한다.
가설 설정
- (증명) 만일 ls{p, q) U 灵0, 3)이면 소정리가 성 립한다. 그렇지 않은 경우, Zs(p, g) 는 볼록 체인 c/i(«w)와는교차하지 않으므로 cHns) 와 교차한다.
- 모든 부분 체 인 ch(p, q) U c/i(w舶)에 대해서, 와 연결되어 단순 다각형을 형성하는 볼록 체인 应i(g, p)가 존재하면 c/i(ws) 를 매우 깔끔한 체 인(very tidy chain)이 라고 정의한다. 이 때, ch(岛p) 는 T7에서의 체인 c/i(g, p)를 대체한 임의의 볼록 체인이고 u P(v, w) 인 ch(w, v) 가 존재해야 한다. 다음의 소정 리 1은 매우 깔끔한 체인에서의 최 단경로는항상볼록경로가된다는 것을 보여준다.
- , %_])로 나타낸다. 서술의편의상, P의 어떤 세 점도 일직선 상에 있지 않다고 가정한다. 정 점 0의 내각이 180。보다 작으면 볼록 정 점이라고 부르고, 180o 보다 크면 오목 정점이라고 부른다.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.