경계구

가장 작은 경계 원의 일부 예, 2차원의 경계 구체의 경우.

수학에서 $d$ $d$ - 차원 $d$ 공간에서 유한한 확장 객체의 비어 있지 않은 집합이 주어진다. 예를 들어, 해당 집합에 대해 점 집합, 경계 구, 둘러싸는 구 또는 둘러싸는 공은 이러한 모든 물체를 포함하는 $d$ $d$ - 차원 $d$ 고체 구이다.

컴퓨터 그래픽과 컴퓨터 기하학에서 사용되는 바운딩 구체는 바운딩 볼륨의 특별한 유형이다.실시간 컴퓨터 그래픽 어플리케이션에서 실용성이 높은 여러 가지 빠르고 단순한 경계 구체구축 알고리즘이 있다.^[1]

통계학이나 운영연구에서 그 물체는 전형적으로 점이며, 일반적으로 관심의 영역은 최소 경계 영역, 즉 모든 경계 영역 중에서 반경이 최소인 구이다.그러한 구체는 독특하다는 것이 증명될 수 있다: 만약 두 개의 구가 있다면, 문제의 물체는 그들의 교차점 안에 놓여 있다.그러나 반경이 같은 두 개의 비동결 구간의 교차점은 더 작은 반경의 구에 포함되어 있다.

최소 경계 영역의 중심을 계산하는 문제는 "비중치 유클리드 1-중심 문제"로도 알려져 있다.

적용들

클러스터링

그러한 영역은 유사한 데이터 지점의 그룹이 함께 분류되는 클러스터링에 유용하다.

통계적 분석에서 구내 데이터 지점의 산란은 측정 오류 또는 자연적(일반적으로 열적) 프로세스에 기인할 수 있으며, 이 경우 군집은 이상적인 지점의 섭동을 나타낸다.어떤 상황에서는 이 이상적인 지점이 계산 시간을 단축하는 데 유리하게 군집 내 점의 대체물로 사용될 수 있다.

운영 연구에서는 NP-하드 문제에 대한 대략적인 값을 합리적인 시간에 얻기 위해 입력 수를 줄이기 위해 이상적인 지점에 대한 값 군집화를 사용할 수도 있다.선택한 지점은 특이치에 의해 편향될 수 있기 때문에 보통 구의 중심은 아니지만, 대신 최소 제곱점과 같은 평균 위치의 어떤 형태는 군집을 나타내기 위해 계산된다.

알고리즘

경계구 문제 해결을 위한 정확하고 대략적인 알고리즘이 있다.

선형 프로그래밍

님로드 메기도는 1-center 문제를 광범위하게 연구하여 1980년대에 적어도 5번 이상 그것에 대해 발표했다.^[2]1983년에는 치수가 상수로 고정되면 최적의 경계 구역을 찾아 선형 시간대로 달리는 '철거 및 검색' 알고리즘을 제안했다.치수를 고려할 때, 실행 시간 복잡성은 $O((d+1)(d+1)!n)$ 어플리케이션에 비실용적인 $O((d+1)(d+1)!n)$ O $O((d+1)(d+1)!n)$ ( $O((d+1)(d+1)!n)$ ( $O((d+1)(d+1)!n)$ + $O((d+1)(d+1)!n)$ ) $O((d+1)(d+1)!n)$ ( $O((d+1)(d+1)!n)$ + $O((d+1)(d+1)!n)$ ) $O((d+1)(d+1)!n)$ ! $O((d+1)(d+1)!n)$ ) ${\displaystyle O(d+1$ ) (d+1 $)(d+1)!n)}$ 이다.메가도는 이 선형 프로그래밍 접근법을 차원이 고정된 선형 시간에 사용했다.

1991년, Emo Welzl은 Raimund Saidel에 의한 랜덤화 선형 프로그래밍 알고리즘의 확장에 기초하여 훨씬 단순한 랜덤화 알고리즘을 제안했다.예상 선형 시간으로 실행된다.그 논문은 더 높은 차원에서 실용성을 입증하는 실험 결과를 제공한다.^[3]

오픈 소스 컴퓨터 기하 알고리즘 라이브러리(CGAL)는 이 알고리즘의 구현을 포함한다.^[4]

리터의 경계구

1990년에 잭 리터는 최소의 경계 구역을 찾기 위한 간단한 알고리즘을 제안했다.^[5]단순성 때문에 다양한 어플리케이션에서 널리 사용되고 있다.알고리즘은 다음과 같은 방식으로 작동한다.

$P$ $P$ 에서 $x$ 점 $x$ $x$ 을(를) 선택하고 $P$ $p$ ${\displaystyle P$ 에서 $y$ $x$ $x$ 에서 가장 큰 거리를 갖는 점 $y$ $y$ 을(를) 검색하십시오 $x$
$y$ ${\$ $displaystyle y}$ 과 $P$ 와) 가장 큰 거리를가진 P {\ $displaystyle$ $P$ }에서 $z$ 점 z {\ $displaystyle$ z}을 $($ 를 $y$ 검색하십시오 $B$ $y$ {\ $displaysty$ $y}$ 와 $y$ $z$ ${\$ $displaystysty z$ 의 중간점으로 하여 초기 볼 $B$ {\\\ $displaystystystystystytype$ B $}$ 을 설정하십시오. $z$ $}$ 및 z $z$ ;
$만약$ P ${\displaystyle$ P}의 모든 포인트가 $B$ ${\displaystyle$ B} $안$ 에 있다면 $B$ 우리는 경계 구를 얻게 된다.그렇지 않은 $경우$ p{\ $displaystyle p}$ 을(를) 공 바깥쪽 점으로 $p$ 하고, $p$ $p$ 와 $p$ 이전 공을 모두 덮는 새 공을 생성한다.모든 포인트가 포함될 때까지 이 단계를 반복하십시오.

리터의 알고리즘은 $d$ ${\dapplaystyle d}$ -차원 $d$ 공간에서 $n$ $n$ 포인트로 $n$ 구성된 입력에 대해 $O(nd)$ 시간 $O(nd)$ ) $O(nd)$ 로 실행되기 때문에 매우 효율적이다.그러나 그것은 보통 최적보다 5%에서 20% 더 큰 거친 결과만을 제공한다.^{[citation needed]}

코어 집합 기반 근사치

Bădoiu(알. 1+ε{1+\varepsilon\displaystyle}근사가 생성된 영역이 r{r\displaystyle}가장 작은 possi 대부분의(1+ε)r{\displaystyle(1+\varepsilon)r}에서 반경이 의미한다 이 의 경계 영역 problem,[6]1+ε{1+\varepsilon\displaystyle}근사 제시했다.ble경계 구역의 반지름

코어셋은 작은 서브셋으로, 서브셋에서 용액의 $1+\varepsilon$ + $1+\varepsilon$ $1+\varepsilon$ 확장이 $1+\varepsilon$ 전체 세트의 경계 영역이다.코어 세트는 각 반복에서 세트에 가장 먼 점을 추가함으로써 점진적으로 구성된다.

쿠마르 외 연구진은 이 근사 알고리즘을^[7] 개선하여 시간 $O({\frac {nd}{\epsilon }}+{\frac {1}{\epsilon ^{4.5}}}\log {\frac {1}{\epsilon }})$ $O({\frac {nd}{\epsilon }}+{\frac {1}{\epsilon ^{4.5}}}\log {\frac {1}{\epsilon }})$ $O({\frac {nd}{\epsilon }}+{\frac {1}{\epsilon ^{4.5}}}\log {\frac {1}{\epsilon }})$ + $O({\frac {nd}{\epsilon }}+{\frac {1}{\epsilon ^{4.5}}}\log {\frac {1}{\epsilon }})$ $O({\frac {nd}{\epsilon }}+{\frac {1}{\epsilon ^{4.5}}}\log {\frac {1}{\epsilon }})$ 4 $O({\frac {nd}{\epsilon }}+{\frac {1}{\epsilon ^{4.5}}}\log {\frac {1}{\epsilon }})$ $O({\frac {nd}{\epsilon }}+{\frac {1}{\epsilon ^{4.5}}}\log {\frac {1}{\epsilon }})$ $O({\frac {nd}{\epsilon }}+{\frac {1}{\epsilon ^{4.5}}}\log {\frac {1}{\epsilon }})$ $O({\frac {nd}{\epsilon }}+{\frac {1}{\epsilon ^{4.5}}}\log {\frac {1}{\epsilon }})$ $O({\frac {nd}{\epsilon }}+{\frac {1}{\epsilon ^{4.5}}}\log {\frac {1}{\epsilon }})$ ) ${\displaystyle O({\frac {nd}{\epsilon }}}}}{\frac$ { $1}{\epsilon ^{$ 4)로 실행했다 $.$ $5}}\log{\frac{1}{\epsilon }}}$ .

피셔의 정확한 해결사

피셔 외(2003) 알고리즘은 최악의 경우 다항식 실행 시간이 없지만 정확한 해결사를 제안했다.^[8]알고리즘은 순전히 결합형이며 일부 경험적 접근에서 앞서 사용된 선형 프로그래밍을 위한 심플렉스 방법과 유사한 선회형 체계를 구현한다.모든 점을 덮는 큰 구에서 시작하여 더 이상 줄어들 수 없을 때까지 점차 축소한다.이 알고리즘은 이전 저자가 간과한 퇴행의 경우 정확한 종료 규칙과 주요 속도 향상을 야기하는 부분 해결책의 효율적인 처리를 특징으로 한다.저자들은 이 알고리즘이 저·중간(최대 1만) 차원으로 실용적으로 효율적이라는 것을 검증했고, 이 알고리즘이 부동소수점 운영에서 수치적 안정성 문제를 나타내지 않는다고 주장했다.^[8]알고리즘의 C++ 구현은 오픈 소스 프로젝트로 이용할 수 있다.^[9]

극한점 최적구

라르손(2008)은 경계 구문 문제를 해결하기 위해 제어 가능한 속도와 정확도 근사치를 가진 "초단점 최적 구면" 방법을 제안했다.이 방법은 $s$ $s$ 방향 $s$ 벡터 집합을 취하여 작동하며, $s$ ${\$ $displaystyle s$ s {\ $displaystyle s}$ 의 각 벡터에 모든 점을 투영하는 것이 속도-정확한 트레이드오프 변수로 작용한다 $s$ . $2s$ 투영의 2초(\ $displaystyle$ 2s $}$ 극한 $지점$ 에 정확한 용해제를 적용한다 $.$ 그러면 알고리즘은 필요한 경우 구를 증가시키는 나머지 지점(있는 경우)에 대해 반복한다. $large$ n $n$ 의 $n$ 경우 이 방법은 정확한 방법보다 빠른 크기 순서와 유사한 결과를 제공한다. $O(sn)$ 의 경우 O $O(sn)$ ( $O(sn)$ n $){\displaystyle$ O $(sn)}$ 입니다 $O(sn)$

참고 항목

경계량
한정된 구체, 한정된 원

참조

^ ^a ^b Larsson, Thomas (2008), "Fast and tight fitting bounding spheres", SIGRAD 2008: The Annual SIGRAD Conference, Special Theme: Interaction, November 27-28, 2008, Stockholm, Sweden, Linköping Electronic Conference Proceedings, vol. 34, Linköping, Sweden: Linköping University
^ "Nimrod Megiddo's resume and publications ( ????? ?????".
^ Welzl, Emo (1991), "Smallest enclosing disks (balls and ellipsoids)", in Maurer, Hermann (ed.), New Results and New Trends in Computer Science: Graz, Austria, June 20–21, 1991, Proceedings (PDF), Lecture Notes in Computer Science, vol. 555, Berlin, Germany: Springer, pp. 359–370, doi:10.1007/BFb0038202, MR 1254721
^ CGAL 4.3 - Bounding Volumes - Min_sphere_of_spreers_d, 2014-03-30을 검색함.
^ Ritter, Jack (1990), "An efficient bounding sphere", in Glassner, Andrew S. (ed.), Graphics Gems, San Diego, CA, US: Academic Press Professional, Inc., pp. 301–303, ISBN 0-12-286166-3
^ Bādoiu, Mihai; Har-Peled, Sariel; Indyk, Piotr (2002), "Approximate clustering via core-sets" (PDF), Proceedings of the Thirty-Fourth Annual ACM Symposium on Theory of Computing, New York, NY, US: ACM, pp. 250–257, doi:10.1145/509907.509947, MR 2121149, S2CID 5409535
^ Kumar, Piyush; Mitchell, Joseph S. B.; Yıldırım, E. Alper (2003), "Computing core-sets and approximate smallest enclosing hyperspheres in high dimensions", in Ladner, Richard E. (ed.), Proceedings of the Fifth Workshop on Algorithm Engineering and Experiments, Baltimore, MD, USA, January 11, 2003, Philadelphia, PA, US: SIAM, pp. 45–55
^ ^a ^b Fischer, Kaspar; Gärtner, Bernd; Kutz, Martin (2003), "Fast smallest-enclosing-ball computation in high dimensions" (PDF), in Battista, Giuseppe Di; Zwick, Uri (eds.), Algorithms: ESA 2003, 11th Annual European Symposium, Budapest, Hungary, September 16-19, 2003, Proceedings (PDF), Lecture Notes in Computer Science, vol. 2832, Springer, Berlin, pp. 630–641, doi:10.1007/978-3-540-39658-1_57
^ 미니벌 오픈소스 프로젝트

외부 링크

가장 작은 동그라미 문제 – Megiddo의 선형 시간 알고리즘을 포함하여 점 집합을 둘러싸기 위한 몇 가지 알고리즘을 설명한다.

[epos-1] Larsson, Thomas (2008), "Fast and tight fitting bounding spheres", SIGRAD 2008: The Annual SIGRAD Conference, Special Theme: Interaction, November 27-28, 2008, Stockholm, Sweden, Linköping Electronic Conference Proceedings, vol. 34, Linköping, Sweden: Linköping University

[2] "Nimrod Megiddo's resume and publications ( ????? ?????".

[welzl92-3] Welzl, Emo (1991), "Smallest enclosing disks (balls and ellipsoids)", in Maurer, Hermann (ed.), New Results and New Trends in Computer Science: Graz, Austria, June 20–21, 1991, Proceedings (PDF), Lecture Notes in Computer Science, vol. 555, Berlin, Germany: Springer, pp. 359–370, doi:10.1007/BFb0038202, MR 1254721

[4] CGAL 4.3 - Bounding Volumes - Min_sphere_of_spreers_d, 2014-03-30을 검색함.

[Ritter1990-5] Ritter, Jack (1990), "An efficient bounding sphere", in Glassner, Andrew S. (ed.), Graphics Gems, San Diego, CA, US: Academic Press Professional, Inc., pp. 301–303, ISBN 0-12-286166-3

[Badoiu2002-6] Bādoiu, Mihai; Har-Peled, Sariel; Indyk, Piotr (2002), "Approximate clustering via core-sets" (PDF), Proceedings of the Thirty-Fourth Annual ACM Symposium on Theory of Computing, New York, NY, US: ACM, pp. 250–257, doi:10.1145/509907.509947, MR 2121149, S2CID 5409535

[kumar2003-7] Kumar, Piyush; Mitchell, Joseph S. B.; Yıldırım, E. Alper (2003), "Computing core-sets and approximate smallest enclosing hyperspheres in high dimensions", in Ladner, Richard E. (ed.), Proceedings of the Fifth Workshop on Algorithm Engineering and Experiments, Baltimore, MD, USA, January 11, 2003, Philadelphia, PA, US: SIAM, pp. 45–55

[Fischer2003-8] Fischer, Kaspar; Gärtner, Bernd; Kutz, Martin (2003), "Fast smallest-enclosing-ball computation in high dimensions" (PDF), in Battista, Giuseppe Di; Zwick, Uri (eds.), Algorithms: ESA 2003, 11th Annual European Symposium, Budapest, Hungary, September 16-19, 2003, Proceedings (PDF), Lecture Notes in Computer Science, vol. 2832, Springer, Berlin, pp. 630–641, doi:10.1007/978-3-540-39658-1_57

[9] 미니벌 오픈소스 프로젝트

[1]

[2]

[3]

[4]

[5]

[7]

[8]

[9]

Search

경계구

네임스페이스

더

목차

적용들