1

Given a set of distinct points in two dimensions and a pair of coordinate axes, I can generate a sequence according to the following rule: point A comes before point B if its Y-coordinate is larger. If the two points have the same Y coordinate, the one with the larger X coordinate comes first.

A sequence created in this manner is unique for any set of distinct points. Furthermore, it is invariant under translations of the coordinate axes.

Is there a procedure I can follow to generate a unique sequence that is invariant under rotations of the coordinate axes? I suspect this is impossible, but what if the invariance requirement were relaxed, and sets of sequences equivalent under cyclic permutation were permitted?

Is there a procedure that generates sequences that are invariant (permitting cyclic permutations and reversals) under rotations, reflections, and translations?

If such a procedure exists, can it be generalized to higher dimensions?

Edit: Upon further thought, the following rule produces sequences that are invariant (permitting cyclic permutations) under rotations: "the point with the larger polar angle comes first; if two points have the same polar angle, the point further from the origin comes first."

Does this generalize to three or more dimensions? And is there any way to get a sequence that is 'almost' invariant (e.g. allowing for simple equivalence relations like cyclic permutation) under both rotations and translations?

Haycart
  • 11

1 Answers1

0

The invariance w.r. to linear rotations and linear symmetries forces a quasi-order such that the vectors with the same norm are equivalent; and for arbitrary two vectors with different norms, a vector with the larger norm comes before the vector with the smaller norm.

In dimension $\ > 1\ $ you get the same answer even when you consider only linear rotations.

(Linear means that the origin is mapped onto the origin).

The reason is that, say for dimension $\ > 1,\ $ every two points of the same norm can be swapped by a rotation.

Wlod AA
  • 2,124
  • Thanks for the response. I'm not sure I fully understand it, though. Are you saying that, given the requirement for both rotational and translational invariance, there is no way to create a unique total ordering? – Haycart Dec 21 '17 at 07:24
  • For instance, if you allow general arbitrary mirror reflections than no order nor quasi-order is possible but completely trivial quasi-order (meaningless). In my Answer I assume only linear rotations. Then in dim > 1 the points can be ordered only by their norm. (I will even remove symmetries for dim > 1). – Wlod AA Dec 21 '17 at 07:46