4차원 이상 기하 (Hyper Geometry)

정의

고차원 기하 (Hyper / 4D+ Geometry) 는 4차원 이상의 공간 R^d (d >= 4) 에서 점, 벡터, 초평면, 초구 등을 다루는 분야. PS 에서는 d ≤ 4 인 경우가 대부분이며, 주로 벡터-행렬 연산, 초평면과의 거리, 고차원 Convex Hull (d > 3 은 실질적 불가) 형태로 등장.

문제 상황과 동기

3차원까지는 직관이 통하지만 4차원부터 기하 직관이 완전히 무너짐.

• Naive: 점 N 개, 차원 d 에서 모든 쌍 거리 O(N^2) 는 d 와 무관. 하지만 d 가 커지면 곱셈 비용 증가.
• 차원의 저주 (Curse of Dimensionality): d 가 커질수록 공간이 지수적으로 넓어져, 최근접 이웃 / Convex Hull 의 복잡도가 폭발.
  • d=2 에서 Convex Hull O(N log N). d=3 에서 O(N log N) (QuickHull). d>=4 에서는 O(N^{d/2}) (비현실적).
• 응용: ML 의 고차원 feature 공간, 추천 시스템 (cosine similarity), 선형 계획법 (simplex method).

핵심 통찰: 차원이 높아져도 벡터의 내적(dot) 과 거리(Euclidean norm) 는 정의가 변하지 않는다. 외적은 d=3 전용이므로, d>=4 에서는 일반화된 wedge product 또는 행렬 연산으로 대체한다.

시각화

핵심 아이디어

d차원 벡터 연산

d차원 벡터 a = (a_1, a_2, ..., a_d), b = (b_1, ..., b_d):

초평면 (Hyperplane)

d차원 공간에서 초평면은 d-1차원의 아핀 부분공간.

n . x + b = 0   (n 은 법선 벡터, b 는 bias)

초구 (Hypersphere)

||x - c|| = r    (c 는 중심, r 은 반지름)

tesseract (4D 정육면체)

[0,1]^4 범위. 16개 꼭짓점, 32개 모서리, 24개 면(정사각형), 8개 정육면체 셀.

알고리즘

점과 초평면의 거리

hyperplane_distance(P, n, b):
    return |n . P + b| / ||n||

d차원 Convex Hull

d >= 4 인 경우 QuickHull 의 확장 (Chan’s algorithm) 은 존재하지만 대회에서는 d ≤ 3 까지만 현실적. d=4 에서 O(N^2) 까지도 문제에 따라 사용 가능.

구현

// 4D 벡터 연산: 내적, norm, 점-초평면 거리
#include <bits/stdc++.h>
using namespace std;
struct Vec4 { double w, x, y, z; };
double dot(Vec4 a, Vec4 b) {
  return a.w*b.w + a.x*b.x + a.y*b.y + a.z*b.z;
}
double norm(Vec4 a) { return sqrt(dot(a, a)); }
double dist(Vec4 p, Vec4 n, double b) {
  return fabs(dot(p, n) + b) / norm(n);
}
int main() {
  Vec4 p{1, 2, 3, 4};
  Vec4 n{0, 0, 0, 1};   // 초평면 w=0 의 법선
  double b = 0;
  cout << "distance to hyperplane w=0: ";
  cout << dist(p, n, b) << "\n";
  // 4D tesseract 꼭짓점 (0,0,0,0) ~ (1,1,1,1)
  Vec4 a{0,0,0,0}, c{1,1,1,1};
  cout << "tesseract diagonal: " << norm({c.w-a.w, c.x-a.x, c.y-a.y, c.z-a.z}) << "\n";
}

# 4D 벡터 연산 (함수형)
import math
​
def dot(a, b):
  return sum(x*y for x, y in zip(a, b))
​
def norm(a):
  return math.sqrt(dot(a, a))
​
def hyperplane_dist(p, n, b):
  return abs(dot(p, n) + b) / norm(n)
​
p = (1, 2, 3, 4)
n = (0, 0, 0, 1)    # 초평면 w=0 법선
b = 0
print("distance to hyperplane w=0:", hyperplane_dist(p, n, b))
​
# tesseract 대각선
a, c = (0,0,0,0), (1,1,1,1)
print("tesseract diagonal:", norm(tuple(c[i]-a[i] for i in range(4))))

// 4D 벡터: Java record (Java 16+)
import java.util.*;
​
public class Main {
  record Vec4(double w, double x, double y, double z) {
      double dot(Vec4 o) { return w*o.w + x*o.x + y*o.y + z*o.z; }
      double norm() { return Math.sqrt(dot(this)); }
  }
  static double dist(Vec4 p, Vec4 n, double b) {
      return Math.abs(p.dot(n) + b) / n.norm();
  }
  public static void main(String[] args) {
      Vec4 p = new Vec4(1, 2, 3, 4);
      Vec4 n = new Vec4(0, 0, 0, 1);
      System.out.printf("거리: %.2f%n", dist(p, n, 0));
      Vec4 a = new Vec4(0,0,0,0), c = new Vec4(1,1,1,1);
      Vec4 d = new Vec4(c.w-a.w, c.x-a.x, c.y-a.y, c.z-a.z);
      System.out.printf("대각선: %.2f%n", d.norm());
  }
}

distance to hyperplane w=0: 4
tesseract diagonal: 2

복잡도

변형 / 활용

1. 고차원에서의 거리

d 가 클수록 모든 점 쌍 간 거리가 비슷해지는 현상 (차원의 저주). 최근접 / 최원접 구분이 어려워짐.

2. Cosine Similarity

cos(a, b) = (a . b) / (||a|| * ||b||)

추천 시스템, 정보 검색에서 고차원 벡터의 방향 유사도 측정.

3. 선형 변환과 행렬

고차원 기하는 행렬 곱으로 표현. 회전, 반사, 스케일링 모두 d x d 행렬.

4. 4D -> 3D 투영 (Perspective)

P_3d = (P.x / P.w, P.y / P.w, P.z / P.w)

tesseract 의 3D 그림자, 게임 엔진의 4D 렌더링.

함정

1. 외적 부재

d >= 4 에서 cross product 는 정의되지 않음. d choose 2 개의 wedge component 로 bivector 표현.

2. Curse of Dimensionality

d=20 만 되어도 단위 구의 부피는 거의 0 에 가까움. 무작위 두 점 사이 거리가 모두 거의 일정.

3. 정수 연산 확장

CCW 의 d차원 일반화는 행렬식 계산 필요 (O(d!)). d 가 크면 float 으로만 가능.

4. BOJ 에서의 희소성

순수 4D+ 기하 문제는 BOJ 에 거의 없음. d ≤ 3 까지만 출제.

BOJ 연습 문제

참고

• 2D 기하 기본
• 3D 기하
• 볼록 껍질