Recently, due to the help I had with another question, I was able to find a Diophantine equation of degree in four variables which is the condition to be able to construct a "rational" dodecahedron. It was a lot of work, and led to some interesting questions and results. But it got me thinking, is there a way to "cheat" at this?

What I mean here is: Say you have some points that you know satisfy a certain condition, but the algebra to get to a single equation for them is intractable. Is there a way, given those points that you already know, to construct a Diophantine equation for them? I don't just want any random Diophantine equation, I want one that is elegant enough that it is probably the "right" one. You could easily take a product over all terms $(x-x_1)^2+(y-y_1)^2+...$ so that it trivially goes through the given points.

Is it tractable, for example, to go through all possible homogeneous Diophantine equations of small (up to 5, say) degree, such that all terms have a coefficient of 0, 1, or -1, and check if some given points are on that curve? I imagine modular constraints would reduce the number of possibilities, and potentially even turn it into a linear algebra problem.

Has this been done? Can it feasibly be done?