<p>Bowyer's version looks like it's expressed in terms of the vertices of a Voronoi diagram. Voronoi diagrams and Delaunay triangulations are &quot;dual&quot; to each other, meaning that each vertex of the Voronoi diagram corresponds to one triangle of the Delaunay triangulation. In fact, the Voronoi vertex is at the circumcenter of the corresponding Delaunay triangle.</p>
<p>So, when Bowyer speaks of removing any &quot;vertex that is nearer to the new point than to its forming points&quot;, that's the same thing as removing triangles (simplices) that have the new point within their circumcircle (circumsphere).</p>
<p>In both articles, the process of finding new vertices/simplices is, uhh, not exceptionally cleary explained. But if you squint a bit, they're both talking about filling in the &quot;hole&quot; created by deleting the old vertices/simplices, by combining the new point with each of the edges around the &quot;hole&quot;.</p>

CC BY-SA 4.0
2022-03-29T08:20:32.267Z
Thanks for the answer! Does it mean that they are equivalent in the sense of their general idea instead of the detailed algorithm?
8cold8hot
CC BY-SA 4.0
2022-03-29T17:02:11.523Z
I would say that they are talking about the same idea using different language and terminology.
Nathan Reed
CC BY-SA 4.0
2022-03-28T00:32:55.643Z
2022-03-28T00:32:55.643Z
Nathan Reed
<p>Bowyer–Watson algorithm might be the most famous method for computing the Delaunay triangulation of a finite set of points in any number of dimensions. Its <a href="https://en.wikipedia.org/wiki/Bowyer%E2%80%93Watson_algorithm" rel="nofollow noreferrer">Wikipedia</a> page and most textbooks on unstructured meshing <a href="https://en.wikipedia.org/wiki/Bowyer%E2%80%93Watson_algorithm" rel="nofollow noreferrer">1</a> introduced it as the same way in the original article of Watson's <a href="https://i.sstatic.net/p2mxN.png" rel="nofollow noreferrer">2</a>. However, when I looked into Bowyer's original article <a href="https://i.sstatic.net/Oymws.png" rel="nofollow noreferrer">3</a>, it seems to me his version is different from Watson's version. Are they really equivalent? If so, how can they be converted into each other?</p>
<p>Bowyer's version:</p>
<p><a href="https://i.sstatic.net/p2mxN.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/p2mxN.png" alt="enter image description here" /></a>
<a href="https://i.sstatic.net/Oymws.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/Oymws.png" alt="enter image description here" /></a>
<a href="https://i.sstatic.net/SThvv.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/SThvv.png" alt="enter image description here" /></a></p>
<p>Watson's version:</p>
<p><a href="https://i.sstatic.net/xpZkd.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/xpZkd.png" alt="enter image description here" /></a>
<a href="https://i.sstatic.net/ZVh97.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/ZVh97.png" alt="enter image description here" /></a></p>
<p><a href="https://en.wikipedia.org/wiki/Bowyer%E2%80%93Watson_algorithm" rel="nofollow noreferrer">1</a> Farrashkhalvat, M., and J. P. Miles. Basic Structured Grid Generation: With an introduction to unstructured grid generation. Elsevier, 2003.</p>
<p><a href="https://i.sstatic.net/p2mxN.png" rel="nofollow noreferrer">2</a> Watson, David F. (1981). &quot;Computing the n-dimensional Delaunay tessellation with application to Voronoi polytopes&quot;. Comput. J. 24 (2): 167–172. doi:10.1093/comjnl/24.2.167</p>
<p><a href="https://i.sstatic.net/Oymws.png" rel="nofollow noreferrer">3</a> Bowyer, Adrian (1981). &quot;Computing Dirichlet tessellations&quot;. Comput. J. 24 (2): 162–166. doi:10.1093/comjnl/24.2.162</p>

<computational-geometry><mesh><triangulation>
Why the Bowyer's version and Watson's version of computing the Delaunay tessellation are equivalent?
8cold8hot
# Why the Bowyer's version and Watson's version of computing the Delaunay tessellation are equivalent?

(Asked by: username_0 on 2022-03-26)

Bowyer–Watson algorithm might be the most famous method for computing the Delaunay triangulation of a finite set of points in any number of dimensions. Its [Wikipedia](https://en.wikipedia.org/wiki/Bowyer%E2%80%93Watson_algorithm) page and most textbooks on unstructured meshing [1](https://en.wikipedia.org/wiki/Bowyer%E2%80%93Watson_algorithm) introduced it as the same way in the original article of Watson's [2](https://i.sstatic.net/p2mxN.png). However, when I looked into Bowyer's original article [3](https://i.sstatic.net/Oymws.png), it seems to me his version is different from Watson's version. Are they really equivalent? If so, how can they be converted into each other?

Bowyer's version:

[![enter image description here](https://i.sstatic.net/p2mxN.png)](https://i.sstatic.net/p2mxN.png)
[![enter image description here](https://i.sstatic.net/Oymws.png)](https://i.sstatic.net/Oymws.png)
[![enter image description here](https://i.sstatic.net/SThvv.png)](https://i.sstatic.net/SThvv.png)

Watson's version:

[![enter image description here](https://i.sstatic.net/xpZkd.png)](https://i.sstatic.net/xpZkd.png)
[![enter image description here](https://i.sstatic.net/ZVh97.png)](https://i.sstatic.net/ZVh97.png)

[1](https://en.wikipedia.org/wiki/Bowyer%E2%80%93Watson_algorithm) Farrashkhalvat, M., and J. P. Miles. Basic Structured Grid Generation: With an introduction to unstructured grid generation. Elsevier, 2003.

[2](https://i.sstatic.net/p2mxN.png) Watson, David F. (1981). "Computing the n-dimensional Delaunay tessellation with application to Voronoi polytopes". Comput. J. 24 (2): 167–172. doi:10.1093/comjnl/24.2.167

[3](https://i.sstatic.net/Oymws.png) Bowyer, Adrian (1981). "Computing Dirichlet tessellations". Comput. J. 24 (2): 162–166. doi:10.1093/comjnl/24.2.162

**Tags:** computational-geometry, mesh, triangulation


---

## 1 answers

### Answer by username_1 on 2022-03-28. Score: 1

Bowyer's version looks like it's expressed in terms of the vertices of a Voronoi diagram. Voronoi diagrams and Delaunay triangulations are "dual" to each other, meaning that each vertex of the Voronoi diagram corresponds to one triangle of the Delaunay triangulation. In fact, the Voronoi vertex is at the circumcenter of the corresponding Delaunay triangle.

So, when Bowyer speaks of removing any "vertex that is nearer to the new point than to its forming points", that's the same thing as removing triangles (simplices) that have the new point within their circumcircle (circumsphere).

In both articles, the process of finding new vertices/simplices is, uhh, not exceptionally cleary explained. But if you squint a bit, they're both talking about filling in the "hole" created by deleting the old vertices/simplices, by combining the new point with each of the edges around the "hole".

> **Comments:**
> **username_0**: Thanks for the answer! Does it mean that they are equivalent in the sense of their general idea instead of the detailed algorithm?  
> **username_1**: I would say that they are talking about the same idea using different language and terminology.  

---

