최소 인접 인접 거리와 최대 밀도로 3D 공간에서 확률 적으로 주어진 포인트 샘플링

Jan 10 2021

나는이 n3 차원 공간에 포인트를. 나는 모든 가장 가까운 이웃 거리가보다 큰 점의 하위 집합을 확률 적으로 샘플링하고 싶습니다 r. 부분 집합의 크기 m는 알 수 없지만 샘플링 된 포인트가 가능한 한 조밀하기를 원합니다.

비슷한 질문이 있지만 주어진 포인트에서 샘플링하는 것이 아니라 포인트 생성에 관한 것입니다.
최소 인접 이웃 거리로 3D 공간에서 임의의 점 생성

각각의 거리가 최소 인 3 차원 임의의 점을 생성 하시겠습니까?

300 개의 임의의 3D 포인트가 있다고 가정 해 보겠습니다.

import numpy as np
n = 300
points = np.random.uniform(0, 10, size=(n, 3))

최대화하면서 m가장 가까운 이웃 거리가 최소 인 점 의 하위 집합을 얻는 가장 빠른 방법은 무엇입니까 ?r = 1m

답변

2 DavidEisenstat Jan 14 2021 at 08:00

아마도 효율적인 bicriteria 근사 체계가있을 수 있지만 정수 프로그래밍이 평균적으로 그렇게 빠른데 왜 귀찮게할까요?

import numpy as np

n = 300
points = np.random.uniform(0, 10, size=(n, 3))

from ortools.linear_solver import pywraplp

solver = pywraplp.Solver.CreateSolver("SCIP")
variables = [solver.BoolVar("x[{}]".format(i)) for i in range(n)]
solver.Maximize(sum(variables))
for j, q in enumerate(points):
    for i, p in enumerate(points[:j]):
        if np.linalg.norm(p - q) <= 1:
            solver.Add(variables[i] + variables[j] <= 1)
solver.EnableOutput()
solver.Solve()
print(len([i for (i, variable) in enumerate(variables) if variable.SolutionValue()]))

1 DanielF Jan 18 2021 at 16:16

이것은 최적의 하위 집합은 아니지만 KDTree거리 계산을 최적화하는 데 사용하여 시간이 오래 걸리지 않으면 서 가까이 있어야합니다 .

from scipy.spatial import KDTree
import numpy as np

def space_sample(n = 300, low = 0, high = 10, dist = 1):
    points = np.random.uniform(low, high, size=(n, 3))
    k = KDTree(points)
    pairs = np.array(list(k.query_pairs(dist)))
    
    def reduce_pairs(pairs, remove = []):  #iteratively remove the most connected node
        p = pairs[~np.isin(pairs, remove).any(1)]
        if p.size >0:
            count = np.bincount(p.flatten(), minlength = n)
            r = remove + [count.argmax()]
            return reduce_pairs(p, r)
        else:
            return remove
    
    return np.array([p for i, p in enumerate(points) if not(i in reduce_pairs(pairs))])

subset = space_sample()

가장 많이 연결된 노드를 반복적으로 제거하는 것은 최적 이 아니지만 (300 개 포인트 중 약 200 개를 유지) 최적에 가까운 가장 빠른 알고리즘 일 가능성이 높습니다 (단지 무작위로 제거하는 것이 더 빠릅니다). @njit reduce_pairs그 부분을 더 빠르게 만들 수 있습니다 (나중에 시간이 있으면 시도 할 것입니다).