<p>The short answer is: no, there is no such lower bound.</p>

<p>Let $p$ be a positive integer.
Let $\epsilon = \frac{1}{p}$.</p>

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

CC BY-SA 3.0
2016-02-10T08:22:08.673Z
2016-02-10T08:22:08.673Z
Boson
<p>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.</p>

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

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

CC BY-SA 3.0
2016-02-09T22:32:48.373Z
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.
Boson
CC BY-SA 3.0
2016-02-09T22:59:23.087Z
$n=5$, put a point at each of the four corners, and one at $(\epsilon,\epsilon)$. $4$ triangles, minimal distance arbitrarily small...
Boson
CC BY-SA 3.0
2016-02-09T23:01:07.567Z
Under your setup, triangulating S will result in $\Omega(n)$ triangles for the point $(\epsilon, \epsilon)$.
NoviceMathematician
CC BY-SA 3.0
2016-02-09T23:14:06.240Z
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.
Boson
CC BY-SA 3.0
2016-02-09T23:39:22.007Z
Yes, you are correct. It holds for any arbitrary $n$, by making the point $(\epsilon, \epsilon)$ a part of exactly three triangles. Thanks.
NoviceMathematician
CC BY-SA 3.0
2016-02-10T04:00:05.450Z
I have updated the question details to impose the constraint on angles instead of the number of triangles.
NoviceMathematician
<lower-bounds><computational-geometry>
Lowerbound for the minimum distance between points in a "nice" triangulation
NoviceMathematician
# Lowerbound for the minimum distance between points in a "nice" triangulation

(Asked by: username_0 on 2016-02-09)

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?

**Tags:** lower-bounds, computational-geometry

> **Comments:**
> **username_1**: 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.  
> **username_1**: $n=5$, put a point at each of the four corners, and one at $(\epsilon,\epsilon)$. $4$ triangles, minimal distance arbitrarily small...  
> **username_0**: Under your setup, triangulating S will result in $\Omega(n)$ triangles for the point $(\epsilon, \epsilon)$.  
> **username_1**: 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.  
> **username_0**: Yes, you are correct. It holds for any arbitrary $n$, by making the point $(\epsilon, \epsilon)$ a part of exactly three triangles. Thanks.  
> **username_0**: I have updated the question details to impose the constraint on angles instead of the number of triangles.  

---

## 1 answers

### Answer by username_1 on 2016-02-10. Score: 1

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


---

