계산기하학
계산기하학(計算幾何學, computational geometry)은 기하학과 관련하여 설명될 수 있는 알고리즘 연구에 전념하는 컴퓨터 과학의 한 분야이다. 순수하게 기하학적인 문제 중 일부는 계산기하학 알고리즘 연구에서 발생하며, 이러한 문제도 계산기하학의 일부로 간주된다. 현대 계산기하학은 최근의 발전이지만, 고대부터 역사를 거슬러 올라가는 컴퓨팅 분야 중 가장 오래된 분야 중 하나이다.
계산 복잡도는 계산기하학의 핵심이며, 수천만 또는 수억 개의 점을 포함하는 매우 큰 데이터 세트에 알고리즘이 사용될 경우 큰 실제적 중요성을 갖는다. 이러한 세트의 경우 O(n2)와 O(n log n)의 차이는 며칠과 몇 초의 계산 차이가 될 수 있다.
계산기하학이 학문으로서 발전하게 된 주요 동기는 컴퓨터 그래픽스와 컴퓨터 지원 설계 및 제조(CAD/CAM)의 발전이었지만, 계산기하학의 많은 문제는 본질적으로 고전적이며, 수학적 시각화에서 비롯될 수 있다.
계산기하학의 다른 중요한 응용 분야로는 로봇공학 (동작 계획 및 가시성 문제), 지리 정보 시스템 (GIS) (기하학적 위치 및 검색, 경로 계획), 집적 회로 설계 (IC 기하학 설계 및 검증), 컴퓨터 이용 공학 (CAE) (메시 생성), 컴퓨터 비전 (3D 재구성) 등이 있다.
계산기하학의 주요 분야는 다음과 같다.
- 조합 계산기하학(algorithmic geometry라고도 함)은 기하학적 객체를 이산적인 개체로 다룬다. 프레파라타와 샤모스가 이 주제에 대해 쓴 기초 서적은 1975년에 "계산기하학"이라는 용어가 이 의미로 처음 사용되었다고 기록한다.[1]
- 수치 계산기하학(machine geometry, CAGD, 또는 기하학적 모델링이라고도 함)은 주로 CAD/CAM 시스템에서 컴퓨터 계산에 적합한 형태로 실제 객체를 표현하는 것을 다룬다. 이 분야는 화법기하학의 추가적인 발전으로 볼 수 있으며 종종 컴퓨터 그래픽스 또는 CAD의 한 분야로 간주된다. 이 의미의 "계산기하학"이라는 용어는 1971년부터 사용되었다.[2]
대부분의 계산기하학 알고리즘은 전자 컴퓨터를 위해 개발되었지만 (그리고 개발되고 있지만), 일부 알고리즘은 비전통적인 컴퓨터 (예: 광학 컴퓨터 [3])를 위해 개발되었다.
조합 계산기하학
[편집]조합 계산기하학 연구의 주요 목표는 점, 선분, 다각형, 다면체 등과 같은 기본 기하학적 객체를 통해 명시된 문제를 해결하기 위한 효율적인 알고리즘과 자료 구조를 개발하는 것이다.
이러한 문제 중 일부는 너무 간단해 보여서 컴퓨터가 등장하기 전까지는 문제로 간주되지도 않았다. 예를 들어, 최근접 쌍 문제를 고려해 보자.
- 평면 상의 n개의 점이 주어졌을 때, 서로 간의 거리가 가장 작은 두 점을 찾아라.
모든 점 쌍 사이의 거리를 계산할 수 있으며, 그 수는 n(n − 1)/2개이다. 그런 다음 가장 작은 거리를 가진 쌍을 선택한다. 이 무차별 대입 검색 알고리즘은 O(n2) 시간이 걸린다. 즉, 실행 시간은 점 개수의 제곱에 비례한다. 계산기하학의 고전적인 결과는 O(n log n) 시간이 걸리는 알고리즘의 공식화였다. O(n) 예상 시간을 갖는 확률적 알고리즘도 발견되었으며,[4] O(n log log n) 시간이 걸리는 결정론적 알고리즘도 발견되었다.[5]
문제 유형
[편집]계산기하학의 핵심 문제는 다양한 기준에 따라 여러 가지 방식으로 분류될 수 있다. 다음의 일반적인 유형을 구분할 수 있다.
정적 문제
[편집]이 범주의 문제에서는 일부 입력이 주어지고 해당 출력을 구성하거나 찾아야 한다. 이 유형의 몇 가지 기본적인 문제는 다음과 같다.
- 볼록 폐포: 주어진 점 집합에서 모든 점을 포함하는 가장 작은 볼록 다면체/다각형을 찾아라.
- 선분 교차: 주어진 선분 집합 간의 교차점을 찾아라.
- 델로네 삼각분할
- 보로노이 다이어그램: 주어진 점 집합에서 주어진 점에 가장 가까운 점에 따라 공간을 분할한다.
- 선형 계획법
- 최근접 점 쌍: 주어진 점 집합에서 서로 간의 거리가 가장 작은 두 점을 찾아라.
- 가장 먼 점 쌍
- 가장 큰 빈 원: 주어진 점 집합에서 볼록 폐포 내부에 중심이 있고 아무 점도 포함하지 않는 가장 큰 원을 찾아라.
- 유클리드 최단 경로: 유클리드 공간(다면체 장애물 포함)에서 두 점을 최단 경로로 연결한다.
- 다각형 삼각분할: 주어진 다각형의 내부를 삼각형으로 분할한다.
- 메시 생성
- 다각형의 불리언 연산
이 유형의 문제에 대한 계산 복잡도는 주어진 문제 인스턴스를 해결하는 데 필요한 시간과 공간(컴퓨터 메모리)으로 추정된다.
기하학적 질의 문제
[편집]
공간 질의 문서를 참고하십시오.기하학적 질의 문제(일반적으로 기하학적 검색 문제로 알려짐)에서 입력은 검색 공간 부분과 문제 인스턴스에 따라 달라지는 질의 부분의 두 부분으로 구성된다. 검색 공간은 일반적으로 여러 질의에 효율적으로 답변할 수 있도록 전처리되어야 한다.
몇 가지 기본적인 기하학적 질의 문제는 다음과 같다.
- 범위 검색: 질의 영역 내의 점 개수를 효율적으로 세기 위해 점 집합을 전처리한다.
- 점 위치 문제: 공간이 셀로 분할되어 있을 때, 질의 점이 어느 셀에 위치하는지 효율적으로 알려주는 자료 구조를 생성한다.
- 최근접 이웃: 질의 점에 가장 가까운 점을 효율적으로 찾기 위해 점 집합을 전처리한다.
- 광선 추적: 공간에 있는 객체 집합이 주어졌을 때, 질의 광선이 어떤 객체를 먼저 교차하는지 효율적으로 알려주는 자료 구조를 생성한다.
검색 공간이 고정된 경우, 이 유형의 문제에 대한 계산 복잡도는 일반적으로 다음과 같이 추정된다.
- 검색할 자료 구조를 구축하는 데 필요한 시간과 공간
- 질의에 답변하는 데 필요한 시간 (때로는 추가 공간)
검색 공간이 변경될 수 있는 경우는 § 동적 문제를 참조하라.
동적 문제
[편집]또 다른 주요 유형은 동적 문제이다. 이 유형의 목표는 입력 데이터의 각 점진적인 수정(입력 기하학적 요소의 추가 또는 삭제) 후에 반복적으로 해답을 찾기 위한 효율적인 알고리즘을 찾는 것이다. 이 유형의 문제에 대한 알고리즘은 일반적으로 동적 자료 구조를 포함한다. 계산기하학의 모든 문제는 처리 시간 증가를 대가로 동적 문제로 변환될 수 있다. 예를 들어, 범위 검색 문제는 점의 추가 및 삭제를 제공하여 동적 범위 검색 문제로 변환될 수 있다. 동적 볼록 폐포 문제는 볼록 폐포를 추적하는 것이다. 예를 들어, 동적으로 변경되는 점 집합에 대해 즉, 입력 점이 삽입되거나 삭제될 때 볼록 폐포를 추적하는 것이다.
이 유형의 문제에 대한 계산 복잡도는 다음과 같이 추정된다.
- 검색할 자료 구조를 구축하는 데 필요한 시간과 공간
- 검색 공간의 점진적 변경 후 검색된 자료 구조를 수정하는 데 필요한 시간과 공간
- 질의에 답변하는 데 필요한 시간 (때로는 추가 공간)
변형
[편집]일부 문제는 맥락에 따라 어느 범주에 속하는 것으로 취급될 수 있다. 예를 들어, 다음 문제를 고려해 보자.
- 점-다각형 판정 문제: 점이 주어진 다각형 내부에 있는지 외부에 있는지 결정한다.
많은 응용 프로그램에서 이 문제는 단일 처리 문제로 취급된다. 즉, 첫 번째 유형에 속한다. 예를 들어, 많은 컴퓨터 그래픽스 응용 프로그램에서 흔한 문제는 포인터로 화면의 어느 영역이 클릭되었는지 찾는 것이다. 그러나 일부 응용 프로그램에서는 문제의 다각형은 불변인 반면 점은 질의를 나타낸다. 예를 들어, 입력 다각형은 국가의 국경을 나타낼 수 있고 점은 항공기의 위치일 수 있으며, 문제는 항공기가 국경을 침범했는지 여부를 결정하는 것이다. 마지막으로, 이전에 언급된 컴퓨터 그래픽스 예시에서, CAD 응용 프로그램에서는 변경되는 입력 데이터가 종종 동적 자료 구조에 저장되며, 이는 점-다각형 질의 속도를 높이는 데 활용될 수 있다.
질의 문제의 일부 맥락에서는 질의 순서에 대한 합리적인 기대치가 있으며, 이는 효율적인 자료 구조 또는 더 엄격한 계산 복잡도 추정에 활용될 수 있다. 예를 들어, 어떤 경우에는 단일 질의보다 전체 N개 질의 시퀀스에 대한 총 시간의 최악의 경우가 중요하다. 분할 상환 분석도 참조하라.
수치 계산기하학
[편집] 이 부분의 본문은 컴퓨터 지원 기하학적 설계입니다.이 분야는 또한 기하학적 모델링 및 컴퓨터 지원 기하학적 설계(CAGD)로 알려져 있다.
핵심 문제는 곡선 및 표면 모델링 및 표현이다.
여기서 가장 중요한 도구는 베지에 곡선, 스플라인 곡선 및 표면과 같은 매개변수 곡선 및 매개변수 곡면이다. 중요한 비매개변수적 접근 방식은 레벨집합 방법이다.
계산기하학의 응용 분야에는 조선, 항공기 및 자동차 산업이 포함된다.
같이 보기
[편집]
각주
[편집]- ↑ Franco P. Preparata and Michael Ian Shamos (1985). 《Computational Geometry – An Introduction》. Springer-Verlag. ISBN 0-387-96131-3. 1st edition; 2nd printing, corrected and expanded, 1988.
- ↑ A.R. Forrest, "Computational geometry", Proc. Royal Society London, 321, series 4, 187–195 (1971)
- ↑ Yevgeny B. Karasik (2019). 《Optical Computational Geometry》. ISBN 979-8511243344.
- ↑ S. Khuller and Y. Matias. A simple randomized sieve algorithm for the closest-pair problem. Inf. Comput., 118(1):34–37, 1995 (PDF)
- ↑ S. Fortune and J.E. Hopcroft. "A note on Rabin's nearest-neighbor algorithm". Information Processing Letters, 8(1), pp. 20–23, 1979
