I admit I didn't study it the OP's code in great detail. Now I see that it probably does an equivalent thing to what mine does: infer all transitive relations from the data and store them in an object that supports individual queries. The OP code infers the transitive relations in some ad-hoc way, storing in a hash; mine uses a graph module and stores the results in a graph. Of course, you can probably guess that I prefer the elegance of using the high-level abstraction of graph theory ;) (probably because I don't want to re-implement transitive closure logic) So perhaps my previous post should be interpreted as advice on computing the transitive closure using pre-existing hammers instead of an ad-hoc method.
As for efficiency of the compare() sub.. I doubt mine is insanely slow. At worst, the calls to $g->has_edge would cost a few hash lookups in the internals of Graph. If optimization really is a concern at such a low level, you're right -- nothing could be faster than a simple hash lookup. Of course, you could preemptively convert the whole graph's adjacency information into a HoH after doing the transitive closure. For only 50 items, it should be no problem.
Here is an interesting tradeoff that the OP might be willing to consider (described in the language of graphs, but could be also be coded using the HoH of adjacencies). At the moment, both my code and the OP's essentially precompute answers to all possible queries, which on some level might feel inelegant. A more interesting tradeoff is to put all the relations into the graph, but don't compute the transitive closure right away. Instead, whenever a query comes, do a reachability search in the graph (say, breadth-first search from one of the points). For every path that you happen to inspect at along the way, add in all the edges which are inferred by the transitivity property. The next time you query the graph, there will be new "shortcuts" that you can exploit. Eventually, with enough queries, the graph slowly approaches the transitive closure of the original graph.