Geometry

Geometry (기하학)

9.1 Linear Algebra Basics

• Vectors / 벡터: Elements of $\mathbb{R}^n$. / $\mathbb{R}^n$의 원소.
• Dot Product / 내적: $\langle x, y \rangle = \sum_{i=1}^{n} x_i y_i$.
  • $x, y$ perpendicular iff $\langle x, y \rangle = 0$. / $x, y$가 수직이면 $\langle x, y \rangle = 0$.

  • $\langle x, y \rangle =

    x

    _2 \cdot

    y

    _2 \cdot \cos \theta$. / $\langle x, y \rangle =

    x

    _2 \cdot

    y

    _2 \cdot \cos \theta$.

• Cross Product (2D) / 외적 (2D): For vectors in $\mathbb{R}^2$, perpendicular vector: $(-y, x)$ for $(x, y)$. / $\mathbb{R}^2$의 벡터에 대해, 수직 벡터: $(x, y)$에 대해 $(-y, x)$.
• Cross Product (3D) / 외적 (3D): \(x \times y = \begin{pmatrix} x_2 y_3 - x_3 y_2 \\ x_3 y_1 - x_1 y_3 \\ x_1 y_2 - x_2 y_1 \end{pmatrix}\)
• Determinant (2×2) / 행렬식 (2×2): \(\det \begin{pmatrix} a & b \\ c & d \end{pmatrix} = ad - bc\)
  • Interpretation: Signed area of parallelogram. / 기호 있는 평행사변형 넓이.
  • $A$ invertible iff $\det(A) \neq 0$. / $A$가 가역이면 $\det(A) \neq 0$.

9.2 Basic Operations

• CCW (Counter-Clockwise) / CCW (반시계 방향): Determines if point $p$ is left, right, or on line $(a,b)$. / 점 $p$가 선 $(a,b)$의 왼쪽, 오른쪽, 또는 위에 있는지 결정. \(CCW(a,b,p) = (p_y - a_y)(b_x - a_x) - (p_x - a_x)(b_y - a_y)\)
  • Alternative using determinant: / 행렬식 사용: \(CCW(a,b,p) = \det \begin{pmatrix} a_x & b_x & p_x \\ a_y & b_y & p_y \\ 1 & 1 & 1 \end{pmatrix}\)
• Interpretation / 해석:
  • $CCW > 0$: $p$ is to the left. / $p$는 왼쪽.
  • $CCW < 0$: $p$ is to the right. / $p$는 오른쪽.
  • $CCW = 0$: $p$ is on the line. / $p$는 선 위.

• Area of triangle / 삼각형 넓이: $\frac{1}{2}

  CCW(a,b,p)

  $. / $\frac{1}{2}

  CCW(a,b,p)

  $.

• Point on Line Segment / 선분 위의 점: $p$ is on $[a,b]$ iff $p$ is on line $(a,b)$ AND coordinates are between $a$ and $b$. / $p$가 $[a,b]$ 위에 있으면 $p$가 선 $(a,b)$ 위에 있고 좌표가 $a$와 $b$ 사이.
• Line Intersection / 직선 교점: Solve system of equations. Unique solution iff lines not parallel. / 연립방정식 해결. 평행하지 않으면 유일한 해.

---

9.3 Convex Hull

• Definition / 정의: Smallest convex set containing all points. / 모든 점을 포함하는 가장 작은 볼록 집합.
• Graham’s Scan / Graham Scan:
  1. Find bottom-leftmost point (pivot). / 가장 아래-왼쪽 점 찾기 (피벗).
  2. Sort other points by angle with pivot. / 피벗과의 각도로 다른 점 정렬.
  3. Iterate and remove points that create right turns (concave). / 반복하며 오른쪽 회전(오목)을 만드는 점 제거.
• Time Complexity / 시간 복잡도: $\mathcal{O}(n \log n)$ (dominated by sorting). / $\mathcal{O}(n \log n)$ (정렬이 지배적).
• Gift-Wrapping (Jarvis March) / Gift-Wrapping (Jarvis March): $\mathcal{O}(nh)$ where $h$ is number of hull vertices. / $\mathcal{O}(nh)$ ($h$는 헐 꼭짓점 수).

Visualization / 시각화:

CCW (Counter-Clockwise) Test:

Points: a(0,0), b(2,0), p(1,1)

CCW(a,b,p) = (1-0)(2-0) - (1-0)(0-0) = 2 > 0
→ p is to the LEFT of line ab (counter-clockwise)

     p(1,1)
      |
      |
a(0,0)---b(2,0)

If p(1,-1):
CCW(a,b,p) = (-1-0)(2-0) - (1-0)(0-0) = -2 < 0
→ p is to the RIGHT (clockwise)

CCW Visual Examples:

Case 1: CCW > 0 (Left turn, Counter-clockwise)
        p
        |
        |
    a ──┴── b
    (p is to the left)

Case 2: CCW < 0 (Right turn, Clockwise)
    a ──┬── b
        |
        |
        p
    (p is to the right)

Case 3: CCW = 0 (Collinear)
    a ─── p ─── b
    (p is on the line)

Cross Product Interpretation:
CCW(a,b,p) = (b - a) × (p - a)
  = |b-a| × |p-a| × sin(θ)
  = area of parallelogram
  = 2 × area of triangle

Convex Hull Example (Graham Scan):

Points: (0,0), (4,0), (3,1), (1,1), (2,2), (0,3)

Step 1: Find bottom-leftmost: (0,0)
Step 2: Sort by angle: (0,0), (4,0), (3,1), (2,2), (1,1), (0,3)
Step 3: Build hull:
  Start: (0,0), (4,0)
  Add (3,1): CCW > 0 → keep
  Add (2,2): CCW > 0 → keep
  Add (1,1): CCW < 0 → remove (2,2), check again
  Add (0,3): CCW > 0 → keep

Convex Hull: (0,0) → (4,0) → (3,1) → (0,3) → (0,0)

Real Problem Applications:

• Fragile Letters (fra): Geometry problem involving polygon stability. For each edge, check if the polygon can stand on that edge (center of mass must be above the edge, only one edge touches ground). Uses polygon area calculation (shoelace formula) and centroid computation. (EN: Polygon stability - check which edges can serve as base. Requires area, centroid, and geometric checks. KR: 다각형 안정성 - 어떤 변이 밑면이 될 수 있는지 확인. 넓이, 중심, 기하 검사 필요.)
• The Euler Line (eul): Collinearity check using cross product. Given three points (centroid, orthocenter, circumcenter), check if they are collinear. In projective geometry, this is done by checking if the cross product of two vectors is zero (or checking if three points lie on the same line using cross product). (EN: Collinearity test - three points are collinear if cross product of vectors between them is zero. KR: 공선성 테스트 - 세 점 사이의 벡터의 외적이 0이면 공선.)

Geometry Algorithms Comparison / 기하학 알고리즘 비교:

Algorithm	Problem	Time Complexity	Space Complexity	Key Operation
CCW Test	Point-line orientation / 점-선 방향	$\mathcal{O}(1)$	$\mathcal{O}(1)$	Cross product / 외적
Convex Hull (Graham Scan)	Convex hull of points / 점들의 볼록 껍질	$\mathcal{O}(n \log n)$	$\mathcal{O}(n)$	Sorting + CCW test / 정렬 + CCW 테스트
Convex Hull (Jarvis March)	Convex hull of points / 점들의 볼록 껍질	$\mathcal{O}(nh)$	$\mathcal{O}(n)$	Gift-wrapping / 선물 포장
Polygon Area (Shoelace)	Area of polygon / 다각형 넓이	$\mathcal{O}(n)$	$\mathcal{O}(1)$	Sum of cross products / 외적의 합
Line Intersection	Intersection of two lines / 두 직선의 교점	$\mathcal{O}(1)$	$\mathcal{O}(1)$	System of equations / 연립방정식

When to Use / 사용 시기:

• Graham Scan: General case, most efficient. / 일반적인 경우, 가장 효율적.
• Jarvis March: When $h$ (hull vertices) is small. / $h$(헐 꼭짓점 수)가 작을 때.

Complexity Analysis / 복잡도 분석:

Graham Scan:

• Sorting: $\mathcal{O}(n \log n)$ (dominates). / 정렬: $\mathcal{O}(n \log n)$ (지배적).
• Scan: $\mathcal{O}(n)$ - each point pushed/popped at most once. / 스캔: $\mathcal{O}(n)$ - 각 점이 최대 한 번 push/pop.

Jarvis March:

• For each hull vertex: find next point (scan all points). / 각 헐 꼭짓점에 대해: 다음 점 찾기 (모든 점 스캔).
• Total: $h \times n = \mathcal{O}(nh)$ where $h$ is number of hull vertices. / 총합: $h \times n = \mathcal{O}(nh)$ ($h$는 헐 꼭짓점 수).

Possible Questions:

• How does Graham’s scan work? (EN: Sort by angle, then scan removing concave points. KR: 각도로 정렬, 그 다음 오목한 점을 제거하며 스캔.)
• What is a right turn? (EN: CCW < 0, meaning the turn makes the polygon concave. KR: CCW < 0, 다각형을 오목하게 만드는 회전.)
• Why is Graham Scan O(n log n)? (EN: Sorting dominates. The scan itself is O(n). KR: 정렬이 지배적. 스캔 자체는 O(n).)

---

9.4 Polygon Area

• Shoelace Formula / 신발끈 공식: \(\text{Area} = \frac{1}{2}\left|\sum_{i=1}^{n}(x_i y_{i+1} - x_{i+1} y_i)\right|\)
• Signed Area / 부호 있는 넓이: Without absolute value, positive if CCW, negative if CW. / 절댓값 없이, CCW면 양수, CW면 음수.