Scientific Visualization and Computer Graphics > CS > JBI > FWN > RUG


Here is a short summary of different orders and order types, and how they are called in different contexts. Consider `a` and `b` to be multi-component values from the same set, with `a_i` and `b_i` their `i`-th components, then we have:

  • Lexicographical order: `a<=b iff a_1<b_1 or (a_1=b_1 and (a_2<b_2 or ...))`. In a statistical context this is also called a conditional order or C-order. A lexicographical or conditional order is a specific case of a total order. Other total orders that have been tried for morphology on vectors include total orders based on space-filling curves or self-organizing networks.
  • Product order: `a<=b iff AA i(a_i<=b_i)`. In a statistical context this is known as a marginal or M-order. This kind of order is a partial order.
  • `h`-order: `a<=b iff h(a)<=h(b)` for some surjective mapping `h` that maps values into a complete lattice (typically a totally ordered set), also see Goutsias1995. When `h` maps to a totally ordered set this essentially corresponds to either a reduced (or R-)order, or a partial or P-order as used in a statistical context. Reduced ordering is typically based on a distance to some reference point, while P-ordering is based on grouping values according to some measure of "extremeness" (for example, points on the convex hull could be considered the most extreme). This kind of order is a preorder. Note: be sure not to confuse a P-order with the algebraic concept of a partial order, P-ordering actually induces a preorder. (This is why I prefer talking about "a P-order" or "P-ordering".)

Note that I try to use the word "order" to refer to the (algebraic) object and ordering for the action (of ordering things). However, in many cases the object or the procedure for ordering a set is also called an ordering.