[Numpy-discussion] Robust Sorting of Points
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.)
-------------- next part --------------
A non-text attachment was scrubbed...
Size: 836 bytes
Desc: OpenPGP digital signature
More information about the NumPy-Discussion