What's the best way to store/organize them in perl?
in reply to Storing simple Value Pairs
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.