2D 평면에서 주어진 점을 덮는 가장 작은 원

문제 : 2D 평면에서 주어진 N 점을 덮는 원의 최소 직경은 얼마입니까?2D 평면에서 주어진 점을 덮는 가장 작은 원

이 문제를 해결하는 가장 효율적인 알고리즘은 무엇이며 어떻게 작동합니까?

2011-02-04 Leonid

이 이전 요청하고있다. 내가 찾을 수만 있다면. –

이것은 __Smallest circle problem__ 일 것입니다. __ 여기를보세요 : http://en.wikipedia.org/wiki/Smallest_circle_problem – Jack

여기에 "duplicate"가 있습니다. 물론 내 것이 환상적인 대답은 아닙니다. http : // stackoverflow. com/questions/3102547/how-can-i-find-the-minimal-circle-some-some-given-points – Benjamin

이것은 smallest circle problem입니다. 제안 된 알고리즘에 대한 링크는 참고 자료를 참조하십시오.

E.Welzl, 작은 바깥 디스크 (공 및 타원체), H.에서 마우어 (에드.), 뉴 결과 및 새로운 동향 컴퓨터 과학, 컴퓨터 과학 강의 노트, 권. 555, Springer-Verlag, 359-37 (1991)

은 "가장 빠른"알고리즘에 대한 참조입니다.

출처

2011-02-04 18:29:36 Benjamin

고마워! 나는이 대답을 복제본을 제거하기 위해 원래 질문에 포함시킬 수 있다고 생각한다. – Leonid

가장 작은 둘러싸는 공 문제에 대해 여러 가지 알고리즘과 구현이 있습니다.

2D 및 3D의 경우, Gärtner's implementation이 아마도 가장 빠릅니다.
Girtner, Kutz 및 Fischer의 알고리즘 구현 인 https://github.com/hbf/miniball (상위 : 10,000 개까지)을 살펴보십시오 (참고 : 저는 공동 저자 중 한 명입니다).
매우 높은 차원의 경우 코어 세트 (근사치) 알고리즘이 더 빠릅니다.

참고 : 당신이 구체의 작은 바깥 영역 을 계산하는 알고리즘을 찾고 있다면, 당신은 Computational Geometry Algorithms Library (CGAL)에서 C++ 구현을 찾을 수 있습니다.

출처

2013-02-20 13:29:57 Hbf

가장 먼 점 보로 노이 다이어그램 접근 방식

http://www.dma.fi.upm.es/mabellanas/tfcs/fvd/algorithm.html

는 2 일 문제에 대해 정말 잘 작동 밝혀 (단순히 필요한 헤더 및 소스 파일의 압축을 풉니 다 당신은 CGAL의 모두 사용할 필요는 없습니다.). 그것은 비 반복적이고 확실한 정확성을 보장합니다. 나는 이것이 더 높은 차원으로 잘 확장되지 않는다고 생각한다. 그래서 그것은 문헌에 거의 관심을 보이지 않는 이유이다.

내가 여기에서 설명 할 관심이 있다면 - 위의 링크는 생각하기에 약간 어렵습니다.

편집 다른 링크 : http://ojs.statsbiblioteket.dk/index.php/daimipb/article/view/6704

출처

2013-03-05 14:14:18 agentp

2D 평면에서 주어진 점을 덮는 가장 작은 원

답변

관련 문제