Neighbors and Regions

Distance without Square Roots

Nearest-neighbor ordering does not need square-root values. Squared distance keeps every displayed value as an exact integer.

highlighted = computed this step

Distance without square roots

For query (1, 1), the surface computes d^2=(delta x)^2+(delta y)^2.

d2=(Δx)2+(Δy)2d^2=(\Delta x)^2+(\Delta y)^2
Squared distancesThe table shows integer squared distances to the query.Squared distancesquery=(1,1), k=3i(x,y)classd^20(0,0)A21(2,0)A22(0,2)A23(3,3)B84(3,1)B45(1,3)B4distances use d^2 only

Why squared distance is enough

Ordering by d^2 gives the same neighbor order as distance while staying in exact integer arithmetic.

order by d2\text{order by }d^2
Squared distancesThe table shows integer squared distances to the query.Squared distancesquery=(1,1), k=3i(x,y)classd^20(0,0)A21(2,0)A22(0,2)A23(3,3)B84(3,1)B45(1,3)B4distances use d^2 only

Summary

The squared distances are 2, 2, 2, 8, 4, and 4. No square-root value is rendered.

d2=[2,2,2,8,4,4]d^2=[2,2,2,8,4,4]
Squared distancesThe table shows integer squared distances to the query.Squared distancesquery=(1,1), k=3i(x,y)classd^20(0,0)A21(2,0)A22(0,2)A23(3,3)B84(3,1)B45(1,3)B4distances use d^2 only