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)

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)

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)