Talk:Delaunay triangulation

Additional Algorithm

I cannot add an algorithm to this page, because I'm the a inventor (discoverer?) of the algorithm.

The algorithm is highly parallelizable and Self stabilizing.

The 2-dimensional version is covered in this paper.

The N-dimensional version is proven correct in this document.

The algorithm relies on the property that if the graph is connected and is "locally delaunay", then it is the delaunay triangulation. By "locally delaunay", I mean that a node's edges are the same as in a delaunay triangulation of a subgraph consisting of (1) the node, (2) its neighbors, and (3) it's neighbor's neighbors.

Mdnahas (talk) 00:41, 5 January 2022 (UTC)

Notation

User:Fgnievinski (F), can you please revert your unhelpful Addition of Notation Everywhere (ANE) to this article on Delaunay Triangulations (DT)? The ANE of F to DT is making it Unreadable (U) to anyone who might care to read it. It is unconstructive. It is a bad idea. It fails WP:TECHNICAL. Notation can be a helpful thing, to clearly convey concepts that are overly verbose. But when you add unnecessary initialisms and replace text by them, or add notations to sentences merely for the sake of adding notation rather than because they clarify anything in the sentence, you are making the encyclopedia worse. Stop it. —David Eppstein (talk) 05:17, 9 October 2023 (UTC)

It was a slight change of focus, from the set to the points; it was:

... for a given set P of discrete points in a general position is a triangulation DT(P) such that no point in P is inside...

now, it is:

... for a given set {pᵢ} of discrete points pᵢ in general position is a triangulation such that no point pᵢ is inside...

The notation for the point set was opaque, now it's clearer; plus, the additional level of indirection was unnecessary ("no point in P" vs. "no point pᵢ"). I also found the use of boldface distracting, it's unusual as per Set (mathematics)#Notation. As for the operator name, DT was already present in older versions of the article. fgnievinski (talk) 00:47, 10 October 2023 (UTC)

Confusing diagrams

It seems that the first 3 diagrams have a point outside the top of the frame. The circumcircle is drawn, but the triangulation does not include it. The red lines for the Voronoi are shown, but they are solid, and obviously skewed to converge on an external point, not dotted and heading for infinity. A novice might not notice, but another might be confused.

--Mikhailfranco (talk) 14:51, 21 February 2024 (UTC)

The circumcenter of an obtuse triangle lies outside the triangle. —Tamfang (talk) 02:30, 31 March 2024 (UTC)

Yes, you are right (sorry, the diagram confused me).

All the Delaunay Triangulation is shown within the diagram.

To clarify my point: there is a center of a circumcircle outside the bounds of the diagram. So there is a point in the Voronoi that is not shown in the following two diagrams. The first caption is wrong: 'The Delaunay triangulation with all the circumcircles and their centers' - one of the centers is not visible. The second has one Voronoi vertex and part of the Voronoi cell clipped by the edge of the diagram. Mikhailfranco (talk) 08:20, 5 April 2024 (UTC)

Comprehensibility

In the interests of making the introduction more helpful to people who could understand the concept but don't know lots of jargon, I think it should begin along the lines

A Delaunay triangulation is a concept in mathematics and computational geometry. A triangulation is [self-contained jargon-free definition]; a Delaunay triangulation chooses the triangles such that [stuff about circumcircles and maximising the smallest angle]. This is useful because [situation where long thin triangles are a nuisance].

Noting that here rather than just doing it, because first I have to disentangle what the point-set triangulation article's introduction is saying. (I think it's saying something rather straightforward, but unfortunately it's not saying it straightforwardly. I'm one of those readers who has to double-check what a convex hull is, for example.) Musiconeologist (talk) 23:30, 1 April 2024 (UTC)

The first sentence should very briefly set the context, and then give some idea what the topic is about within that context. Your proposed first sentence is all bun and no burger. It sets the context only, and then fails to say anything about what the article is actually about within that context. If someone has seen the title word "triangulation", they might already guess that it is a topic in mathematics and computational geometry. Your proposed first sentence would leave them completely uninformed beyond that guess. It does not need to be and should not be a complete precise mathematical definition of the topic, but it should provide at least some information rather than being content-free. Better might be something like:

In computational geometry, the Delaunay triangulation of points in the plane subdivides the convex hull of the points into triangles whose circumcircles do not contain any of the given points.

Later on in the article can more carefully state the missing parts of this gloss, that the point set should be finite or locally finite, the triangles should have the points as vertices and meet edge-to-edge, etc. —David Eppstein (talk) 23:45, 1 April 2024 (UTC)

@David Eppstein You're right, I'm still including too much. And I absolutely don't want a formal definition as the opening! My main concern is to remove as much jargon as possible from there, so a non-mathematician with some interest in maths can see what the concept is and whether to read further.

It frustrates me that so many mathematical articles seem unable to introduce simple concepts in a simple way. Musiconeologist (talk) 00:32, 2 April 2024 (UTC)

Ok, but in trying to remove jargon you should not remove all the content and leave only "it's a mathematical thing, don't try to understand". —David Eppstein (talk) 01:12, 2 April 2024 (UTC)

@David Eppstein Of course! That's exactly my point. Replace the jargon by its meaning, without any dumbing-down. Then maybe introduce the jargon to someone after they've understood the concept, so they know exactly what a term is labelling and have the right idea of its meaning right from the start, and so they only have to focus on one thing at once.

(FWIW, I had a father who explained the shape of the teeth of involute gears to me when I was 8: he reckoned that any subject could be explained to an 8-year-old by someone who understood it well enough. I think I've inherited a similar outlook.) Musiconeologist (talk) 02:31, 2 April 2024 (UTC)

The lead can definitely be clearer. Taking out explicit symbols seems fine. Taking out extra abbreviations seems fine. The notion of a "degenerate" triangle made from colinear points should perhaps be better explained inline. The term "general position" should be cut from the introductory sentence; for one thing, the following sentence that Delaunay triangulations involving 4 concyclic points are non-unique implies that this condition is not required for the concept to be meaningful, but more importantly, it's unnecessary jargon which is fine to discuss in the following sections (ideally with a quick lay-accessible definition inline at the point of use). –jacobolus (t) 01:27, 2 April 2024 (UTC)

@Jacobolus You replied while I was doing the edit—just of the very opening so far. I added a footnote informally clarifying convex hull. Maybe circumcircle should have one too, since the concept of the triangulation seems simple enough to be understood by people who learnt the term in high school geometry and have subsequently forgotten it.

Re the symbols, I'm a big fan of not introducing them until they need to be used, which quite often turns out to be not at all. Musiconeologist (talk) 02:03, 2 April 2024 (UTC)

Clarifying footnotes are not that helpful for this. The people who most need the clarification are unlikely to look at the note. I would just leave "convex hull" out of the first sentence. –jacobolus (t) 02:38, 2 April 2024 (UTC)

@Jacobolus Hmm, good point. It's tempting to use a phrase like is a network of triangles connecting them, but I feel that maybe goes a bit too far and starts losing content (as well as misusing network). Musiconeologist (talk) 02:55, 2 April 2024 (UTC)

Though it possibly loses less content than the current version, in fact. But uses the words rather too loosely. Musiconeologist (talk) 03:04, 2 April 2024 (UTC)

Incidentally I am also not a fan of using symbols in the lead when they can be avoided. If it's just notation for later in the article, introduce it later. I think your changes removing them from the lead paragraph are an improvement. —David Eppstein (talk) 04:32, 2 April 2024 (UTC)

@David Eppstein Thanks! I think sometimes it gets added through habit, because people are so used to naming the things they're about to use in a proof or calculation that it becomes automatic. It can mean the reader is unnecessarily keeping track of two things at once.

Sometimes symbols get introduced that are never even used. Musiconeologist (talk) 05:06, 2 April 2024 (UTC)

Ambiguous sentence

I would like to rewrite

• This maximizes the minimum of all the angles of the triangles in the triangulation

as something like

• This maximises the smallest angle found in the triangulation between two sides of the same triangle

so it can't mean

• For any of the triangles, this maximises the size of its smallest angle.

Have I got that right? Musiconeologist (talk) 00:01, 2 April 2024 (UTC)

Suggestion: "between two sides of the same triangle" is equivalent to "at a vertex", since the angle between edges not of the same triangle must be bigger than within a triangle. Which is more intuitive? —Tamfang (talk) 03:22, 2 April 2024 (UTC)

@Tamfang Roughly equally intuitive, but switching attention to a new detail (the vertices)? "At a vertex" is a more comfortable phrase . . . But I realised the ambiguity still refuses to go away. Namely whether the maximum is for the set of angles at a given vertex, or for the union of all such sets. Musiconeologist (talk) 05:24, 2 April 2024 (UTC)

@Musiconeologist Have you tried searching for lay-accessible sources about Delaunay triangulation? This is a popular enough topic that I am guessing you can find some simple explanations that expert mathematicians and/or technical writers spent a lot of effort on clarifying already, and possibly even tested on an intended non-technical audience. –jacobolus (t) 03:51, 2 April 2024 (UTC)

@Jacobolus I haven't! I simply got involved earlier this evening, because a random article linked to this one and I was dismayed to see a mass of symbols and unexplained terms instead of a straightforward description that would tell me what it was. Then I saw User:David Eppstein had already objected to the unnecessary notation, so I removed that and discovered the introduction was now comprehensible enough for me start simplifying the language. That's a good suggestion. Musiconeologist (talk) 04:25, 2 April 2024 (UTC)

Four points on a circle

At first sight, the logic here needn't be true:

For four or more points on the same circle . . . the Delaunay triangulation is not unique: each of the two possible triangulations that split the quadrangle into two triangles satisfies the "Delaunay condition"

The logic assumes that the points are connected as a quadrilateral, and that the quadrilateral has no points inside it and is therefore inevitably divided into only two triangles. But we might have four widely-spaced points on a circle, with chains of multiple edges joining them. Is it known that there's no unique Delaunay triangulation in that situation? Not guaranteed to be unique seems more likely. Musiconeologist (talk) 20:39, 2 April 2024 (UTC)

As long as you have a circle with more than three sites, empty of other sites, the Delaunay triangulation is non-unique. All triangulations of the sites on the circle can be part of a triangulation of the whole input that meets the usual definition of a DT (each triangle has an empty circumcenter). The number of triangulations of the sites on the circle is a Catalan number: 2 for four sites, 5 for five sites, 14 for six sites, etc. It is always more than one, for more than three sites. —David Eppstein (talk) 20:49, 2 April 2024 (UTC)

We should take "two" out of "each of the two" if we're leading with "four or more" though. –jacobolus (t) 22:19, 2 April 2024 (UTC)

One of the claims contains a poor reference.

The reference provided to show that "The Delaunay triangulation contains ${\textstyle O{\bigl (}n^{\lceil d/2\rceil }{\bigr )}}$ simplices." does not give a proof of that. The author claims that another author proved it, but they just provide as reference a private communication, so there is no way to verify this. 150.241.212.145 (talk) 12:00, 15 April 2024 (UTC)

References

The entire paper gives a proof, of a more general statement on polytopes. The fact that Delaunay triangulations are combinatorially equivalent to certain special polytopes is not from that source, but is easily proved, well known, and covered elsewhere in our article (at the end of the "d-dimensional Delaunay" section). —David Eppstein (talk) 22:34, 15 April 2024‎ (UTC)

upside-down

One way to generate a D.t. is to map the points to a paraboloid, $(x_{0},...,x_{n})$ → $(x_{0},...,x_{n},\Sigma {x_{i}^{2}})$, and take the convex hull; the triangulation is the reverse projection of the "underside" of this hull – but is there a name for, or anything interesting to say about, the upward-facing faces? —Tamfang (talk) 22:05, 15 April 2024 (UTC)

They're the farthest-point Delaunay triangulation. —David Eppstein (talk) 22:34, 15 April 2024 (UTC)

One other thing probably worth mentioning, while on this topic, is that instead of projecting orthogonally onto a paraboloid we can also take the inverse sterographic projection onto a sphere, which lets us compute the delaunay triangulation of a sphere (which is also the convex hull) in terms of the delaunay triangulation of the plane, or vice versa. This sees use in computational geometry applications on the sphere. –jacobolus (t) 01:24, 16 April 2024 (UTC)

That was the way K. Q. Brown originally did it. Nowadays you're more likely to see the orthogonal paraboloid version in textbooks. —David Eppstein (talk) 01:31, 16 April 2024 (UTC)

As an aside: if you start with coordinates ⁠$\langle 0,x,y\rangle$⁠ in the plane, then the inverse stereographic projection is $$\left\langle {\frac {{\tfrac {1}{2}}(1-x^{2}-y^{2})}{{\tfrac {1}{2}}(1+x^{2}+y^{2})}},{\frac {x}{{\tfrac {1}{2}}(1+x^{2}+y^{2})}},{\frac {y}{{\tfrac {1}{2}}(1+x^{2}+y^{2})}}\right\rangle$$ and the orthogonal projection to the paraboloid is $$\left\langle {\tfrac {1}{2}}(1-x^{2}-y^{2}),x,y\right\rangle ,$$ so you can also get from the sphere to the paraboloid or vice versa by central projection through the origin. –jacobolus (t) 02:11, 16 April 2024 (UTC)

The first determinant and second determinant specified in Algorithms section are not the same

The change is needed in this section Delaunay triangulation#Algorithms.

These determinants are not equal or even equivalent. Some clarification is needed about the first determinant.

${\begin{aligned}&Z_{1}(D)={\begin{vmatrix}A_{x}&A_{y}&A_{x}^{2}+A_{y}^{2}&1\\B_{x}&B_{y}&B_{x}^{2}+B_{y}^{2}&1\\C_{x}&C_{y}&C_{x}^{2}+C_{y}^{2}&1\\D_{x}&D_{y}&D_{x}^{2}+D_{y}^{2}&1\end{vmatrix}}\\[8pt]Z_{2}(D)={}&{\begin{vmatrix}A_{x}-D_{x}&A_{y}-D_{y}&(A_{x}-D_{x})^{2}+(A_{y}-D_{y})^{2}\\B_{x}-D_{x}&B_{y}-D_{y}&(B_{x}-D_{x})^{2}+(B_{y}-D_{y})^{2}\\C_{x}-D_{x}&C_{y}-D_{y}&(C_{x}-D_{x})^{2}+(C_{y}-D_{y})^{2}\end{vmatrix}}\end{aligned}}$

Only the $Z_{2}$ gives correct result. $Z_{1}$ is from , but gives incorrect result.

The $Z_{1}(D)=0$ forms a parabola D that goes through points $A$, $B$ and $C$. When the parabola is tall and narrow, the inner region can easily miss the circumcenter of the triangle $ABC$.

The $Z_{2}(D)=0$ forms the circumcircle D of the triangle $ABC$.

$Z_{1}$ expands to:

$+A_{y}A_{y}B_{y}D_{x}$

$+A_{y}A_{y}B_{x}C_{y}$

$+A_{y}A_{y}C_{x}D_{y}$

$+A_{y}B_{y}B_{y}C_{x}$

$+A_{y}B_{x}B_{x}C_{x}$

$+A_{y}B_{x}D_{y}D_{y}$

$+A_{y}B_{x}D_{x}D_{x}$

$+A_{y}C_{y}C_{y}D_{x}$

$+A_{y}C_{x}C_{x}D_{x}$

$+A_{x}A_{x}B_{y}D_{x}$

$+A_{x}A_{x}B_{x}C_{y}$

$+A_{x}A_{x}C_{x}D_{y}$

$+A_{x}B_{y}B_{y}D_{y}$

$+A_{x}B_{y}C_{y}C_{y}$

$+A_{x}B_{y}C_{x}C_{x}$

$+A_{x}B_{x}B_{x}D_{y}$

$+A_{x}C_{y}D_{y}D_{y}$

$+A_{x}C_{y}D_{x}D_{x}$

$+B_{y}B_{y}C_{y}D_{x}$

$+B_{y}C_{x}D_{y}D_{y}$

$+B_{y}C_{x}D_{x}D_{x}$

$+B_{x}B_{x}C_{y}D_{x}$

$+B_{x}C_{y}C_{y}D_{y}$

$+B_{x}C_{x}C_{x}D_{y}$

$-A_{y}A_{y}B_{y}C_{x}$

$-A_{y}A_{y}B_{x}D_{y}$

$-A_{y}A_{y}C_{y}D_{x}$

$-A_{y}B_{y}B_{y}D_{x}$

$-A_{y}B_{x}B_{x}D_{x}$

$-A_{y}B_{x}C_{y}C_{y}$

$-A_{y}B_{x}C_{x}C_{x}$

$-A_{y}C_{x}D_{y}D_{y}$

$-A_{y}C_{x}D_{x}D_{x}$

$-A_{x}A_{x}B_{y}C_{x}$

$-A_{x}A_{x}B_{x}D_{y}$

$-A_{x}A_{x}C_{y}D_{x}$

$-A_{x}B_{y}B_{y}C_{y}$

$-A_{x}B_{y}D_{y}D_{y}$

$-A_{x}B_{y}D_{x}D_{x}$

$-A_{x}B_{x}B_{x}C_{y}$

$-A_{x}C_{y}C_{y}D_{y}$

$-A_{x}C_{x}C_{x}D_{y}$

$-B_{y}B_{y}C_{x}D_{y}$

$-B_{y}C_{y}C_{y}D_{x}$

$-B_{y}C_{x}C_{x}D_{x}$

$-B_{x}B_{x}C_{x}D_{y}$

$-B_{x}C_{y}D_{y}D_{y}$

$-B_{x}C_{y}D_{x}D_{x}$

While $Z_{2}$ expands to:

$+A_{y}B_{x}B_{x}C_{x}$

$+A_{y}B_{x}D_{x}D_{x}$

$+A_{y}C_{x}C_{x}D_{x}$

$+A_{x}A_{x}B_{y}D_{x}$

$+A_{x}A_{x}B_{x}C_{y}$

$+A_{x}A_{x}C_{x}D_{y}$

$+A_{x}B_{y}C_{x}C_{x}$

$+A_{x}B_{x}B_{x}D_{y}$

$+A_{x}C_{y}D_{x}D_{x}$

$+B_{y}C_{x}D_{x}D_{x}$

$+B_{x}B_{x}C_{y}D_{x}$

$+B_{x}C_{x}C_{x}D_{y}$

$-A_{y}B_{x}B_{x}D_{x}$

$-A_{y}B_{x}C_{x}C_{x}$

$-A_{y}C_{x}D_{x}D_{x}$

$-A_{x}A_{x}B_{y}C_{x}$

$-A_{x}A_{x}B_{x}D_{y}$

$-A_{x}A_{x}C_{y}D_{x}$

$-A_{x}B_{y}D_{x}D_{x}$

$-A_{x}B_{x}B_{x}C_{y}$

$-A_{x}C_{x}C_{x}D_{y}$

$-B_{y}C_{x}C_{x}D_{x}$

$-B_{x}B_{x}C_{x}D_{y}$

$-B_{x}C_{y}D_{x}D_{x}$

I made a simple test app in C# with Windows forms you can use to compare the results [1]https://github.com/ernestasjuska/DelauneyDeterminantTest/blob/main/Determinants/Form1.cs. Wikipedia does not allow me to upload diagram pictures yet. Ernestasju (talk) 09:14, 14 July 2024 (UTC)