Listen to this article

계산기하학

Computational geometry
저널은 계산 지오메트리(저널)를 참조하십시오.

계산기하학은 기하학의 관점에서 기술할 수 있는 알고리즘 연구에 전념하는 컴퓨터 과학의 한 분야이다.일부 순수 기하학적 문제는 계산 기하학 알고리즘의 연구에서 발생하며, 이러한 문제는 계산 기하학의 일부로 간주됩니다.현대 컴퓨터 기하학은 최근의 발전이지만, 고대까지 거슬러 올라가는 역사를 가진 가장 오래된 컴퓨터 분야 중 하나입니다.

계산 복잡성은 계산 기하학의 핵심이며, 알고리즘이 수천 또는 수억 개의 포인트를 포함하는 매우 큰 데이터 세트에 사용되는 경우 실질적으로 매우 중요합니다.이러한 집합의 경우, O2(n)와 O(n log n)의 차이는 계산의 일수와 초의 차이일 수 있습니다.

컴퓨터 지오메트리의 한 분야로서의 개발의 주된 추진력은 컴퓨터 그래픽과 컴퓨터 지원 설계 및 제조(CAD/CAM)의 진보였지만, 컴퓨터 지오메트리의 많은 문제는 본질적으로 고전적이고 수학적 시각화에서 비롯될 수 있습니다.

컴퓨터 지오메트리의 다른 중요한 응용 프로그램에는 로봇 공학(운동 계획 및 가시성 문제), 지리 정보 시스템(GIS)(지리학적 위치 및 검색, 경로 계획), 집적 회로 설계(IC 지오메트리 설계 및 검증), 컴퓨터 지원 엔지니어링(CAE)(메쉬 생성) 및 컴퓨터 비전(3D 재고)이 포함됩니다.무단결석)

계산기하학의 주요 분기는 다음과 같습니다.

  • 알고리즘 지오메트리라고도 불리는 조합 계산 지오메트리는 기하학적 객체를 이산 엔티티로 취급합니다.프리페아타와 샤모스가 이 주제에 관한 기초적인 책을 통해 1975년까지 [1]"컴퓨터 기하학"이라는 용어가 처음 사용된 시기로 추정됩니다.
  • 수치 계산 지오메트리는 기계 형상, CAGD(Computer-Aided Geometry Design) 또는 기하학적 모델링이라고도 불리며, 주로 CAD/CAM 시스템의 컴퓨터 계산에 적합한 형태로 실제 개체를 표현합니다.이 분기는 기술 기하학의 발전으로 간주될 수 있으며, 종종 컴퓨터 그래픽스 또는 CAD의 분기로 간주됩니다.이 의미의 "컴퓨터 기하학"이라는 용어는 [2]1971년부터 사용되어 왔다.

계산기하학의 알고리즘은 대부분 전자 컴퓨터를 위해 개발되어 왔지만(그리고 개발되고 있다) 일부 알고리즘은 비전통적인 컴퓨터(광학 컴퓨터 등)를 위해 개발되었다.

조합계산기하학

조합 계산 기하학 연구의 주요 목표는 기본 기하학적 객체(점, 선분, 다각형, 다면체 등)의 관점에서 기술된 문제를 해결하기 위한 효율적인 알고리즘과 데이터 구조를 개발하는 것이다.

이러한 문제들 중 일부는 너무 단순해 보여서 컴퓨터가 등장하기 전까지는 전혀 문제로 여겨지지 않았다.예를 들어 가장 가까운 쌍의 문제를 생각해 보겠습니다.

  • 평면에서 n개의 점을 지정하면 서로 거리가 가장 작은 두 점을 찾습니다.

n(n-1)/2가 있는 모든 점 쌍 사이의 거리를 계산한 다음 가장 작은 거리를 가진 쌍을 선택할 수 있다.이 brute-force 알고리즘에는 O(n2) 시간이 걸립니다.즉, 실행 시간은 포인트 수의 제곱에 비례합니다.계산기하학의 고전적인 결과는 O(n log n)를 취하는 알고리즘의 공식화였다.O(n)의 [4]예상 시간이 걸리는 랜덤화 알고리즘과 O(n log n)[5]의 시간이 걸리는 결정론적 알고리즘도 발견되었다.

문제 클래스

계산기하학의 핵심 문제는 다양한 기준에 따라 다른 방식으로 분류될 수 있다.다음과 같은 일반 클래스가 구별될 수 있습니다.

정적인 문제

이 범주의 문제에서는 일부 입력이 제공되며 해당 출력을 구성하거나 찾아야 합니다.이러한 유형의 근본적인 문제는 다음과 같습니다.

  • 볼록 선체: 일련의 점을 지정하면 모든 점을 포함하는 가장 작은 볼록 다면체/폴리곤을 찾습니다.
  • 선분 교차로:주어진 선분 집합 사이의 교차로를 찾습니다.
  • 들라우나이 삼각 측량
  • Voronoi 다이어그램: 일련의 점을 지정하면 지정된 점에 가장 가까운 점에 따라 공간을 분할합니다.
  • 선형 프로그래밍
  • 가장 가까운 점 쌍: 일련의 점을 지정하면 서로 거리가 가장 작은 두 점을 찾습니다.
  • 가장 먼 점 쌍
  • 가장 큰 빈 원: 일련의 점을 지정하면 볼록한 선체 안쪽에 중심이 있고 둘 다 감싸지 않은 가장 큰 원을 찾습니다.
  • 유클리드 최단 경로: (다면체 장애물이 있는) 유클리드 공간의 두 점을 최단 경로로 연결합니다.
  • 폴리곤 삼각 측량: 폴리곤을 지정하면 내부를 삼각형으로 분할합니다.
  • 메쉬 생성
  • 폴리곤의 부울 연산

이러한 종류의 문제에 대한 계산 복잡도는 주어진 문제 인스턴스를 해결하는 데 필요한 시간과 공간(컴퓨터 메모리)에 의해 추정됩니다.

기하학적 쿼리 문제

기하학적 검색 문제로 일반적으로 알려진 기하학적 쿼리 문제에서 입력은 두 부분으로 구성됩니다. 즉, 검색 공간 부분과 쿼리 부분으로, 문제 인스턴스에 따라 다릅니다.일반적으로 검색 공간은 여러 쿼리에 효율적으로 응답할 수 있도록 사전 처리해야 합니다.

기본적인 기하학적 쿼리 문제는 다음과 같습니다.

  • 범위 검색: 쿼리 영역 내의 포인트 수를 효율적으로 계산하기 위해 포인트 세트를 사전 처리합니다.
  • 점 위치: 공간을 셀로 분할하면 쿼리 지점이 어느 셀에 있는지 효율적으로 알려주는 데이터 구조를 생성합니다.
  • 가장 가까운 이웃: 쿼리 포인트에 가장 가까운 점을 효율적으로 찾기 위해 일련의 점을 사전 처리합니다.
  • 레이 트레이스: 공간에 있는 객체 세트를 지정하면 쿼리 레이가 먼저 교차하는 객체를 효율적으로 알려주는 데이터 구조를 생성합니다.

서치 공간이 고정되어 있는 경우, 이 종류의 문제에 대한 계산 복잡도는 보통 다음과 같이 추정됩니다.

  • 검색할 데이터 구조를 구축하는 데 필요한 시간과 공간
  • 질의에 응답하는 시간(경우에 따라 추가 공간)

서치 공간을 변경할 수 있는 경우 "동적 문제"를 참조하십시오.

동적 문제

그러나 또 다른 주요 클래스는 동적 문제이며, 여기서 목표는 입력 데이터(추가 또는 삭제 입력 기하학적 요소)의 각 증분 수정 후 반복적으로 해결책을 찾기 위한 효율적인 알고리즘을 찾는 것이다.이러한 유형의 문제에 대한 알고리즘은 일반적으로 동적 데이터 구조를 포함합니다.연산 기하학적 문제 중 하나는 처리 시간의 증가를 희생하면서 동적 문제로 변환될 수 있다.예를 들어 레인지 검색 문제는 포인트의 추가 및/또는 삭제를 제공함으로써 다이내믹 레인지 검색 문제로 변환할 수 있다.동적 볼록 선체 문제는 입력 지점이 삽입 또는 삭제되는 동안 동적으로 변화하는 포인트 세트에 대해 볼록 선체를 추적하는 것이다.

이러한 종류의 문제에 대한 계산 복잡도는 다음과 같이 추정됩니다.

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

바리에이션

상황에 따라서는, 몇개의 문제가 어느쪽인가의 카테고리에 속하는 것으로 취급되는 경우가 있습니다.예를 들어, 다음 문제를 고려합니다.

  • 폴리곤의 점:점이 지정된 폴리곤 내부 또는 외부에 있는지 여부를 결정합니다.

많은 애플리케이션에서 이 문제는 싱글샷(즉, 퍼스트 클래스에 속하는 것)으로 취급됩니다.예를 들어 컴퓨터 그래픽스의 많은 응용 프로그램에서 공통적인 문제는 포인터로 화면의 어느 영역을 클릭하는지 찾는 것입니다.그러나 일부 응용 프로그램에서는 해당 폴리곤이 불변인 반면 점은 쿼리를 나타냅니다.예를 들어 입력 폴리곤은 국가의 국경을 나타내고 지점은 항공기의 위치를 나타낼 수 있으며, 문제는 항공기가 국경을 위반했는지 여부를 판단하는 것이다.마지막으로 앞서 언급한 컴퓨터 그래픽스 예에서 CAD 어플리케이션에서는 변경 입력 데이터가 동적 데이터 구조에 저장되는 경우가 많아 포인트 인 폴리곤 쿼리를 고속화하기 위해 이용될 수 있다.

쿼리 문제의 일부 상황에서는 쿼리의 시퀀스에 대한 합리적인 기대가 존재하며, 이는 효율적인 데이터 구조 또는 보다 엄격한 계산 복잡도 추정에 악용될 수 있습니다.예를 들어 단일 쿼리가 아닌 N개의 쿼리 시퀀스 전체에 대해 최악의 경우를 파악하는 것이 중요합니다."변형 분석"을 참조하십시오.

수치계산기하학

주요 기사: 컴퓨터 지원 기하학적 디자인

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

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

여기서 가장 중요한 계측기는 파라메트릭 곡선 및 베지어 곡선, 스플라인 곡선 및 표면과 같은 파라메트릭 표면입니다.중요한 비모수적 접근법은 수준 설정 방법이다.

컴퓨터 기하학의 응용 분야에는 조선, 항공기 및 자동차 산업이 포함됩니다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ 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.
  2. ^ A.R. Forrest, "컴퓨터 기하학", Proc. 로열 소사이어티 런던, 321, 시리즈 4, 187-195(1971년)
  3. ^ Yevgeny B. Karasik (2019). Optical Computational Geometry. ISBN 979-8511243344.
  4. ^ S. Khuller와 Y.마티아스.가장 가까운 쌍의 문제에 대한 단순한 랜덤화된 체 알고리즘.Inf. 컴퓨터, 118 (1):34 - 37,1995 (PDF)
  5. ^ S. Fortune과 J.E.홉크로프트."라빈의 가장 가까운 이웃 알고리즘에 대한 메모"정보처리 서신, 8(1), 페이지 20 - 23, 1979

추가 정보

일지

조합/알고리즘 계산 지오메트리

아래는 기하학 알고리즘에 관한 연구를 발표해 온 주요 학술지 목록입니다.컴퓨터 지오메트리에 특화된 저널이 등장함에 따라 범용 컴퓨터 사이언스 저널과 컴퓨터 그래픽 저널에서 기하학 출판물의 점유율이 감소했다는 점에 주목하십시오.

외부 링크

이 기사 듣기 (9분)
Spoken Wikipedia icon
이 오디오 파일은 2013년 9월 17일(2013-09-17) 본 문서의 개정판에서 작성되었으며 이후 편집 내용은 반영되지 않습니다.
(오디오 도움말, 기타 음성 기사)