lexicographic order

[Supercharged]

Hi all

Can anyone explain to me in layman’s terms the meaning of lexicographic order, the context is that of a series of vertices in Euclidean Space

I have searched the web but I am really struggling with the concept

Any help really appreciated

Thanks

Talyrond

[anna69]

I'm guessing.... since lexicography is to do with dictionaries, lexicographic order might be the order in which a dictionary would list a bunch of vertices.

So (0,0,0) would be the very first followed by (0,0,1).

(0,0,5) would preceed (0,1,0) because the second 0 in 0,0,5 is "above" the 1 in 0,1,0 in dictionarial thinking.

But as I say, I'm guessing!

HTH?

EDIT: I stuck bunch of x,y,z's into a column in Excel, in a random order. When I sorted the vertices 1,0,1; 0,0,5; 0,1,1; 0,0,4 & 0,1,0 it put them as follows: 0,0,4; 0,0,5; 0,1,0; 0,1,1; 1,0,1 which bears out what I said.

[Supercharged]

Thanks anna69 for your reply, I think you are correct in your assumption. I am now trying to figure out if this order has made the vertices order more sequential with regards to nearest neighbour. Could this process be a pre operation to speed up a fully-fledged nearest neighbour search?

[anna69]

Re nearest neighbours...

If you had say 0,0,1; 0,1,0 and 0,0,1000000000 they would sort as 0,0,1; 0,0,1000000000; then 0,1,0 according to my reckoning which separates the 2 nearby ones (0,0,1 & 0,1,0) with one very far away and so wouldn't seem to help!

[Supercharged]

Yep, you’re dead right, just cant see what use it has!

[sql_lall]

Yeah, lexicographic ordering is commonly associated with strings, and it refers to ordering words as you would expect them to be ordered...

first letter, then second, then third...

so, yeah, if you replace 'string' = collection of characters, with 'vector' = collection of numbers, you'd do the same thing.

This also means, i think. that if you have (0, 1, 5) and (0, 1), and had to sort them, then (0, 1) would come first. Cos, "fig" comes before "fight" in the dictionary.

[Supercharged]

Thanks sql_lall, it's starting to make sense now!

Cheers All