Wrong result when removed a point from the nearest pairs iteratively

[salihmarangoz]

Instead of merging, removing single points results in the wrong solution. The test image looks like this:

When I merge with this method:

fp = FastPair()
fp.build(points)

for i in range(int(len(fp) * 0.8)): # remove 80 percent of points
    dist, (a, b) = fp.closest_pair()

    c = (a[0]/2+b[0]/2, a[1]/2+b[1]/2)
    fp -= b
    fp -= a
    fp += c
    
for p in fp:
    plt.plot(p[0], p[1], "b.")

I get this result:

But if I remove a point from the closest pairs iteratively like this:

fp = FastPair()
fp.build(points)

for i in range(int(len(fp) * 0.8)):  # remove 80 percent of points
    dist, (a, b) = fp.closest_pair()
    fp -= a

for p in fp:
    plt.plot(p[0], p[1], "b.")

I get this output:

Do you have any ideas why this is happening? Input image and ipynb can be found here:
fastpair_test.zip

[carsonfarmer]

Hi sorry for the delayed response. This is an unexpected (but interesting) use-case of fast-pair! Is it possible that, without computing the mean of the two closest points, this is in fact the outcome when you remove the closest pairs? Alternatively, what happens if you remove both a and b, and then re-insert b in the iterative case?

[salihmarangoz]

When I remove a and b and then re-insert b, it works:

The code:

fp = FastPair()
fp.build(points)

for i in range(int(len(fp) * 0.8)):  # remove 80 percent of points
    dist, (a, b) = fp.closest_pair()
    fp -= a
    fp -= b
    fp += b

for p in fp:
    plt.plot(p[0], p[1], "b.")

You can also try it with the notebook I shared it is pretty short. I tested this with the latest commit of this repository.

But the problem is; the algorithm should work without removing b and re-inserting b. Looks like there is a problem that may cause instability in other problems as well. I also checked the code but couldn't find it easily.

[salihmarangoz]

Instead of removing and re-adding b, this also produces the same result:

fp._update_point(b, b)

I hope this helps.