계산기하학

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 역사
3. 조합론적 계산기하학
4. 수치 계산 기하학
- 4.1. 핵심 개념
5. 응용 분야
6. 관련 학술지
참조

1. 개요

계산 기하학은 기하학적 문제 해결을 위한 알고리즘과 자료 구조를 연구하는 컴퓨터 과학의 한 분야이다. 점, 선분, 다각형, 다면체 등 기하학적 객체를 다루며, 최소 볼록 껍질, 선분 교차, 보로노이 다이어그램, 최단 거리 찾기 등과 관련된 문제들을 해결하기 위한 효율적인 알고리즘 개발을 목표로 한다. 정적, 기하 질의, 동적 문제로 분류되며, 조선, 항공기, 자동차 산업 등 다양한 분야에 응용된다.

더 읽어볼만한 페이지

계산기하학 - 보로노이 다이어그램
보로노이 다이어그램은 거리 공간에서 점 집합을 기반으로 공간을 분할하는 기하학적 구조이며, 각 점까지의 거리가 가장 가까운 공간 영역인 보로노이 셀들의 집합을 의미하고 다양한 분야에서 활용된다.
계산기하학 - Discrete & Computational Geometry
Discrete & Computational Geometry는 수학 및 컴퓨터 과학 분야의 학술 저널이며, 다양한 데이터베이스에 수록되어 있고, 길 칼라이와 새뮤얼 퍼거슨의 논문을 게재하고 풀커슨 상을 수상했다.
컴퓨터 과학 - 수학적 최적화
수학적 최적화는 주어진 집합에서 실수 또는 정수 변수를 갖는 함수의 최댓값이나 최솟값을 찾는 문제로, 변수 종류, 제약 조건, 목적 함수 개수에 따라 다양한 분야로 나뉘며 여러 학문 분야에서 활용된다.
컴퓨터 과학 - 증명 보조기
증명 보조기는 수학적 증명의 정확성을 검증하고 형식적인 증명 탐색을 지원하는 소프트웨어 도구로, 고차 논리, 의존 타입, 작은 커널, 자동 정리 증명, 반사 증명, 코드 생성 등의 다양한 기능을 제공하며, "정리 증명기 박물관" 프로젝트를 통해 소스 보존을 목표로 하는 다양한 시스템들이 존재한다.
수학 - 회귀 분석
회귀 분석은 종속 변수와 하나 이상의 독립 변수 간의 관계를 모델링하고 분석하는 통계적 기법으로, 최소 제곱법 개발 이후 골턴의 연구로 '회귀' 용어가 도입되어 다양한 분야에서 예측 및 인과 관계 분석에 활용된다.
수학 - 수학적 최적화
수학적 최적화는 주어진 집합에서 실수 또는 정수 변수를 갖는 함수의 최댓값이나 최솟값을 찾는 문제로, 변수 종류, 제약 조건, 목적 함수 개수에 따라 다양한 분야로 나뉘며 여러 학문 분야에서 활용된다.

계산기하학
개요
분야	컴퓨터 과학
하위 분야	알고리즘, 기하학
관련 분야	이산 기하학 전산 위상수학 컴퓨터 그래픽스 CAD/CAM
상세 정보
설명	기하학적 문제를 해결하는 알고리즘 연구 분야
목표	기하학적 객체를 효율적으로 표현하고 조작하는 알고리즘 설계
응용 분야	컴퓨터 그래픽스 로봇 공학 지리 정보 시스템 (GIS) 컴퓨터 지원 설계 (CAD) 컴퓨터 지원 제조 (CAM) 패턴 인식
주요 문제	볼록 껍질 계산 선 교차 문제 삼각 분할 보로노이 다이어그램 점 위치 결정
중요성	다양한 분야에서 효율적인 알고리즘 개발에 기여
역사
기원	1970년대 후반
주요 인물	마이클 이언 셰이모스 프랑코 프레파라타
영향	알고리즘 및 데이터 구조 연구에 큰 영향

2. 역사

계산 기하학은 컴퓨터 그래픽스의 발전, 컴퓨터 지원 디자인 및 조작(CAD/CAM) 연구 분야로서의 측면을 주요 동기로 전개되었지만, 계산 기하학에서의 문제는 그 대부분이 자연계에서의 고전적인 기하학 문제이다.

그 외에 계산 기하학의 중요한 응용 분야는 다음과 같다.

로봇 공학: 행동 계획 및 문제의 가시성
기하 정보 시스템: 기하학적 배치 및 탐색, 경로 선정
집적 회로 설계: 집적 회로의 기하학적 설계와 검증
컴퓨터 지원 공학: 수치 제어 기계의 프로그래밍

계산 기하학의 주요 분과에는 다음과 같은 것들이 있다.

조합론적 계산 기하학: 이산적인 존재로서의 기하학적 대상을 다룬다. 이 주제의 기초가 되는 기본적인 교과서는 1975년에 처음으로 이 의미로 "계산 기하학"이라는 용어를 사용한 Preparata와 Shamos이다.
수치 계산 기하학, 컴퓨터 지원 기하학적 디자인, 기하학적 모델링: 실세계의 물체를 CAD/CAM 시스템에서의 컴퓨터 계산에 적합한 형태로 표현하는 것을 주로 다룬다. 이 분과는 투영 기하학의 더욱 발전된 형태라고 볼 수 있으며, 종종 컴퓨터 그래픽스나 CAD에 관한 분야의 일부로 여겨진다. 이 의미로 용어 "계산 기하학"이 사용된 것은 1971년부터이다.

3. 조합론적 계산기하학

조합론적 계산기하학은 이산적인 존재로서의 기하학적 대상을 다룬다. 1975년에 Preparata와 Shamos가 처음으로 "계산 기하학"이라는 용어를 사용하면서 이 주제의 기초가 되는 기본적인 교과서가 되었다.^[4]

주된 목표는 점, 선분, 다각형, 다면체 등 기본적인 기하학적 객체로 표현되는 문제를 해결하기 위한 효율적인 알고리즘과 자료 구조를 개발하는 것이다.

이러한 문제들 중 일부는 컴퓨터가 등장하기 전까지는 문제로 간주되지 않을 정도로 단순해 보인다. 예를 들어, 최근접 쌍 문제는 평면에 ''n''개의 점이 주어졌을 때, 서로 가장 가까운 두 점을 찾는 문제이다.

모든 점 쌍 간의 거리를 계산하여 가장 작은 거리를 가진 쌍을 선택하는 무차별 대입 알고리즘은 O(''n''²) 시간이 걸린다. 즉, 실행 시간은 점의 수의 제곱에 비례한다. 그러나 계산 기하학에서는 O(''n'' log ''n'') 시간이 걸리는 효율적인 알고리즘이 개발되었다. O(''n'') 기대 시간을 갖는 확률적 알고리즘^[4]과 O(''n'' log log ''n'') 시간이 걸리는 결정론적 알고리즘^[5]도 발견되었다.

계산 기하학에서는 알고리즘이 매우 거대한 데이터 집합 위에서 사용되는 것을 상정하여 계산 복잡도를 매우 중요시한다. 거대한 데이터 집합에 대해 O(''n''²)와 O(''n'' log ''n'')의 차이는, 계산이 며칠이 걸리느냐, 혹은 몇 초 만에 끝나느냐와 같이 명확한 차이를 만들어낸다.

3. 1. 정적 문제

계산 기하학의 핵심 문제들은 다양한 기준에 따라 여러 방식으로 분류될 수 있다. 그 중 정적 문제는 다음과 같다.

볼록 껍질: 점 집합이 주어지면, 모든 점을 포함하는 가장 작은 볼록 다면체 또는 다각형을 찾는다.
선분 교차: 주어진 선분 집합에서 교차점을 찾는다.
들로네 삼각분할
보로노이 다이어그램: 점 집합이 주어지면, 각 점에 가장 가까운 점에 따라 공간을 분할한다.
선형 계획법
최근접 쌍 문제: 점 집합이 주어지면, 서로 거리가 가장 짧은 두 점을 찾는다.
가장 먼 점 쌍
가장 큰 빈 원: 점 집합이 주어지면, 볼록 껍질 내부에 중심이 있고 점을 포함하지 않는 가장 큰 원을 찾는다.
유클리드 최단 경로: 유클리드 공간(다면체 장애물 포함)에서 두 점을 최단 경로로 연결한다.
다각형 삼각분할: 다각형이 주어지면, 내부를 삼각형으로 분할한다.
메시 생성
다각형에 대한 부울 연산

이러한 문제들은 주어진 입력을 바탕으로 출력을 계산하거나 찾는 것이 목표이다. 예를 들어, 평면에 ''n''개의 점이 주어졌을 때 서로 가장 가까운 두 점을 찾는 '최근접 쌍 문제'를 생각해 보자. 모든 점 쌍 간의 거리를 계산하여 가장 작은 거리를 가진 쌍을 선택하는 무차별 대입 알고리즘은 O(''n''²) 시간이 걸린다. 즉, 실행 시간은 점의 수의 제곱에 비례한다. 그러나 계산 기하학에서는 O(''n'' log ''n'') 시간이 걸리는 효율적인 알고리즘이 개발되었다. O(''n'') 기대 시간을 갖는 확률적 알고리즘^[4]과 O(''n'' log log ''n'') 시간이 걸리는 결정론적 알고리즘^[5]도 발견되었다.

3. 2. 기하학적 질의 문제

범위 검색: 점 집합을 전처리하여, 질의 영역 내의 점의 수를 효율적으로 계산한다.
점 위치 문제: 공간을 셀로 분할한 상태에서, 질의 점이 어느 셀에 위치하는지 효율적으로 알려주는 데이터 구조를 생성한다.
최근접 이웃: 질의점에 가장 가까운 점을 효율적으로 찾기 위해 점 집합을 전처리한다.
광선 추적: 공간에 있는 객체 집합이 주어졌을 때, 질의 광선이 먼저 교차하는 객체를 효율적으로 알려주는 데이터 구조를 생성한다.

3. 3. 동적 문제

입력 데이터가 증분 방식으로 수정될 때마다(입력 기하학적 요소의 추가 또는 삭제) 반복적으로 해를 찾는 효율적인 알고리즘을 찾는 것이 목표인 문제 유형이다. 이 유형의 문제에 대한 알고리즘은 일반적으로 동적 자료 구조를 포함한다. 모든 계산 기하학적 문제는 처리 시간이 증가하는 대가로 동적 문제로 변환될 수 있다. 예를 들어, 범위 검색 문제는 점의 추가 및/또는 삭제를 제공하여 동적 범위 검색 문제로 변환될 수 있다. 동적 볼록 껍질 문제는 입력 점이 삽입되거나 삭제되는 동안 동적으로 변경되는 점 집합에 대한 볼록 껍질을 추적하는 것이다.^[4]

이 유형의 문제에 대한 계산 복잡성은 다음을 통해 추정된다.

검색할 데이터 구조를 구축하는 데 필요한 시간과 공간
검색 공간의 증분 변화 이후 검색된 데이터 구조를 수정하는 시간과 공간
쿼리에 응답하는 데 걸리는 시간(때로는 추가 공간)

4. 수치 계산 기하학

이 분야는 기하학적 모델링 또는 컴퓨터 지원 기하학적 설계(CAGD)로도 알려져 있다.

핵심적인 문제는 곡선 및 곡면의 모델링과 표현이다. 여기서 기본적인 도구는 베지어 곡선이나 스플라인 곡선·스플라인 곡면과 같은 곡선의 매개변수 표시 및 곡면의 매개변수 표시이다. 비매개변수적 방법으로는 레벨 집합이 있다.

응용 분야에는 조선, 항공, 자동차 제품 등이 포함된다. 현대 컴퓨터의 보편화와 성능은 향수병이나 샴푸 병조차 1960년대 조선 기술자라면 상상도 할 수 없는 기법을 사용하여 디자인하고 있다는 것을 의미한다.

4. 1. 핵심 개념

계산 기하학의 핵심 문제에는 다음이 포함된다.

최소볼록집합: 주어진 점을 모두 포함하는 가장 작은 볼록 입체를 구하는 문제이다.
Line segment intersection: 주어진 선분의 교차점을 찾는 문제이다.
보로노이 다이어그램과 들로네 삼각분할
최단 거리 찾기

이 분야는 '''기하 모델링'''과 '''컴퓨터 지원 기하 설계''' (CAGD)로도 알려져 있다.

핵심 문제는 곡선 및 표면 모델링과 표현이다.

여기서 가장 중요한 도구는 매개변수 곡선 및 매개변수 표면으로, 베지어 곡선, 스플라인 곡선 및 표면 등이 있다. 중요한 비매개변수적 접근 방식은 레벨 셋 방법이다.

계산 기하학의 응용 분야는 조선, 항공기 및 자동차 산업을 포함한다. 현대 컴퓨터의 보편화와 성능은 1960년대 조선 기술자라면 상상도 할 수 없는 기법을 사용하여 향수병이나 샴푸 병을 디자인할 수 있음을 의미한다.

5. 응용 분야

계산 기하학은 컴퓨터 그래픽스의 발전, 컴퓨터 지원 디자인 및 조작(CAD/CAM) 연구 분야로서의 측면을 주요 동기로 전개되었지만, 계산 기하학에서의 문제는 그 대부분이 자연계에서의 고전적인 기하학 문제이다.

그 외에 계산 기하학의 중요한 응용 분야는 다음과 같다.

로봇 공학: 행동 계획 및 문제의 가시성
기하 정보 시스템: 기하학적 배치 및 탐색, 경로 선정
집적 회로 설계: 집적 회로의 기하학적 설계와 검증
컴퓨터 지원 공학: 수치 제어 기계의 프로그래밍

6. 관련 학술지

ACM Computing Surveys(ACM 컴퓨팅 서베이)
ACM Transactions on Graphics(ACM 트랜잭션 온 그래픽스)
Acta Informatica(악타 인포르마티카)
Advances in Geometry(기하학 발전)
Algorithmica(알고리드미카)
Ars Combinatoria(아르스 콤비나토리아)
Computational Geometry: Theory and Applications(계산 기하학: 이론과 응용)
Communications of the ACM(ACM 통신)
Computer Graphics and Applications(컴퓨터 그래픽스 앤 애플리케이션)
Computer Graphics World(컴퓨터 그래픽스 월드)
Discrete & Computational Geometry(이산 및 계산 기하학)
Geombinatorics(지오엠비네이터릭스)
Geometriae Dedicata(지오메트리아 데디카타)
IEEE Transactions on Graphics(IEEE 트랜잭션 온 그래픽스)
IEEE Transactions on Computers(IEEE 트랜잭션 온 컴퓨터)
IEEE Transactions on Pattern Analysis and Machine Intelligence(IEEE 트랜잭션 온 패턴 분석 및 기계 지능)
Information Processing Letters(정보 처리 레터)
International Journal of Computational Geometry and Applications(국제 계산 기하학 및 응용 저널)
Journal of Combinatorial Theory, series B(조합론 저널, B 시리즈)
Journal of the ACM(ACM 저널)
Journal of Algorithms(알고리즘 저널)
Journal of Computer and System Sciences(컴퓨터 및 시스템 과학 저널)
Management Science(경영 과학)
Pattern Recognition(패턴 인식)
Pattern Recognition Letters(패턴 인식 레터)
SIAM Journal on Computing(SIAM 컴퓨팅 저널)
SIGACT News(SIGACT 뉴스) - 조셉 오'루크의 "계산 기하학 칼럼" 게재
Theoretical Computer Science(이론 컴퓨터 과학)
The Visual Computer(비주얼 컴퓨터)

참조

_[1] 서적 Computational Geometry - An Introduction "[[Springer-Verlag]]"
_[2] 간행물 Computational geometry Proc. Royal Society London
_[3] 서적 Optical Computational Geometry
_[4] 논문 A simple randomized sieve algorithm for the closest-pair problem https://www.scienced[...]
_[5] 논문 "A note on Rabin's nearest-neighbor algorithm."
_[6] 문서 "Combinatorial computational geometry 또는 algorithmic geometry"
_[7] 서적 Computational Geometry - An Introduction "[[Springer-Verlag]]"
_[8] 문서 "Numerical computational geometry、machine geometry"
_[9] 문서 "computer-aided geometric design、CAGD"
_[10] 문서 geometric modeling
_[11] 간행물 Computational geometry Proc. Royal Society London

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com