  For every half-translation surface with marked points $(M,\Sigma)$, we
construct an associated tessellation $\Pi(M,\Sigma)$ of the Poincar\'e upper
half plane whose tiles have finitely many sides and area at most $\pi$. The
tessellation $\Pi(M,\Sigma)$ is equivariant with respect to the action of
$\mathrm{PSL}(2,\mathbb{R})$, and invariant with respect to (half-)translation
covering. In the case $(M,\Sigma)$ is the torus $\mathbb{C}/\mathbb{Z}^2$ with
a one marked point, $\Pi(\mathbb{C}/\mathbb{Z}^2,\{0\})$ coincides with the
iso-Delaunay tessellation introduced by Veech as both tessellations give the
Farey tessellation. As application, we obtain a bound on the volume of the
corresponding Teichm\"uller curve in the case $(M,\Sigma)$ is a Veech surface
(lattice surface). Under the assumption that $(M,\Sigma)$ satisfies the
topological Veech dichotomy, there is a natural graph $\mathcal{G}$ underlying
$\Pi(M,\Sigma)$ on which the Veech group $\Gamma$ acts by automorphisms. We
show that $\mathcal{G}$ has infinite diameter and is Gromov hyperbolic.
Furthermore, the quotient $\overline{\mathcal{G}}:=\mathcal{G}/\Gamma$ is a
finite graph if and only if $(M,\Sigma)$ is actually a Veech surface, in which
case we provide an algorithm to determine the graph $\overline{\mathcal{G}}$
explicitly. This algorithm also allows one to get a generating family and a
"coarse" fundamental domain of the Veech group $\Gamma$.
