[Numpy-discussion] Robust Sorting of Points

Nathaniel Smith njs at pobox.com
Sun Oct 27 14:35:07 EDT 2013

On Sun, Oct 27, 2013 at 6:28 PM, Freddie Witherden
<freddie at witherden.org> wrote:
> Hi all,
> This is a question which has been bugging me for a while.  I have an (N,
> 3) array where N ~ 16 of points.  These points are all unique and
> separated by a reasonable distance.
> I wish to sort these points into a canonical order in a fashion which is
> robust against small perturbations.  In other words changing any
> component of any of the points by an epsilon ~ 1e-12 should not affect
> the resulting sorted order.

I don't understand how this is possible even in principle.

Say your points are

 a = [0, 0, 0]
 b = [0, 0, 1e-12]

According to your criterion, either a or b should go first -- I don't
know which. Let's say our canonical ordering decides that a goes
first. But if you perturb both of them, then you have

 a = [0, 0, 1e-12]
 b = [0, 0, 0]

And now your requirement says that a still has to go first. But if a
goes first this time, then b had to go first the last time, by
symmetry. Thus your criterion is self-contradictory...?


More information about the NumPy-Discussion mailing list