# Lowerbound for the minimum distance between points in a "nice" triangulation

Suppose we have a unit square $S$ that contains $n$ points. Assume we always have a point at each of the four corners. No we triangulate $S$ by adding non-intersecting segments between the points. That is, every face is a triangle.

Suppose that the resulting triangulation has the property that the smallest angle is greater than some constant $\phi$.

Given this, can we compute a lowerbound $f(n)$ on the minimum distance between the points?

• I must have missed something... Let $n = 3$, put a point at $(0,0)$, another at $(1,0)$ and the third one at $(\epsilon,\epsilon)$. We have a single triangle, and it trivially answers the question. Feb 9 '16 at 22:32
• $n=5$, put a point at each of the four corners, and one at $(\epsilon,\epsilon)$. $4$ triangles, minimal distance arbitrarily small... Feb 9 '16 at 22:59
• Under your setup, triangulating S will result in $\Omega(n)$ triangles for the point $(\epsilon, \epsilon)$. Feb 9 '16 at 23:01
• I exhibit an infinite collection of instances of your problem, for which $n = 5$ is constant, every point is part of at most $4$ triangles, and the minimum distance between two points is not bounded below. As a side note, I do not think that the constraint on the angles and on the number of triangles are equivalent. Feb 9 '16 at 23:14
• Yes, you are correct. It holds for any arbitrary $n$, by making the point $(\epsilon, \epsilon)$ a part of exactly three triangles. Thanks. Feb 9 '16 at 23:39

Let $p$ be a positive integer. Let $\epsilon = \frac{1}{p}$.
Put points at coordinates $(i \epsilon, j \epsilon)$ for $i,j \in \{ 0 \dots p \}$, and at coordinates $(i \epsilon + \frac{\epsilon}{2}, j \epsilon + \frac{\epsilon}{2})$ for $i,j \in \{ 1 \dots p \}$. You end up with $n = (p+1)^2 + p^2$ points, and a triangulation in which all triangles are both right and isosceles. So all angles are either $\frac{\pi}{2}$ or $\frac{\pi}{4}$, and the minimal distance between two points is $\frac{\epsilon}{\sqrt{2}}$.