평면에 여러 개의 분리 된 간단한 다각형이 있고 모든 다각형 외부에 두 개의 점 와 가 있다고 가정 합니다. 유클리드 최단 경로 문제는 다각형의 내부와 교차하지 않는 에서 까지 유클리드 최단 경로를 계산하는 것 입니다. 구체적으로, 및 의 좌표와 모든 다각형 정점의 좌표는 정수 라고 가정합니다 .s

$s$t

$t$s

$s$t

$t$s

$s$t

$t$

이 문제를 다항식 시간으로 해결할 수 있습니까?

즉시 물론, 네 말을 대부분의 계산 기하학 : 존 허쉬 버거와 수 바시 수리는 에서 계산하여 유클리드 최단 경로, 그 알고리즘 설명 시간을, 그리고 바인딩이 시간은 대수 계산 트리 모델에 최적입니다. 불행히도, Hershberger와 Suri의 알고리즘 (그리고 그 전후의 거의 모든 관련 알고리즘)은 다음과 같은 강력한 의미에서 정확한 실제 산술 을 요구하는 것 같습니다 .O(nlogn)

$O(n\log n)$

모든 내부 정점이 장애물 정점 인 경우 유효한 다각형 경로를 호출합니다 . 모든 유클리드 최단 경로가 유효합니다. 유효한 경로의 길이는 정수의 제곱근의 합입니다. 따라서 두 유효한 경로의 길이를 비교하려면 다항식 시간에 수행하는 방법을 모르는 두 제곱근의 합을 비교해야합니다 .

더욱이, 제곱근 문제의 임의의 인스턴스가 동등한 유클리드 최단 경로 문제로 감소 될 수 있다는 것은 완전히 그럴듯 해 보인다.

그래서 : 유클리드 최단 경로를 계산하는 다항식 시간 알고리즘이 있습니까? 아니면 NP-hard 문제입니까? 또는 제곱근 근경 ? 또는 다른 것?

몇 가지 참고 사항 :

• 적어도 다각형의 삼각 측량이 주어진 경우 표준 깔때기 알고리즘을 사용하여 이상한 숫자 문제없이 하나의 다각형 내부 또는 외부의 최단 경로를 시간 으로 계산할 수 있습니다 .O(n)

  $O(n)$

  $O(n)$

• 실제로 부동 소수점 산술은 부동 소수점 정밀도까지 가장 짧은 경로를 계산하기에 충분합니다. 나는 정확한 문제 의 복잡성에만 관심이 있습니다.

• 존 캐니 (John Canny)와 존 레이프 (John Reif) 는 3- 공간에서 해당하는 문제가 NP-hard라는 것을 증명했다 (지난 수의 최단 경로가있을 수 있기 때문에). 최준수, 위르겐 셀렌 (Jürgen Sellen) 및 치 Ya p (Chee-Keng Yap )은 다항식 근사법을 설명했다.

• Simon Kahan과 Jack Snoeyink 는 간단한 다각형에서 최소 링크 경로 관련 문제에 대해 유사한 문제를 고려했습니다.

답변