Was there some prior idea that inspired both Fermat & Descartes to invent coordinates? It seems incredible to me that both Descartes & Fermat could have both simultaneously discovered such a novel & significant idea, without there being some single prior idea that they both could have taken inspiration from. Has there been any research done on this, or can someone expliciate the histrorical record further?
Wikipedia does state that Nicole Oresme in the 14C made constructions similar to coordinates. This is well before either Descartes or Fermat. It doesn't state whether they were influenced by him.
Alternatively, could they have been influenced by developments in Cartography or Map-making?
 A: To complement Henning Makholm's fine answer, I would add that it is not entirely accurate to say that "The improved notation had been in development for at least a couple of centuries, with algebraists gradually freeing themselves from the classical/medieval tradition of describing everything in prose." Here the key name is Vieta.  His work introduced the idea of symbolic mathematics in a systematic way, and constituted the transition to the modern period as far as symbolism is concerned. Both Fermat and Descartes relied on this.
A: They didn't invent coordinates as such -- a coordinate system was used by Ptolemy in his Geography more than 1000 years earlier.
The major novelty in the work of Descartes and his contemporaries was not the use of coordinates to describe a single point, but the idea that a single algebraic relation between the two coordinates can describe an entire family of points -- i.e., a curve.
This idea must have been "in the air" at the time, and the final ingredient of it that had just arrived seems to have been improvements in algebraic notation, with letters standing for known and unknown quantities alike, which made manipulations of equations, formulas and recipes for calculation easy enough to be useful for analyzing geometric situations. Only with good notation in place did it become natural to think of an algebraic relation as a "thing" among other similar things that could be an "object of thought" rather than just some particular canned sequence of actions.
The improved notation had been in development for at least a couple of centuries, with algebraists gradually freeing themselves from the classical/medieval tradition of describing everything in prose, figuring out the proper laws for manipulating different powers of the unknown, and inventing convenient notation to go with it. Descartes himself was among the first to use recognizably modern algebraic notation (and is credited with the idea of letters from the beginning of the alphabet (a, b, c, ...) for constants and letters from the end of the alphabet (x, y, z, ...) for unknowns).
