Create a sorted-map of coordinates
Yes, this is the right way to do it.

Many Clojure programs do not bother with creating empty maps. The absence of a value or nil behave like an empty map. For example (assoc nil :foo :bar) returns {:foo :bar}. You may be able to initialize to an empty sorted-map, and only assoc-in novelty as you need it ... depending on your logic.