랜덤 점의 정렬

평면에서 임의의 점의 정렬이란 평면 영역에 임의로 배치된 더 큰 점 집합 내에서 대략 직선을 차지하는 점의 부분 집합을 발견하는 연구를 말합니다.연구에 따르면 그러한 거의 정렬은 직관적으로 예상할 수 있는 것보다 더 큰 빈도로 우연히 발생합니다.

이것은 지지자들이 제시한 초자연적 또는 인류학적 설명과는 달리, 몇몇 사람들이 깊은 의미가 있는 현상이라고 믿는 레이 라인과 다른 유사한 신비로운 정렬이 단지 우연 때문에 존재할 수도 있다는 증거로 제시되었습니다.이 주제는 컴퓨터 비전과 천문학 분야에서도 연구되었습니다.

여러 연구에서 평면 상의 임의의 점들의 정렬에 대한 수학을 조사했습니다.^[1][2][3][4]이 모든 것에서 선의 너비(완벽한 직선으로부터 점의 위치를 이동하는 것의 허용)는 중요합니다.이것은 실제 특징이 수학적인 점이 아니라는 사실과 그들의 위치가 정확히 정렬될 필요가 없다는 사실을 허용합니다.Alfred Watkins는 그의 고전적인 작품인 "The Old Straight Track"에서 지도 위의 연필 선의 너비를 선형으로 간주될 수 있는 허용 오차의 한계로 사용했습니다.예를 들어 1:50,000 축척의 Ordnance Survey 맵에 1mm 연필 선을 사용하여 선형을 그립니다. 지면의 해당 너비는 50m입니다.^[5]

우연 정렬 확률 추정치

직관과는 반대로, 임의로 배치된 풍경의 점들 사이의 선형을 찾는 것은 고려할 지리적 영역이 증가함에 따라 점진적으로 쉬워집니다.이 현상을 이해하는 한 가지 방법은 해당 영역에 있는 점 집합의 가능한 조합의 수가 증가하면 해당 영역에 있는 점 집합이 정렬될 확률이 감소하는 것을 압도한다는 것입니다.

일반적으로 인정되는 "정렬"의 의미를 표현하는 한 가지 정의는 다음과 같습니다.

지정된 랜드마크 점 집합에서 선택된 점 집합으로, 모든 점이 지정된 폭의 적어도 하나의 직선 경로 내에 있습니다.

더 정확하게 말하면, 너비 w의 경로는 평면 상의 직선의 w/2 거리 내의 모든 점들의 집합, 구면 상의 대원 또는 일반적으로 다른 종류의 다양체 상의 임의의 측지선으로 정의될 수 있습니다.일반적으로 이러한 방식으로 정렬된 주어진 점 집합에는 무한히 다른 직선 경로가 많이 포함됩니다.따라서 점들의 집합이 선형인지 여부를 결정하기 위해서는 적어도 하나의 직선 경로가 존재해야 합니다.이러한 이유로 경로 자체보다는 점 집합을 세는 것이 더 쉽습니다.발견된 선형의 수는 허용된 너비 w에 매우 민감하며, w에^k-2 비례하여 증가합니다. 여기서 k는 선형의 점 개수입니다.

다음은 균일하게 분포된 "상당한" 점으로 덮인 평면을 가정할 때 선형 가능성에 대한 매우 근사적인 크기의 추정치입니다.

지름이 L이고 넓이가 L인 콤팩트한 영역에 있는 n개의 점 집합을 생각해 보십시오. 유효한 선은 모든 점이 선의 거리 w/2 이내에 있는 것으로 간주합니다(즉, 너비 w의 트랙 위에 있고, 여기서 w ≪ L).

n개의 점에서 순서가 매겨진 k개의 점을 모두 고려해 보십시오. 이 중에는 다음과 같은 것들이 있습니다.

${\displaystyle {\binom {n}{k}}={\frac {n!}{(n-k)!\,k!}}$

(표기 방법은 요인 및 이항 계수 참조).

주어진 k개의 점들의 부분집합이 위에서 정의된 방식으로 대략적으로 공선일 확률을 추정하기 위해, 그 부분집합의 "최좌측"과 "최우측" 두 점 사이의 선(일부 임의의 좌/우축의 경우: 예외적인 수직의 경우 위와 아래를 선택할 수 있습니다)을 고려합니다.이 두 점을 통해 약간의 직선을 그릴 수 있습니다.부분 집합의 나머지 k-2 점 각각에 대해 점이 선에 "충분히 가까이" 있을 확률은 대략 w/L이며, 이는 선 공차 영역의 면적(대략 wL)과 전체 면적(대략 L²)의 비율을 고려하면 알 수 있습니다.

따라서 위의 대략적인 추정치를 바탕으로 전체 집합에서 예상되는 k-점 선형의 수를 대략 다음과 같이 추정할 수 있습니다.

${\displaystyle {\frac {n!}{(n-k)!}\left({\frac {w}{L}}\right)^{k-2}}$

다른 것들 중에서, 직관과 반대로, 주어진 선폭에서 점들로 덮인 평면에서 임의의 기회로부터 예상되는 k-점선의 수가 고려된 면적의 크기에 따라 선형보다 훨씬 더 증가한다는 것을 보여주는 데 사용될 수 있습니다.점들의 가능한 조합들의 수에서 증가의 조합 폭발이 임의의 조합 줄 세우기의 난이도의 증가를 보충하는 것 이상이기 때문입니다.

예상되는 선형 수에 대한 보다 정확한 추정

유사하지만 더 신중한 분석을 사용하면 변 L의 정사각형에 무작위로 배치된 n개의 점들 중에서 우연히 예상되는 최대 너비 w와 최대 길이 d의 3점 정렬의 수에 대한 더 정확한 표현을 찾을 수 있습니다.

${\displaystyle \mu = {\frac {\pi}{3}}{\frac {w}{L}}\left({\frac {d}{L}\right)^{3}n\left(n-1\right)\left(n-1\right)}$

≈ L과 k = 3을 설정하면 상수 인자까지 위의 대략적인 추정치와 동일한 예측을 할 수 있습니다.

모서리 효과(사각형의 경계에서 손실된 선형)가 포함된 경우 식은

${\displaystyle \mu = {\frac {\pi}{3}}{\frac {w}{L}}\left({\frac {d}{L}\right)^{3}n\left(n-1\right)\left(n-1\right)\left(1-{\frac {3}{\pi }}\left(1-{\frac {d}{L}\right)+{\frac {3}{5}}\left ({\frac {4}{\pi}}-1\right)\left ({\frac {d}{L}\right)^{2}\right)}$

k-점 선형에 대한 일반화(에지 효과 무시)는^[3]

${\displaystyle \mu = {\frac {\pin\left(n-1\right)\left(n-1\right)\cdots \left(n-\left(k-1\right))\right)}{k\left(k-2\right)!}}\left({\frac {w}{L}}\right)^{k-2}\left({\frac {d}{L}}\right)^{k}}$

동일한 이유로, 앞 절의 조대 근사치와 대략 비슷한 점근적 스케일링 특성을 가지고 있습니다; 큰 n에 대한 조합 폭발이 다른 변수들의 효과를 압도합니다.

선형 컴퓨터 시뮬레이션

컴퓨터 시뮬레이션에 따르면 평면의 점들은 위의 규모 추정치와 일치하는 숫자에서 레이 사냥꾼들이 발견한 것과 유사한 정렬을 형성하는 경향이 있으며, 레이 선이 우연히 생성될 수도 있음을 시사합니다.이 현상은 포인트가 컴퓨터에 의해 의사 랜덤으로 생성되었는지, 피자 레스토랑 또는 전화 부스와 같은 일상적인 기능의 데이터 세트로부터 생성되었는지에 관계없이 발생합니다.

폭이 수십 킬로미터인 지도에서는 w = 50 m인 비교적 작은 피쳐 집합에서도 4~8 포인트의 선형을 쉽게 찾을 수 있습니다.면적이 더 크거나 형상 집합이 더 조밀하거나 w 값이 더 크면 20개 이상의 점으로 된 선형을 쉽게 찾을 수 있습니다.

참고 항목

• 아포페니아
• 군집 착시
• 우연
• 완전 공간임의성
• 일반직위
• 패턴인식
• 프로크러스트 분석
• 램지 이론, "피할 수 없는 우연"에 대한 개념
• 통계형상해석

참고문헌