선택한 단어 수는 입니다.
최소 단어 이상 선택하여야 합니다.
최소 단어 이상 선택하여야 합니다.
선택한 단어 수는 30입니다.
최대 10 단어까지만 선택 가능합니다.
최대 10 단어까지만 선택 가능합니다.
문제 정의
- 하나는 큰 원의 파형이고 나머지 둘은 도로에서 양쪽으로 뻗어 나가는 바늘 같온 모양을 하고있는 파형이다. 본 논문에서 가장 핵심적인 아이디어는 이 바늘 모양의 파형을 어떤 독립적인 새로운 싸이트로 간주한다는 것이다. 이 새롭게 만들어진 싸이트로부터 새로운 파형이럳어나오고 이것은 또 다른 도로에 부딪혀서 또 다른 바뉼 모양의 파형을 만들어 낼 것이다・
- 이것을 도로망 G가 주어진 경우의 거리로 정의하며 로 표시한다. 이런 가정하에 평면상의 n개의 점들의 집합 S가 주어질 경우 S에 대한 보로노이 다이어그램 %(S)를 정의할 수 있으며' 본 논문에서는 va(s)블 O(nm2 1ogn + m3logm)시간 안에 계산할 수 있는 알고리즘을 제안한다. 여기서 me 주어진 도로망의 도로의 개수이다.
가설 설정
- 수의 변형과 그 응용 또한 이미 밝혀져 있다. [시 본 논문에서는 유클리드 평면상에 도로망이 주어져 있어서 여행자들이 그 도로들을 이용하여 더욱 빠르게 이동할 수 있을 경우를 가정한다. 기본적으로 여행자들은 도로의 어느 점에서든지 출입이 가능하다.
- G는 평면상에 임 베드 되어 있어서 각 도로는 평면상의 선분으로 표현할 수 있다. 또한 각 도로 e에는 개별적인 속도 讽e)가 주어지며, 도로 밖에서의 속도는 1이라고 가정한다. 보통의 유클리드 평면상에서의 거리는 두 점사 이의 직선거리(즉, S norm)를 이용하지만 본 논문에서는 직선거리가 아닌, 도로를 사용하면서 갈 수 있는 가장 빠른 시간을 "거리'로 간주한다.
- Abellanas 등 [1]과 Aichholzer 둥 岡은 Li 평면상에 도로망이 있을 경우에 대해 연구하였는데 특히 후자의 논문에서는 모든 도로가 工축 또는 3축과 평행하고 모든 도로의 속도가 동일한 경우에 대하여 문제를 해결하였으며 이것이 이전의 가장 일반화된 문제에 대한 해결이었다. 본 논문에서는 이전의 결과들 보다 훨씬 더 일반적인 경우인, 유클리드 평면상에 도로망이 직선의 간선을 갖는 평면 그래프로 주어지고 각 도로의 속도도 개별적으로 주어지는 경우를 가정한다.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.