제1부 수학적 기초

1.24 계산 기하와 공간 자료구조: 볼록 껍질·보로노이·메시·k-d 트리·옥트리

1.24.1 이 장에서 배우는 것 / 선수 지식 / 특히 중요한 독자

이 장은 점 집합과 형상을 다루는 로봇 소프트웨어(충돌 검사, 지도, 점군 정합, 경로 계획)가 공통으로 사용하는 계산 기하의 알고리즘과 공간 자료구조를 정리한다. 점 집합의 볼록 껍질과 들로네 삼각분할(보로노이 도형의 쌍대)은 근접성의 구조를 주고, 메시는 표면의 표현이며, k-d 트리와 옥트리는 근접 질의와 점유 표현을 빠르게 한다. 이 모든 알고리즘은 기하 술어(점의 방향·원 안 판정)에 의존하며 부동소수점 오류가 구조를 깨뜨릴 수 있다. 다룰 질문은 다섯 가지다. 방향 판정은 부동소수점에서 어떻게 틀리는가, 볼록 껍질과 들로네 삼각분할은 어떻게 계산하고 검증하는가, k-d 트리의 최근접 탐색은 차원에 따라 얼마나 빨라지는가, 옥트리의 노드 수는 해상도에 따라 어떻게 늘어나는가, 삼각 메시의 위상과 부피는 어떻게 점검하는가.

배우는 것:

• 기하 술어와 견고성 — 방향 판정, 정확 연산과의 비교.
• 볼록 껍질 — 앤드루 단조 사슬 $O(n\log n)$.
• 들로네·보로노이 — 빈 외접원 조건, 증분 삽입, 오일러 공식.
• k-d 트리 — 중앙값 분할, 가지치기, 차원의 저주.
• 옥트리 — 점유 표현, 노드 수의 증가.
• 메시 — 오일러 수, 다양체 점검, 부피·면적.
• 라이브러리 — SciPy(Qhull·cKDTree)와의 비교.

선수 지식: 1.6(동차변환·점), 1.23(그래프). 표기는 BK-05와 A.2을 따른다. 충돌 검사(GJK·BVH)는 11.2, 점유 격자·OctoMap은 9.28, 거리장·메시 지도는 9.29, 볼록 분해는 4.15, 형상 공간의 보로노이 계획은 11.1이 다룬다.

특히 중요한 독자: 점군·메시·지도를 처리하는 소프트웨어 개발자, 충돌 검사·근접 질의를 구현하는 연구자, 기하 라이브러리의 견고성을 평가하는 엔지니어.

출처 방침. 서지는 Crossref 응답으로 확인했다(목록은 이 장 끝). 직접 실행한 것: SciPy 1.18.1(NumPy 2.5.4)의 spatial.ConvexHull·Delaunay·Voronoi·cKDTree. 읽지 못한 것: 인용한 논문·교과서의 본문(정리 번호는 (확인 필요)), SciPy·Qhull의 소스. 이 장의 수치는 순수 파이썬 구현(정확 연산은 표준 라이브러리 fractions)으로 계산했다.

1.24.2 개념 — 점 사이의 관계를 구조로

로봇이 다루는 데이터는 점(LiDAR 점군, 관절 위치), 면(메시, 지도), 영역(점유 공간)이다. 이들에서 반복되는 질문은 "이 점에서 가장 가까운 점은 어디인가", "점들을 감싸는 최소의 볼록 영역은 무엇인가", "공간을 어떻게 나누어 점유를 기록하는가"이다. 알고리즘은 점의 상대 위치를 판정하는 기하 술어(세 점이 반시계인가, 점이 원 안에 있는가)의 부호에 의존한다. 부호가 틀리면 껍질이 오목해지거나 삼각분할이 겹치는 식으로 구조가 깨진다.

아래 도해는 무작위 점 24개의 볼록 껍질과 들로네 삼각분할이다.

1.24.3 원리

1.24.3.1 기하 술어와 견고성

결론: 방향 판정은 세 점이 거의 한 직선 위에 있을 때 부동소수점에서 부호가 틀리고, 틀린 부호로는 알고리즘의 불변식이 깨지므로 정확 연산이나 적응형 정밀도 연산이 필요하다.

세 점 $a,b,c$의 방향 판정은 $\mathrm{orient}(a,b,c)=(b-a)\times(c-a)$의 부호(양수이면 반시계)이다. 이 값은 뺄셈과 곱셈의 합으로 계산되므로 두 항이 거의 같으면 유효 숫자가 사라진다. 정확한 부호는 부동소수점 수를 정확한 유리수로 변환해 구할 수 있다(이 장은 파이썬의 Fraction을 사용했으며 느리다). 빠르게 정확한 부호를 내는 방법으로 Shewchuk(1997)의 적응형 정밀도 연산이 있으며, 부동소수점 기하 계산의 견고성 문제의 예는 Kettner 외(2008)가 다룬다(서지 확인, 본문 미확인). 이 장의 시험은 같은 종류의 거의 공선 점을 직접 구성했으며 논문의 구성과 같은지는 확인하지 않았다.

1.24.3.2 볼록 껍질

점 집합의 볼록 껍질은 점을 모두 포함하는 최소의 볼록 다각형이다. 앤드루의 단조 사슬 알고리즘(Andrew 1979)은 점을 $x$ 좌표로 정렬한 뒤 아래쪽 사슬과 위쪽 사슬을 따로 만든다. 사슬에 점을 추가할 때 마지막 두 점과의 방향이 우회전(또는 공선)이면 마지막 점을 제거한다. 정렬이 $O(n\log n)$이고 사슬 구성이 $O(n)$이다. 방향 판정의 부호가 틀리면 사슬이 오목해질 수 있다(1.24.5).

1.24.3.3 들로네 삼각분할과 보로노이 도형

결론: 들로네 삼각분할은 모든 삼각형의 외접원이 다른 점을 포함하지 않는 삼각분할이며 보로노이 도형과 쌍대이다. 평면에서 점 $n$개, 껍질 꼭짓점 $h$개이면 삼각형 수는 $2n-2-h$이다.

보로노이 도형은 각 점에 가장 가까운 영역의 분할이고, 들로네 삼각분할의 삼각형 외심이 보로노이 꼭짓점이다. 증분 삽입(Bowyer 1981; Watson 1981)은 새 점을 외접원이 포함하는 삼각형들을 지우고 그 구멍의 경계와 새 점을 이어 삼각형을 만든다. 이 장의 구현은 $O(n^2)$이다. $O(n\log n)$ 알고리즘으로 Fortune(1987)의 스위프라인이 있다. "원 안" 판정은 $4\times4$ 형태의 행렬식(1.24.5의 in_circle)이며 방향 판정처럼 견고성이 필요하다. 로봇공학에서는 보로노이 도형이 일반화 보로노이 그래프 기반 경로 계획(11.1)과 가장 가까운 시설 배정에 나타난다.

1.24.3.4 k-d 트리

결론: k-d 트리는 공간을 축에 수직인 평면으로 재귀 분할하며, 최근접 탐색은 분할 평면까지의 거리가 현재 최소 거리보다 크면 반대쪽을 방문하지 않아 저차원에서 거의 상수의 거리 계산으로 끝난다. 차원이 커지면 가지치기가 사라진다.

중앙값으로 분할한 이진 트리를 만들고(Bentley 1975), 질의점이 속한 쪽을 먼저 탐색한 뒤 $(q_a-s)^2<d_{\text{best}}$일 때만 반대쪽을 탐색한다. 저차원에서 로그 시간 기대 탐색이 알려져 있다(Friedman 외 1977; 정리 번호 (확인 필요)). 고차원에서는 분할 평면까지의 거리가 최근접 거리보다 작은 경우가 대부분이어서 거의 모든 잎을 방문한다. 이 장의 측정은 $d=16$에서 점의 98.5%를 방문함을 보인다. 점군 정합(ICP·NDT, 9.17·10.20)의 대응점 탐색이 대표적 사용처이다.

1.24.3.5 옥트리와 점유 표현

결론: 옥트리는 정육면체를 8개로 재귀 분할하며, 점유한 셀만 노드로 두면 노드 수가 표면적에 비례해($4^d$) 밀집 격자($8^d$)보다 훨씬 느리게 늘어난다.

깊이 $d$의 셀 한 변은 루트의 $2^{-d}$이다. 표면 위의 점은 표면적을 셀 면적으로 나눈 만큼의 셀을 점유하므로 점유 셀 수가 해상도를 2배로 할 때 약 4배가 된다. 이 구조를 확률적 점유 지도에 적용한 것이 OctoMap이다(Hornung 외 2013; 9.28). 이 장은 점유 셀의 수만 계산했고 확률 갱신은 다루지 않았다.

1.24.3.6 삼각 메시

삼각 메시는 꼭짓점 좌표와 면(꼭짓점 인덱스 세 개)의 목록이다. 닫힌 다양체 메시는 모든 모서리가 정확히 두 면에 속하며, 오일러 수 $V-E+F=2-2g$($g$는 종수)를 만족한다(구는 $g=0$이므로 2). 닫힌 메시의 부피는 발산 정리에서 유도한 부호 있는 사면체의 합 $\tfrac16\sum_f a\cdot(b\times c)$이고 면적은 삼각형 면적의 합이다(면의 방향이 바깥쪽으로 일관되어야 한다). 충돌용 형상의 볼록 분해(4.15)와 거리장(9.29)은 이 표현에서 만든다.

1.24.3.7 라이브러리

SciPy의 ConvexHull·Delaunay·Voronoi는 Qhull 라이브러리를 사용하는 것으로 알려져 있다 (확인 필요: 문서). Qhull의 알고리즘(quickhull)은 Barber 외(1996)가 다룬다(서지 확인). cKDTree는 C로 구현된 k-d 트리이다. 이 장의 구현과 같은 입력에서의 결과를 비교했다(1.24.5).

1.24.4 알고리즘

볼록 껍질, 들로네(증분 삽입), k-d 트리 최근접 탐색, 점유 셀

convex_hull(P):  P를 (x, y)로 정렬 ;  아래 사슬: 각 점 p에 대해
                   orient(끝에서 둘째, 끝, p) ≤ 0이면 끝 점 제거 ;  p 추가
                 위 사슬도 역순으로 같게 ;  두 사슬을 이어 반시계 꼭짓점
delaunay(P):     큰 초기 삼각형 ;  점 p마다:
                   bad ← p를 외접원 안에 두는 삼각형들
                   구멍의 경계 ← bad의 모서리 중 한 번만 나타나는 것
                   bad를 지우고 (경계 모서리, p)로 삼각형 추가
kd_nearest(T, q): 잎이면 점들의 거리 계산 ;  아니면 q가 속한 쪽 먼저 방문,
                   (q[축] − 분할값)² < 현재 최소 거리²이면 반대쪽도 방문
occupied_cells(P, d): 깊이 d의 셀 인덱스 = floor(좌표 · 2^d)의 집합 크기

구현은 1.24.5의 두 코드 블록에 있다.

1.24.5 풀이 예제 — 견고성·껍질·삼각분할·k-d 트리·옥트리·메시와 SciPy 비교

방향 판정의 부동소수점 오류를 정확 연산과 비교하고, 볼록 껍질과 들로네 삼각분할을 구현·검증하며, k-d 트리의 가지치기를 차원별로 측정하고, 옥트리의 점유 셀 수와 아이코구 메시의 위상·부피를 계산한 뒤 SciPy와 대조한다. 결론부터 적으면 다음과 같다. ① 거의 공선인 점 65,536개 가운데 11,972개(18.3%)에서 부동소수점 방향 판정의 부호가 정확한 부호와 다르고 11,556개는 0으로 판정되는 반면, 무작위 점 20,000개에서는 틀린 경우가 없다. ② 볼록 껍질은 점 100~100,000개에서 꼭짓점 9~31개이며 모든 점이 껍질 안임을 정확 판정으로 확인했다. ③ 점 60개의 들로네 삼각형은 109개로 $2n-2-h=109$와 같고 빈 외접원 조건 위반이 0이다. ④ k-d 트리 최근접 탐색의 거리 계산은 점 10,000개에서 전수 탐색의 0.1%($d=2$), 0.3%($d=3$), 8.3%($d=8$), 98.5%($d=16$)이다. ⑤ 구 표면 점의 점유 셀은 깊이가 1 늘 때 약 3.6~4.3배 늘고 밀집 격자는 8배이며 깊이 7에서 점유 비율이 2.0%이다. ⑥ 아이코구 메시는 모든 분할에서 $V-E+F=2$이고 모서리당 면 수의 최대가 2이며 4회 분할에서 부피가 구의 99.78%이다. ⑦ SciPy와 껍질·삼각형 집합이 200개 사례에서 모두 같고 $k$-d 트리 결과가 4개 차원 모두에서 같다.

구현. orient·convex_hull·in_circle·delaunay(첫 블록), kd_build·kd_nearest·occupied_cells·mesh_stats(둘째 블록). 정확 판정 orient_exact(Fraction), 메시 생성 icosphere

import math

def orient(a, b, c):
    """(b-a) x (c-a): 양수이면 a, b, c가 반시계 방향"""
    return ((b[0] - a[0]) * (c[1] - a[1])
            - (b[1] - a[1]) * (c[0] - a[0]))

def convex_hull(P):
    """앤드루 단조 사슬 O(n log n), 반시계 꼭짓점"""
    pts = sorted(set(P))
    if len(pts) < 3:
        return pts
    def half(seq):
        h = []
        for p in seq:
            while len(h) > 1 and orient(h[-2], h[-1], p) <= 0:
                h.pop()
            h.append(p)
        return h
    lo, up = half(pts), half(pts[::-1])
    return lo[:-1] + up[:-1]

def in_circle(a, b, c, d):
    """d가 반시계 삼각형 abc의 외접원 안이면 양수"""
    rows = [(p[0] - d[0], p[1] - d[1],
             (p[0] - d[0]) ** 2 + (p[1] - d[1]) ** 2)
            for p in (a, b, c)]
    (a0, a1, a2), (b0, b1, b2), (c0, c1, c2) = rows
    return (a0 * (b1 * c2 - b2 * c1)
            - a1 * (b0 * c2 - b2 * c0)
            + a2 * (b0 * c1 - b1 * c0))

def delaunay(P):
    """증분 삽입 들로네 O(n^2): 삼각형 (i, j, k)"""
    n = len(P)
    M = 1e5 * max(1.0, max(max(abs(x), abs(y)) for x, y in P))
    V = list(P) + [(-M, -M), (M, -M), (0.0, M)]
    T = [(n, n + 1, n + 2)]
    for i, p in enumerate(P):
        bad = [t for t in T if in_circle(V[t[0]], V[t[1]],
                                         V[t[2]], p) > 0]
        cnt = {}
        for a, b, c in bad:
            for e in ((a, b), (b, c), (c, a)):
                k = tuple(sorted(e))
                cnt[k] = cnt.get(k, 0) + 1
        T = [t for t in T if t not in bad]
        for (a, b), c in cnt.items():
            if c == 1:
                ccw = orient(V[a], V[b], p) > 0
                T.append((a, b, i) if ccw else (b, a, i))
    return [t for t in T if max(t) < n]

import math

def kd_build(P, idx=None, d=0, leaf=8):
    """중앙값 분할 k-d 트리: (축, 값, 왼쪽, 오른쪽) 또는 잎"""
    idx = list(range(len(P))) if idx is None else idx
    if len(idx) <= leaf:
        return ('leaf', idx)
    ax, m = d % len(P[0]), len(idx) // 2
    idx.sort(key=lambda i: P[i][ax])
    L = kd_build(P, idx[:m], d + 1, leaf)
    R = kd_build(P, idx[m:], d + 1, leaf)
    return (ax, P[idx[m]][ax], L, R)

def kd_nearest(P, T, q, best, cnt):
    """최근접 이웃: 분할 평면까지의 거리로 가지치기"""
    if T[0] == 'leaf':
        for i in T[1]:
            cnt[0] += 1
            d = sum((a - b) ** 2 for a, b in zip(P[i], q))
            if d < best[0]:
                best[0], best[1] = d, i
        return
    ax, s, L, R = T
    near, far = (L, R) if q[ax] < s else (R, L)
    kd_nearest(P, near, q, best, cnt)
    if (q[ax] - s) ** 2 < best[0]:
        kd_nearest(P, far, q, best, cnt)

def occupied_cells(P, depth):
    """깊이 0..depth의 점유 셀 수(팔진 트리의 층별 노드)"""
    return [len({(int(x * 2 ** d), int(y * 2 ** d),
                  int(z * 2 ** d)) for x, y, z in P})
            for d in range(depth + 1)]

def cross3(u, v):
    return (u[1] * v[2] - u[2] * v[1],
            u[2] * v[0] - u[0] * v[2],
            u[0] * v[1] - u[1] * v[0])

def mesh_stats(V, F):
    """V, E, F, 모서리당 면 수의 최대, 부피, 면적"""
    E = {}
    vol = area = 0.0
    for a, b, c in F:
        for e in ((a, b), (b, c), (c, a)):
            k = (min(e), max(e))
            E[k] = E.get(k, 0) + 1
        A, B, C = V[a], V[b], V[c]
        vol += sum(x * y for x, y in zip(A, cross3(B, C))) / 6
        u = [p - q for p, q in zip(B, A)]
        v = [p - q for p, q in zip(C, A)]
        w = cross3(u, v)
        area += 0.5 * math.sqrt(sum(x * x for x in w))
    return len(V), len(E), len(F), max(E.values()), vol, area

① 방향 판정의 견고성.

거의 공선인 입력에서 부동소수점 판정은 정확한 부호와 18.3%에서 다르다. 무작위 점에서는 두 값이 같으므로 이 오류는 퇴화에 가까운 입력에서 나타난다.

② 볼록 껍질.

껍질 꼭짓점 수는 점 수가 1,000배($10^2\to10^5$)가 되어도 9에서 31로만 늘었다(균일 분포의 관찰). 순수 파이썬에서 $10^5$점의 계산 시간은 이 환경에서 0.4초 안팎이었다.

③ 들로네 삼각분할.

④ k-d 트리의 가지치기.

차원이 2~3일 때 전수 탐색의 0.1~0.3%만 계산하지만 $d=8$에서 8.3%, $d=16$에서 98.5%로 가지치기가 사라진다. 점 10,000개에 대한 값이며 점 수가 늘면 저차원의 비율은 더 줄 것으로 보이나 측정하지 않았다 (추정).

⑤ 옥트리의 점유 셀.

점유 셀의 증가 배율이 깊이 3~6에서 4.0, 4.3, 3.8, 3.6으로 4에 가깝고(표면의 점유), 깊이 7에서 3.1로 낮아지는 것은 점 100,000개가 셀 41,760개를 채우는 표본 한계 때문이다 (추정). 깊이 7의 밀집 격자는 2,097,152셀이나 점유 셀은 그 2.0%이다.

⑥ 메시의 위상과 부피.

면이 바깥쪽으로 일관된 닫힌 구 메시에서 $V-E+F=2$이고 모서리마다 면이 정확히 2개이다. 부피와 면적이 구에 수렴하는 비율은 분할 때마다 오차가 약 1/4로 줄어(부피: $1-0.9661=0.034$, $1-0.9914=0.0086$, $1-0.9978=0.0022$) 이차 수렴이다.

⑦ SciPy 호출 결과(실행 2026-11-03). 스크립트는 robotics/fig-src/1.24-libcheck.py, 출력은 robotics/fig-src/data/1.24-libcheck-output.txt에 있다.

(비율은 표 ④와 다른 난수 점집합이므로 값이 조금 다르다.) cKDTree는 같은 점을 내고 질의가 3~170배 빠르다(C 구현의 효과이며 알고리즘의 차이는 확인하지 않았다).

한계. 수치는 합성 입력(시드 고정)이다. 껍질·들로네는 평면만, 정확 판정은 Fraction(느림)이다. 증분 삽입은 $O(n^2)$이며 큰 점 집합과 퇴화(동원·공선 다수) 입력은 시험하지 않았다. 슈퍼 삼각형을 유한한 크기로 두어 껍질 근처에서 Qhull과 다른 삼각형이 나올 수 있으나 이 입력(200개)에서는 모두 같았다. k-d 트리는 균일 분포에서만 측정했고 군집한 점군은 다루지 않았다. 옥트리는 노드 수만 세었고 질의·확률 갱신·메모리는 측정하지 않았다. 메시는 구에 한정했다.

견해: 이 책은 기하 알고리즘을 직접 구현할 때 방향·원 안 판정을 견고한 술어(정확 또는 적응형)로 두고, 근접 질의는 차원이 낮으면(대략 3 이하) k-d 트리 같은 공간 분할을, 차원이 높으면 전수 탐색이나 근사 최근접 탐색을 검토하는 것을 기본으로 둔다고 본다. 근거는 위 예제에서 부동소수점 방향 판정이 거의 공선 입력의 18.3%에서 틀렸고, k-d 트리의 가지치기 이득이 $d=2$에서 99.9%, $d=16$에서 1.5%였다는 점이다. 이 근거는 균일 분포의 합성 입력이다.

1.24.6 설계 트레이드오프 — 공간 표현의 선택

공개 문헌에서 확인되는 선택지는 네 가지다.

• ① 균일 격자(복셀). 질의가 상수 시간이고 구현이 단순하다. 메모리가 $8^d$로 늘어난다.
• ② 옥트리(점유 셀만). 메모리가 표면적에 비례한다. 포인터 추적이 필요하다.
• ③ k-d 트리. 점 집합의 최근접·범위 질의에 알맞다. 고차원에서 효과가 없다.
• ④ 메시·BVH. 표면을 정확히 표현한다. 충돌·거리 질의에 별도 구조가 필요하다(11.2).

견해: 자료구조의 선택은 질의의 종류(최근접·범위·점유)와 갱신 빈도로 정하고 정확도의 문제는 술어의 견고성으로 분리해 다루는 것이 맞다고 본다. 근거는 이 장의 결과가 구조의 효율(가지치기·노드 수)과 판정의 정확도(방향 판정 오류)를 독립적으로 보였다는 점이다.

1.24.7 응용 축 비교

이 표는 이 책의 정리이며 장별 요구는 다르다.

1.24.8 관련 규격·프로토콜

기하 알고리즘의 표기에 국제 표준은 없다. 결과의 비교는 입력·판정 방식(부동소수점·정확)을 적은 실행 기록이 기준이다.

1.24.9 관련 규제·인증 요구와의 연결

직접 적용되는 규제는 없다. 충돌 검사·점유 지도의 기하 오류(방향 판정의 부호 오류로 구조가 깨지는 경우)는 안전 기능의 입력 오류로 이어질 수 있으며 안전 관련 소프트웨어의 검증 항목이 될 수 있다. 소프트웨어 안전과 품질 표준은 26.20이 다룬다.

1.24.10 한계·유의점·미해결

• 정리의 출처. 앤드루 알고리즘의 정당성, 들로네 삼각분할의 성질(최소 각 최대화 등), k-d 트리의 기대 시간, 교과서(de Berg 외)의 장 번호는 확인하지 않았다 (확인 필요).
• 견고성. 방향 판정의 오류는 한 종류의 입력(거의 공선)에서 측정했고 Kettner 외(2008)의 구성과의 일치는 확인하지 않았다.
• 규모·분포. 큰 점 집합, 군집·퇴화 입력, 3차원 껍질·들로네는 다루지 않았다.
• 옥트리. 확률 점유 갱신, 질의 시간, 실제 메모리는 측정하지 않았다.
• 라이브러리. SciPy·Qhull의 소스는 읽지 않았고 실행 결과로만 비교했다.

1.24.11 체크포인트·연구 질문

체크포인트:

1. 방향 판정의 정의와 부동소수점에서 부호가 틀리는 조건을 설명할 수 있는가.
2. 앤드루 단조 사슬의 절차와 시간 복잡도를 설명할 수 있는가.
3. 들로네 삼각분할의 빈 외접원 조건과 보로노이 도형과의 쌍대 관계, 삼각형 수 $2n-2-h$를 설명할 수 있는가.
4. k-d 트리 최근접 탐색의 가지치기 조건을 적고 차원이 커지면 효과가 사라지는 이유를 설명할 수 있는가.
5. 옥트리의 점유 셀 수가 $4^d$로, 밀집 격자가 $8^d$로 늘어나는 이유를 설명할 수 있는가.
6. 닫힌 메시의 오일러 수와 다양체 조건, 부피 공식을 쓸 수 있는가.
7. 기하 라이브러리의 결과를 정확 판정이나 다른 라이브러리와 대조해 검증하는 방법을 말할 수 있는가.

연구 질문(47.12에 수록한다):

• 로봇 점군(군집·비균일 분포)에서 k-d 트리와 옥트리의 최근접 질의 비용은 균일 분포의 결과와 얼마나 다른가.
• 부동소수점 기하 술어의 오류가 충돌 검사·점유 지도의 오판정으로 이어지는 빈도는 실제 로봇 데이터에서 얼마인가.
• 근사 최근접 탐색(해시·그래프 기반)과 k-d 트리의 정확도·지연 균형은 점군 정합에서 어떻게 정해지는가.

1차 출처

• J. R. Shewchuk, 「Adaptive Precision Floating-Point Arithmetic and Fast Robust Geometric Predicates」, Discrete & Computational Geometry 18(3), 305–363, 1997(doi:10.1007/pl00009321) — 서지만 확인.
• L. Kettner, K. Mehlhorn, S. Pion, S. Schirra, C. Yap, 「Classroom examples of robustness problems in geometric computations」, Computational Geometry 40(1), 61–78, 2008(doi:10.1016/j.comgeo.2007.06.003) — 서지만 확인(Crossref가 처음 세 저자까지 확인).
• A. M. Andrew, 「Another efficient algorithm for convex hulls in two dimensions」, Information Processing Letters 9(5), 216–219, 1979(doi:10.1016/0020-0190(79)90072-3) — 서지만 확인.
• A. Bowyer, 「Computing Dirichlet tessellations」, The Computer Journal 24(2), 162–166, 1981(doi:10.1093/comjnl/24.2.162); D. F. Watson, 「Computing the n-dimensional Delaunay tessellation with application to Voronoi polytopes」, The Computer Journal 24(2), 167–172, 1981(doi:10.1093/comjnl/24.2.167) — 서지만 확인.
• S. Fortune, 「A sweepline algorithm for Voronoi diagrams」, Algorithmica 2, 153–174, 1987(doi:10.1007/bf01840357) — 서지만 확인.
• C. B. Barber, D. P. Dobkin, H. Huhdanpaa, 「The quickhull algorithm for convex hulls」, ACM Transactions on Mathematical Software 22(4), 469–483, 1996(doi:10.1145/235815.235821) — 서지만 확인.
• J. L. Bentley, 「Multidimensional binary search trees used for associative searching」, Communications of the ACM 18(9), 509–517, 1975(doi:10.1145/361002.361007); J. H. Friedman, J. L. Bentley, R. A. Finkel, 「An Algorithm for Finding Best Matches in Logarithmic Expected Time」, ACM Transactions on Mathematical Software 3(3), 209–226, 1977(doi:10.1145/355744.355745) — 서지만 확인.
• A. Hornung 외, 「OctoMap: an efficient probabilistic 3D mapping framework based on octrees」, Autonomous Robots 34(3), 189–206, 2013(doi:10.1007/s10514-012-9321-0) — 서지만 확인.
• M. de Berg, O. Cheong, M. van Kreveld, M. Overmars, 『Computational Geometry: Algorithms and Applications』, 3판, Springer, 2008(doi:10.1007/978-3-540-77974-2) (확인 필요: 장 번호).
• SciPy 1.18.1(spatial.ConvexHull·Delaunay·Voronoi·cKDTree 실행, 2026-11-03).

다음 장. 1.25은 신호와 시스템 기초로, 샘플링·라플라스 변환·$z$ 변환·주파수 응답·디지털 필터를 다룬다. 센서 신호의 표본화·변환·필터를 정리하며 제1부 수학적 기초를 마무리한다.