중심에서 가장 멀리 떨어진 점 (2D 유클리드 그래프)의 비교적 큰 부분을 선택하는 효율적인 방법을 찾고 있습니다. 이것은 볼록한 선체와 비슷하지만 더 많은 점을 포함합니다. 추가 기준 :그래프에서 바깥 쪽 점을 선택하는 알고리즘 ("rich"convex hull)
선택/세트 ("K")의 포인트 수는 지정된 범위 내에 있어야합니다. 대부분 매우 좁은 것은 아니지만 대부분 다른 범위 (예 : 0.01 * N < K < 0.05 * N 및 0.1 * N < K < 0.2 * N)에서 작동합니다.
알고리즘은 중심으로부터의 거리와 "로컬 밀도"의 균형을 유지할 수 있어야합니다. 그래프 영역의 위쪽 부분에 밀집된 영역이 있지만 하단 부분 근처에 드문 드문 영역이있는 경우 알고리즘은 상단 부분의 점보다 중심에 더 가깝더라도 하단 부분의 일부 점을 선택해야합니다 부위. (아래 예 참조)
보너스 : 중심에서 단순한 거리가 아니라 특정 점 (또는 점과 중심 모두)까지의 거리를 고려하면 완벽 할 것입니다.
내 시도는 지금까지 (좌표 값에 기초하여 상자 포인트를 할당 CXR 박스로 나누어 그래프) "비둘기 천공"를 이용하여 우리가 세트 충분한 포인트가 될 때까지 "외부"박스 선택에 초점을 맞추고있다. 그러나, 나는 고정 된 박스 크기로 인해 과도하게 선택된 고밀도 영역의 선택과 센터를 대신하여 선택된 포인트를 참조로 사용하는 것에 성공하지 못했다.
나는 (가난하게) 그려진 것이 Example입니다. 빨간색 점이 점이고, 녹색 모양은 내가 원하는 것의 예입니다 (녹색 밖에 선택됨). 희소 영역의 경우, 경계 모양이 중심에 더 가까워 적절한 점을 찾습니다 (그러나 중심에 너무 가까울 경우 반드시 찾을 필요는 없습니다). 노란색 상자는 내 Pigeon Holing 기반 알고리즘의 예입니다. 더 좁은 지역을 조정하려고 할 때조차도 잘 관리되지 않습니다.
모든 아이디어를 환영합니다!
두 가지 모두 계산 상 매우 비쌉니다. 두 방법 모두의 복잡성에 대한 아이디어? – Gaminic
네, 맞습니다 - KDE와 알파 형태의 접근 방식은 모두 매우 계산적으로 비쌉니다. 몇 가지 추가 아이디어를 추가했습니다. – mattnedrich
감사합니다. 매우 흥미로운 아이디어. 나는 각각을 잘 살펴보고 경험적 방법으로 그들의 힘을 사용한다고 생각할 수 있는지 알아볼 것입니다. – Gaminic