Talk:Simple polygon

Question

I enjoy math, but I am a novice with it. I was wondering today if there is a proof that a simple polygon can always be made by connecting any set of dots on a plane, so I went online to try to find out. Is it possible that this sort of info could be provided on this page?

Thank you.

2Plus2Is4 (talk) 01:19, 27 June 2013 (UTC)

Yes. For instance the solution to the traveling salesman problem is always a simple polygon. It should be possible to find this in a published source and add to the article. —David Eppstein (talk) 02:01, 27 June 2013 (UTC)

He-he, no. If all points are collinear . Otherwise yes, and the first part of Graham scan will be a way faster way. Of related curiuosity, whether nlogn is the lower bound for complexity. - üser:Altenmann >t 04:29, 12 December 2015 (UTC) - üser:Altenmann >t 04:29, 12 December 2015 (UTC)

In what model of computation? If the coordinates are integers and integer sorting is allowed, then no, you can do it faster. (Split the points into the subset above and below the line segment between leftmost and rightmost, and then connect each subset in sorted order.) However, in models of computation where convex hulls take $\Omega (n\log n)$ time (e.g. algebraic computation trees) constructing a simple polygon takes the same time, because it is known how to go from a simple polygon to the convex hull in linear time. —David Eppstein (talk) 04:40, 12 December 2015 (UTC)

Problem with weakly simple section

Our section currently states "If a closed polygonal chain embedded in the plane divides it into two regions one of which is topologically equivalent to a disk, then the chain is called a weakly simple polygon." But this cannot be correct: if the chain is embedded, it cannot touch itself (that's what the definition of "embedding" is), so it is simple (not just weakly simple) and by the Jordan curve theorem always divides the plane into two parts. And the associated illustration, which is supposed to match this "definition", does not show an embedded chain, but one that has self-intersections. So what is the correct form of the definition that is intended here? —David Eppstein (talk) 04:55, 12 December 2015 (UTC)

I changed this part to more accurately reflect what its source actually says. However, I suspect there are other sources out there with definitions that differ from the two given here in subtle or less-subtle ways, some of which may resemble the part I replaced. If so they should be added. —David Eppstein (talk) 05:45, 12 December 2015 (UTC)

Simple polygons on the sphere

It may be worth adding a discussion at the end of polygons on the sphere. These are practically important for GIS etc. have some interesting differences from planar polygons; for example, there is no a priori reason to declare one side or the other as the "interior". In particular things get tricky when a polygon does not fit within a hemisphere, e.g. such polygons don't have an easily defined convex hull. –jacobolus (t) 03:25, 18 July 2023 (UTC)

definition of "region"

At some point a while back I looked up a whole bunch of analysis textbooks to compare their definitions/usage of the terms "domain" and "region", as evidence for figuring out what the top couple sections of domain should say. (The "historical notes" section there is not really right; Caratheodory definitely did not introduce this concept.) From everything I can tell, these terms are largely used interchangeably across mathematical subdisciplines to mean "connected open set in a topological space", which is a precise formalization of a casual term meaning something like "the inside or outside of a shape". (Some sources, rather confusingly in my opinion, specifically define the two to mean subtly different things.)

The reason I think it's helpful to wikilink terms like this, even if the link might sometimes fly over the head of some of the intended audience, is that many readers don't actually know that this is what "region" informally means in mathematics. The article circle (whose text I didn't write), says:

Specifically, a circle is a simple closed curve that divides the plane into two regions: an interior and an exterior. In everyday use, the term "circle" may be used interchangeably to refer to either the boundary of the figure, or to the whole figure including its interior; in strict technical usage, the circle is only the boundary and the whole figure is called a disc.

Just yesterday someone tried to change it to say that the circle divides the plane into 3 regions: the interior, the circle itself, and the exterior. To someone who is not familiar with the customary techical meaning of the jargon word "region", it's not inherently obvious that a circle (or a simple polygon) can't be a "region". Obviously the word "region" originally comes by analogy with the geographical / cartographical term region, and you'd think people would roughly have a sense of the distinction between a region – say an administrative district – and its border or boundary, but when a word is transplanted from one context to another like that, it's helpful to be able to point to a definition to avoid confusion and give readers something to look into if they are curious to learn further details.

The better solution in my opinion would be to add some material at the top of domain which is more accessible to non-technical readers, along with a picture or two and some examples. –jacobolus (t) 08:01, 9 September 2023 (UTC)

should turning number / "density" be worked in here?

For a simple polygon, the turning number or "density" is always equal to 1. Perhaps this should be worked into the paragraph about being a Jordan curve, or into the paragraph about internal and external angles. –jacobolus (t) 17:21, 17 September 2023 (UTC)

This is the same thing as the sum of external angles, but for smooth curves. Polygons are not smooth curves, so we should not link to articles defined to require smoothness. —David Eppstein (talk) 19:21, 17 September 2023 (UTC)

Eh, the concept (like total curvature) is most naturally defined first for polygons then generalized to arbitrary closed curves (which can be taken as a smooth limit of polygons as the vertices get infinitely close together / sides get infinitesimally short – as familiar in every other concept related to smooth shapes and motions built on calculus, this limit turns a sum into an integral; if we allow curvature as a function of arclength to be a distribution we can easily account for closed curves with cusps, etc.). I think the version in Wikipedia overconstrains and does a poor job explaining the concept, but perhaps that's inherited from available sources just doing a bad job.

Despite leading with a limiting definition, turning number does mention polygons. Then density (polytope)#Polygons is entirely about polygons. –jacobolus (t) 19:45, 17 September 2023 (UTC)

We could say something like "The fact that all simple polygons have the same sum of external angles can be generalized to simple closed curves, which all have the same turning number.", at the end of the paragraph on external angles. But we would need a published source making that specific connection. —David Eppstein (talk) 20:46, 17 September 2023 (UTC)

This paper seems to have some good historical survey: https://www.ams.org/journals/tran/1990-322-01/S0002-9947-1990-1024774-2/S0002-9947-1990-1024774-2.pdf – as I would have expected the polygon concept seems to have come first. –jacobolus (t) 21:53, 17 September 2023 (UTC)

GA Review

This review is transcluded from Talk:Simple polygon/GA1. The edit link for this section can be used to add comments to the review.

Reviewer: Dedhert.Jr (talk · contribs) 04:36, 2 January 2024 (UTC)

I'll be honest. I'm trying to avoid reviewing this article, but I have no choice but to do so. If I'm not actively reviewing this article due to up to my neck in real life, I may need a second opinion to assist me. Anyway, at least let me try.

I see that @David Eppstein and @Jacobolus are the main writers of this article, so I think this could be counted as two users nominating the article. I'll begin reviewing this article now.

• Lead: Just an option question. Is it possible to write at least three paragraphs? Dedhert.Jr (talk) 07:21, 2 January 2024 (UTC)
  • I'm not sure I understand what you're asking. It has four paragraphs. Four is "at least three". —David Eppstein (talk) 17:59, 2 January 2024 (UTC)

    Oh. Okay, I thought three paragraphs is enough to describe the whole article. That doesn't matter anyway. Dedhert.Jr (talk) 02:08, 3 January 2024 (UTC)

• Definition: It doesn't mention the word "closed curve" in the source. Is it related, or maybe I should probably need to understand the meaning of closed curve first? (GACR2) In the second paragraph, why do you need the plural word for "vertex" if our article Vertex (geometry) could have just mentioned it? Are the words "exactly" and "indeed" in the second and third paragraph, respectively, supposed to be avoided under WP:EDITORIAL? (GACR1b) In the second paragraph, if the words phrase "some sources", should you cite them in at least two or more sources? Presumably, you forgot the link in the last citation in the second paragraph [1]. The source in the fourth paragraph didn't mention anything about the diagonal. GACR2) Dedhert.Jr (talk) 07:21, 2 January 2024 (UTC)
  • I added another source for the "closed curve" definition; Preparata and Shamos give a different but equivalent definition. Why "vertices": as Jacobolus says below, because we use the plural frequently, it is not a standard way to form a plural, it doesn't take long to say what the plural is, and this is often a point of confusion (I often hear students back-form the singular to the incorrect "verticee"). "Exactly" disambiguates the number "two": it means the number must be two, no more, no less. It is not an editorialization; it is a clarification. But in some rewording that sentence is now gone. "Indeed" is again, not an editorialization, but rather a connecting word, emphasizing the relevance of the special case of polygons to the full Jordan curve theorem. I didn't forget the link in the reference; I used an offline copy of the reference rather than finding it from a link. The link you supplied goes to the wrong edition of the book. I added a doi (not a url) for the correct edition. —David Eppstein (talk) 18:16, 2 January 2024 (UTC)

    I do think that I may have misunderstood, but thanks for clarifying anyway. Dedhert.Jr (talk) 02:07, 3 January 2024 (UTC)

• Properties: You may forget to put the link in the citation in the first paragraph, again [2] (hopefully this is the right one). Also, the phrase Every simple polygon can be partitioned into interior-disjoint triangles by a subset of its diagonals. Is it possible to find the link for interior-disjoint here, as I do not understand the meaning of these mathematical terms? (GACR1a) Do you have an illustration for the ear and mouth of a simple polygon, or maybe you could exploit the image of a somewhat called polygonal triangulation by expanding captions to provide both second and third paragraphs? (GACR6) Dedhert.Jr (talk) 07:21, 2 January 2024 (UTC)

  Link added. Changed "interior-disjoint" to be "non-overlapping" to be less technical. The illustration is already there in the definitions section. —David Eppstein (talk) 05:12, 3 January 2024 (UTC)

• Special cases: No problems here. Dedhert.Jr (talk) 07:21, 2 January 2024 (UTC)

• Computational problems: Can we just mathfying the related-mathematical-symbols and -letter, instead of writing in HTML by adding more prime marks or apostrophes, just for consistency? Also, the same reason for the weasel word again in the awkward last sentence (GACR1b). Dedhert.Jr (talk) 07:21, 2 January 2024 (UTC)

  Math converted and sentence reworded. —David Eppstein (talk) 05:34, 3 January 2024 (UTC)

• Related construction: The section has some short paragraphs. For the last paragraph, can you summarize up what the open problem says? Dedhert.Jr (talk) 07:21, 2 January 2024 (UTC)

  The paragraphs are short because they each point to an article on a related topic, and the detail on those topics can be found at the linked articles. It would not make sense to merge them because they are on different topics. Here's a summary of the open problem, copied from the first few words of the sentence: "The computational complexity of reconstructing a polygon that has a given graph as its visibility graph". We don't know what that problem's complexity is. The open problem is to find out the complexity of reconstructing polygons from visibility graphs. There isn't really anything more to add summarizing the problem than what is already there. —David Eppstein (talk) 05:37, 3 January 2024 (UTC)

I also wonder if you can put most of the see-also links in every section of the article, which may be helpful for expansion, or whatever it is. The article has met six criteria good article: It is neutral (GACR4) and stable, although we have one [3], maybe? (GACR5) Weirdly, the copyvio mentions it has the similarity of words comparing the 86% in group google, and over 8% in AMS. [4] Anyway, if you have any questions, or if you have completed them, please let me know. Good luck! Dedhert.Jr (talk) 07:21, 2 January 2024 (UTC)

The 86% similarity is from somebody copy-pasting our article and some other stuff dated December 28, 2023, a few days ago. That is, they copied from us, rather than vice versa. —David Eppstein (talk) 07:59, 2 January 2024 (UTC)

Okay. At least this could not be considered as WP:COPYVIO, so I will not fail this article. Dedhert.Jr (talk) 08:03, 2 January 2024 (UTC)

The AMS one (a web column called "Are Precise Definitions a Good Idea?") is entirely based on the occurrence in both of generic phrases such as "the set of points in a plane", "the interior of the polygon", "the vertices of a simple polygon", and "the same is true for". –jacobolus (t) 17:22, 2 January 2024 (UTC)

I'd say @David Eppstein was the main author here. My main contribution was to pull pictures in from other places to liven things up a bit, and then make a couple new basic illustrations. (If you see anything else that seems like it needs a picture, feel free to ask.) Do you have an illustration for the ear and mouth of a simple polygon, – scroll up a bit, this is one of the parts illustrated in the figure in the "Definitions" section. –jacobolus (t) 16:35, 2 January 2024 (UTC)

@Jacobolus Thank you. I didn't notice that the image is also describing the ear and mouth as well. Maybe we can explain what are the ear and mouth, or maybe we could replace their definition from the section "Properties" to "Definition". But meh, whatever. It's optional anyway. Dedhert.Jr (talk) 02:05, 3 January 2024 (UTC)

why do you need the plural word for "vertex" – this seems pretty helpful to me, since the words vertex and vertices appear all over this article, and it's a non-standard pluralization. –jacobolus (t) 16:38, 2 January 2024 (UTC)

@David Eppstein, @Jacobolus. I think I should on hold the addition of see-also links later applying to the content, and maybe this can be discuss later. As I mentioned, the article has met six criterias. I guess I can pass this article! Felicitations to both of you! Dedhert.Jr (talk) 15:13, 4 January 2024 (UTC)

Thanks! And Jacobolus, I know you don't think you should count as the main author, but thanks regardless for your help bringing this up to the GA standard. —David Eppstein (talk) 15:37, 4 January 2024 (UTC)

Cheers. –jacobolus (t) 18:05, 4 January 2024 (UTC)