Policies to Avoid Distance Computations - (2)

4. Double-Pivot Distance Constraint

이전장에서 다룬 pivot-pivot distance constraint에서는,

하나의 피벗만 사용한 'Ball partitioning'에서 사용 가능한 constraint였다.

Generalized hyper-plane에 적용하기 위해서는, 2개의 피벗을 사용해야한다.

피벗 두개를 사용하여 

 

만약 q와 o가 다른 subspace에 존재한다 가정해보자.

lower bound는 (d(q,p1) - d(q,p2))/2

 

 

5. Pivot Filtering

- object-pivot constraint의 확장으로, 더 많은 pivot을 사용한다.

- pruning을 위해 삼각부등식을 사용한다.

- 모든 object들과 pivot p 사이의 거리를 알고있다 가정한다.

- object o가 다음 조건을 하나라도 만족하면 가지치기를 할 수 있다.

•       d(p,o) < d(p,q) – r

•       d(p,o) > d(p,q) + r

 

위 그림은 일반적인 object-pivot constraint이다.

 

두 개의 pivot으로 필터링을 하게 되면 다음과 같은 결과가 나온다.

여기서 우리가 검사하면 되는 유일한 부분은, 

진한 파란색으로 색칠된 영역뿐이다.

즉 더 많은 피봇을 사용할 수록, 효율성이 증대된다.