Is it easy to say how exactly $T(n)$ is related to the number of torsion-free subgroups of $PSL_2(\mathbb{Z})$ of index $6n$?

Look at convex hull algorithms: en.wikipedia.org/wiki/Convex_hull_algorithms

Thanks for the reference Vidit --- that looks like a good paper to read. By the way, you're absolutely right that (1) is surmountable: if $f$ is the number of faces then $n = f/2 + 2 - 2g$. Maybe (2) is surmountable too, for fixed $g$ at least...

This paper on realizations of MacPhersonians apparently has a fatal flaw, and was later retracted by Biss.