consider a finite set $\mathcal{P}(x,y)=\lbrace(x_1,y_1),\dots,\,(x_n,y_n)\rbrace$ of points in the Euclidean plane and let $\mathrm{DT}(x,y)$ be the Delaunay triangulation of $\mathcal{P}(x,y)$
Define the cost $|\mathrm{DT}(x,y)|$ of the Delaunay triangulation to be $\sum\limits_{e_{ij}\in \mathrm{DT}}|y_i-y_j|$, i.e. the sum over the absolute difference between the y-coordinates of two points that are adjacent to the same edge in the triangulation.
If we scale the x-coordinates by $\alpha$ then the edge sets of $\mathrm{DT}(x,y)$ may be different from the edge set of $\mathrm{DT}(\alpha x,y)$ and thus their costs may also be different, leading to the
Question:
how can $\alpha_0: |\mathrm{DT}(\alpha_0 x,\,y)|= \min_\alpha|\mathrm{DT}(\alpha x,\,y)|\lt|\mathrm{DT}((\alpha_0+\varepsilon)\cdot x,\,y)|\ \forall \varepsilon,\alpha\gt 0$ be calculated efficiently?
The question may also be extended to asking for the maximal range $[\alpha_0,\alpha_1]$ outside of which the cost doesn't change but replacing either $\alpha_0$ with $\alpha_0+\varepsilon$ or $\alpha_1$ with $\alpha_1-\varepsilon$ incurs a change of cost.
Edit
I restate the problem to:
determine the parameters of an affine transformation of a finite point set in the Euclidean plane that renders the minimal angle in the Delaunay triangulation of the transformed point set maximal.
