불규칙하게 분포된 2D 또는 그 이상의 다차원 점(point) 데이터를 효율적인 격자(grid) 구조로 변환하는 새로운 알고리즘 '카르테시안 그리드 정렬(Cartesian Grid Sort)'이 공개되었습니다. 이 알고리즘은 'SquareNet'이라는 그리드화 엔진의 핵심 절차를 시연하기 위해 개발되었으며, 공간적으로 일관된 다중 인덱스 구조가 필요한 다양한 분야에 활용될 수 있습니다.
카르테시안 그리드 정렬은 N개의 유클리드 점을 처리하여 M x M 격자 형태의 텐서로 변환합니다. 핵심 아이디어는 간단합니다. 먼저, 점들을 무작위로 2D 멀티 키(multi-key) 격자로 나눈 후, x축 좌표를 기준으로 행(row)을 정렬하고, 이어서 y축 좌표를 기준으로 열(column)을 정렬하는 과정을 반복합니다. 한 축을 정렬하면 다른 축의 정렬이 깨질 수 있으므로, 두 차원이 동시에 정렬될 때까지 이 과정을 반복합니다. C++로 최적화된 버전은 100만 개의 2D 포인트를 200밀리초 미만에 처리할 수 있으며, 알고리즘의 종료가 수학적으로 증명되어 안정성을 보장합니다.
이 알고리즘의 가장 큰 의미는 불규칙한 점 데이터를 빠르고 효율적으로 구조화할 수 있다는 점입니다. 특히, 최적 운송(Optimal Transport) 알고리즘이 제공하는 '정확한 최적성' 대신 '속도'를 선택하여, 실시간 처리나 대규모 데이터셋에 더 적합합니다. 결과적으로 생성된 격자 뷰(gridded view)는 x축과 y축을 따라 단조롭게 증가하는 특성을 가지며, 이는 공간적 근접성(spatial coherence)을 보존하여 인접한 점들이 격자에서도 인접하게 배치되도록 돕습니다. 이는 데이터 분석, 컴퓨터 그래픽스, 시뮬레이션 등 공간 데이터 처리가 중요한 여러 분야에서 데이터 접근 및 연산 효율을 크게 향상시킬 수 있습니다.