힐베르트 곡선(Hilbert curve)은 독일의 수학자 다비트 힐베르트(David Hilbert)가 1891년 논문에서 처음 제시한 연속 프랙탈 곡선으로, 공간 채움 곡선(space-filling curve)의 한 종류이다. 이탈리아 수학자 주세페 페아노(Giuseppe Peano)가 1890년 발견한 페아노 곡선의 변형으로 개발되었다.
정의
힐베르트 곡선은 단위 구간 [0,1]을 단위 정사각형 [0,1]×[0,1] 위로 연속적으로 사상하는 함수이다. 이 곡선은 일련의 조각적 선형 곡선(piecewise linear curve)들의 균등 극한(uniform limit)으로 구성된다. n차 힐베르트 다각형은 다음과 같은 과정으로 생성된다.
1차 단계에서는 구간 [0,1]을 4등분하고 정사각형을 4개의 부분 정사각형으로 나누어 각 구간과 정사각형을 대응시킨 뒤, 이웃하는 정사각형의 중심을 연결한다. 2차 단계에서는 각 구간과 정사각형을 다시 4등분하여 16개의 구간과 16개의 정사각형을 대응시키고 중심을 연결한다. 이 과정을 반복하여 n이 증가함에 따라 곡선은 점차 정사각형 전체를 채우게 된다.
성질
힐베르트 곡선은 다음과 같은 수학적 성질을 가진다.
- 균등 연속 함수(uniformly continuous function)이다.
- 전사 함수(surjective function)로서, 곡선의 상(image)이 단위 정사각형 전체와 일치한다.
- 단사 함수(injective function)가 아니며, 이는 네토 정리(Netto's theorem)의 특수한 경우에 해당한다.
- 모든 점에서 미분 불가능하며, 립시츠 연속 함수(Lipschitz continuous function)가 아니다.
- 공간을 채우므로 하우스도르프 차원(Hausdorff dimension)이 2이다.
- n차 곡선의 길이는 2^n - 1/2^n으로, n에 따라 길이가 지수적으로 증가한다.
응용 분야
힐베르트 곡선은 1차원 공간과 2차원 공간 사이의 매핑을 제공하면서 국소성(locality)을 비교적 잘 보존하는 성질 때문에 컴퓨터 과학에서 널리 사용된다. 주요 응용 분야는 다음과 같다.
- 데이터베이스 인덱싱: 힐베르트 R-트리(Hilbert R-tree)와 같은 다차원 데이터베이스 인덱스의 압축 및 가속에 사용된다. Z-순서(Z-order)보다 국소성 보존 성능이 우수한 것으로 알려져 있다.
- 이미지 처리: 리머스마 디더링(Riemersma dithering) 알고리즘에서 그레이스케일 사진을 흑백 이미지로 변환할 때 사용된다.
- IP 주소 매핑: 인터넷 전체의 IP 주소 범위를 2차원 그림으로 시각화하는 데 활용된다.
- 3D 프린팅: 3D 모델을 적층 가공하기 위한 경로 생성 시 내부 채움(infill) 패턴의 하나로 사용된다.
- 모바일 로봇: 공간 탐색 경로 계획 알고리즘에 활용된다.
L-시스템 표현
힐베르트 곡선은 L-시스템(L-system, 재작성 시스템)으로 다음과 같이 표현할 수 있다.
- 알파벳: A, B
- 상수: F, +, -
- 공리(Axiom): A
- 생성 규칙:
- A → +BF-AFA-FB+
- B → -AF+BFB+FA-
여기서 'F'는 앞으로 이동, '+'는 왼쪽으로 90도 회전, '-'는 오른쪽으로 90도 회전을 의미하며, 'A'와 'B'는 그리는 동안 무시된다.
역사적 의의
힐베르트 곡선은 최초의 공간 채움 곡선은 아니지만(최초는 페아노 곡선), 힐베르트가 논문에 실은 그림은 공간 채움 곡선의 생성 과정을 시각적으로 설명한 최초의 그림으로 평가된다. 이 곡선은 프랙탈 기하학과 위상수학의 발전에 기여하였으며, 현대 컴퓨터 과학의 다양한 알고리즘 설계에 실용적으로 응용되고 있다.
