Computational Geometry
Computational geometry - Tutorial 19.5.2021
Delaunay triangulation
- vertices: sites of the Voronoi diagram
- we have an edge whenver the two corresponding cells of the Voronoi diagram have a common boundary
Exercise 1
Draw the Delaunay triangulation of the point set from the drawing below.
Exercise 2
For $i=1, \dots, 100$, choose the coordinates of the points ${p_i} \in \mathbb{R}^2$ in such a way that the Delaunay triangulation of the set $\lbrace {p_1}, {p_2}, \dots, {p_{100}} \rbrace$ contains at least two points of degree $99$. The points should be in general position: no three points are collinear and no four points are concyclic. Carefully argue that your choice of points has the desired properties.
Exercise 3
Let $P$ be a set of points in a plane. Its shortest triangulation is such a triangulation that minimizes the sum of edge lengths. Prove that the shortest triangulation is not necessarily a Delaunay triangulation.
Exercise 4
Let $P = \lbrace {p_1}, {p_2}, \dots {p_n} \rbrace$ be a set of $n$ points in a plane. Assume the following general position: if $\lbrace {p_i}, {p_j} \rbrace \ne \lbrace {p_{i’}}, {p_{j’}} \rbrace$, ${p_i} \ne {p_j}$, ${p_{i’}} \ne {p_{j’}}$, then $d({p_i}, {p_j}) \ne d({p_{i’}}, {p_{j’}})$, where $d(\cdot,\cdot)$ is the Euclidean distance. The minimum distance ${d_{\min}}$ in $P$ is
\[d_{\min} = \min\{d(p_i, p_j) \mid p_i \ne p_j\}.\]We define the second smallest distance ${d_{2.!\min}}$ in $P$ as
\[d_{2.\!\min} = \min\left(\{d(p_i, p_j) \mid p_i \ne p_j \} \setminus \{d_{\min} \}\right).\]Describe an algorithm which computes the second smallest distance ${d_{2.!\min}}$ in $O(n \log n)$ time.
- Compute the Delaunay triangulation of $P$ ($O(n \log n)$)
- Find the edge ${p_i} {p_j}$ of minimal length ${d_{\min}}$ ($O(n)$)
- Compute the Delaunay triangulations of $P \setminus \lbrace {p_i} \rbrace$ and $P \setminus \lbrace {p_j} \rbrace$ ($O(n \log n)$)
- Find the shortest edge in these two triangulations, its length gives ${d_{2.!\min}}$ ($O(n)$)
Exercise 5
Let $P$ be a set of $n$ points in a plane. The Gabriel graph $G(P)$ for $P$ has vertex set $P$ and an edge between $p$ and $q$ if and only if the disk with diameter $pq$ does not contain any point of $P \setminus \lbrace p, q \rbrace$.
- Show that $G(P)$ is a subgraph of the Delaunay triangulation of $P$.
- Show that $pq$ is an edge of $G(P)$ if and only if the Voronoi faces of $p$ and $q$ have a common edge $e$ and the segment $\overline{pq}$ intersects $e$.
- Describe an algorithm which returns $G(P)$ in $O(n \log n)$ time.
- Show that at least $\Omega(n \log n)$ time is required to compute the Gabriel graph.
- If the disk with diameter $pq$ contains not point from $P \setminus \lbrace p, q \rbrace$, then we can enlarge it, keeping $p, q$ on the boundary, until it meets another point giving a Delaunay triangle, implying that $pq$ is a Delaunay edge.
- $\overline{pq}$ intersects $e$ if and only if the intersection (the midpont of $\overline{pq}$) is nearest to $p$ and $q$.
Exercise 6
Let $P$ be a set of $n$ points in a plane. Describe an algorithm for finding the smallest disk $D$ containing at least four points of $P$, with at least three of these points lying on the boundary of $D$. Your algorithm should run in $O(n \log n)$ time.
Hint: which Delaunay triangulations will be useful?