[Numpy-discussion] Robust Sorting of Points

Freddie Witherden freddie at witherden.org
Sun Oct 27 14:42:37 EDT 2013

On 27/10/13 18:35, Nathaniel Smith wrote:
> 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...?

Not exactly; in your case the distance between a and b is of the order
epislon.  However, my points are "all unique and separated by a
reasonable distance."  This requires at least one of the components of
any two points to differ in all instances, permitting an ordering to be
defined.  (Where if epislon ~ 1e-12 the minimum instance between any two
points is of order ~ 1e-6.)

Regards, Freddie.

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 836 bytes
Desc: OpenPGP digital signature
URL: <http://mail.python.org/pipermail/numpy-discussion/attachments/20131027/2da72e05/attachment.sig>

More information about the NumPy-Discussion mailing list