The Lower Bound of the Distance between the Start point and End point of Axis-reachable 2-dimensional Rectilinear Chain
Hyun Tark, Chan-Su Shin · 정보과학회 컴퓨팅의 실제 논문지 · 2022
+x축 방향으로 원점을 떠나 x축 또는 y축에 평행한 방향으로만 격자점 간을 이동하며 자기 자신과 만나지 않는 경로를 ‘직교 경로’라 한다. 직교 경로는 현재 진행방향으로부터 반시계 또는 시계 방향으로 90도 회전하는 두 가지의 방향전환만을 가지며, 전자는 L, 후자는 R로 지칭한다. L과 R로 이루어진 하나의 ‘방향전환 문자열’로 한 직교 경로의 방향전환을 순서대로 표현할 수 있다. 반대로, 직교 경로의 각 선분의 길이는 자연수 중에서 자유롭게 선택할 수 있기에 하나의 방향전환 문자열을 따르는 직교 경로는 여러 가지가 존재한다. 이 논문은 주어진 방향전환 문자열을 따르는, +x축, -x축, +y축, _y축 중 적어도 하나에 도달 가능한 직교 경로의 출발점(원점)과 도달점 간 거리에 대한 개선된 하한을 제시한다.