Very nice visualisation!
On two occassions:
Sort[..., Norm[#1, 1] > Norm[#2, 1] &]
Could be sped up by:
SortBy[..., Norm[#, 1]&]
25% improved on my laptop...
In addition:
DeleteDuplicatesBy[SortBy[newpts, #[[2]] &], First]
Speeds it up another 10x times, 13x total or so...
Moral of the story: if you compare two the same things in Sort, DeleteDuplicates, Gather et cetera use SortBy, DeleteDuplicatesBy, GatherBy, et cetera. those are a lot faster because it evaluates the criterion only once on all the elements, sorts those (very fast) and reorders the original. While e.g Sort compares each PAIR again and again, reevaluating the criterion. Because in theory you could have an 'asymmetrical' comparison: e.g. SortBy[list,First[#1]>Last[#2]&] (quite uncommon but it happens sometimes!).