in reply to
Storing simple Value Pairs
What's the best way to store/organize them in perl?
That depends upon how you want to access the data. Looks to me like you pretty much understand the options. The 2-D AoA is a logical choice if you just need a sequential list of coordinates.
The AoH is also commonly done (your option 1). "Wasteful" or not is a subjective thing. For something simple this can take less storage than you might think. This is similar to a C array of struct.
In your option (2), use HoA (hash of array) instead of a simple hash if you want to represent more than one point with the same X value. I would make all of the hash entries pointers to array (not do some as simple values if only one) just to make things more "regular" and eliminate special case.