0
$\begingroup$

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?

| cite | improve this question | |
$\endgroup$
  • $\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$ – NoviceMathematician 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$ – NoviceMathematician Feb 9 '16 at 23:39
1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$

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.