Talk:Delaunay triangulation
This is the talk page for discussing improvements to the Delaunay triangulation article. This is not a forum for general discussion of the article's subject. |
Article policies
|
Find sources: Google (books · news · scholar · free images · WP refs) · FENS · JSTOR · TWL |
Archives: 1Auto-archiving period: 730 days ![]() |
![]() | This article is rated C-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects: | ||||||||||
|
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)
- @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)
- 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)
- 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)
- 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)
- 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)
- @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)
- 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)
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)
- @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)
- @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)