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?

  • $\begingroup$ 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. $\endgroup$
    – Boson
    Feb 9 '16 at 22:32
  • $\begingroup$ $n=5$, put a point at each of the four corners, and one at $(\epsilon,\epsilon)$. $4$ triangles, minimal distance arbitrarily small... $\endgroup$
    – Boson
    Feb 9 '16 at 22:59
  • $\begingroup$ Under your setup, triangulating S will result in $\Omega(n)$ triangles for the point $(\epsilon, \epsilon)$. $\endgroup$ Feb 9 '16 at 23:01
  • $\begingroup$ 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. $\endgroup$
    – Boson
    Feb 9 '16 at 23:14
  • $\begingroup$ Yes, you are correct. It holds for any arbitrary $n$, by making the point $(\epsilon, \epsilon)$ a part of exactly three triangles. Thanks. $\endgroup$ Feb 9 '16 at 23:39

The short answer is: no, there is no such lower bound.

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}}$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.