Talk:Bowyer–Watson algorithm

Mathematics Start‑class Low‑priority

	Mathematics portal This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics
Start	This article has been rated as Start-class on Wikipedia's content assessment scale.
Low	This article has been rated as Low-priority on the project's priority scale.

Incorrect Result?

The Voronoi tessellation of the vertices in the example is not dual to the result shown. Correspondingly, the result shown is not a correct Delaunay triangulation: The circumcircle of the middle triangle (of the final three) contains the rightmost vertex. The correct triangulation would not connect the topmost with the bottom right vertex, but the bottom left with the rightmost. That would also be dual to the correct Voronoi tessellation. I think the problem lies with the incremental process. The Delaunay triangulation in the step before inserting the rightmost vertex is correct. Then, inserting that vertex, the correct triangle is split up, but in combination with its neighbouring triangles, we generate this wrong triangulation. Perhaps there is a check needed after the insert, and in case of violation, a flip of the edge within a combination of four vertices? As far as I can tell from a glance at the papers, this is also not addressed in there? — Preceding unsigned comment added by 132.180.194.68 (talk) 15:01, 5 February 2020 (UTC)[reply]

Extra Requirements for Super Triangle

While coding up an implementation of this algorithm, I (well, a coworker and I) discovered that the super triangle described here is insufficient in some cases. It is not enough for the super triangle to contain all points. An example is discussed in this StackExchange post: https://math.stackexchange.com/questions/4001660/bowyer-watson-algorithm-for-delaunay-triangulation-fails-when-three-vertices-ap.

I am not yet sure what the necessary condition is for the super triangle. Containing all circumcircles should do the trick, but calculating these is annoying. I'd like to dig through the original literature and see what the authors say about this.

JackCasey067 (talk) 19:50, 3 May 2023 (UTC)[reply]