[Numpy-discussion] Robust Sorting of Points

[Daniele Nicolodi]

On 27/10/2013 19:42, Freddie Witherden wrote:
> 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.)

Do you mean that all you points are distributed around some fixed points
in your space?  In this case, it looks like what you are looking for is
categorization or clustering and not sorting.  Once you perform
clustering, you can simply define an arbitrary order in which report the
content of each cluster.  If this is not the case, the problem that
Nathaniel highlishts is still present.

Cheers,
Daniele