Talk:Art gallery problem

This article is rated B-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects:

Mathematics Low‑priority 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 articles Low This article has been rated as Low-priority on the project's priority scale.

Somebody please illustrate this problem. I'm having trouble understanding it without any graphical guidance. 201.132.65.36 15:33, 13 December 2006 (UTC)[reply]

The 3D version of it seems VERY unlikely to be true. I can't come up with a situation in which a point on the inside of a polyhedron is unable to see any of the vertices. We need to get a citation for this - or we should delete it. SteveBaker 22:58, 31 October 2007 (UTC)[reply]

Kiitos for that example Ilmari. It's a very counterintuitive fact; I didn't believe it until I saw an example. Jamie King 22:22, 11 November 2007 (UTC)[reply]

Surely Art gallery theorem and Art gallery problem are covering the same thing? I suggest a merger. Richard Pinch (talk) 22:28, 23 July 2008 (UTC)[reply]

A picture of a non-convex polygon triangulation with a 3-coloring of vertices would be useful here. Mhym (talk) 03:18, 21 July 2009 (UTC)[reply]

I just happen to have one...will upload. —David Eppstein (talk) 03:35, 21 July 2009 (UTC)[reply]

Can you perhaps shade the interior of the polygon a little? Otherwise this looks like a graph, not the interior of a polygon. Thanks! Mhym (talk) 03:54, 21 July 2009 (UTC)[reply]

I did shade it a little. But maybe it was too subtle. —David Eppstein (talk) 04:00, 21 July 2009 (UTC)[reply]

Ok, changed from #FCFCFC to #F4F4F4. Better? —David Eppstein (talk) 04:02, 21 July 2009 (UTC)[reply]

Yes, I think so. Perhaps this depends on the browser - not sure. Thanks! Mhym (talk) 04:06, 21 July 2009 (UTC)[reply]

It can be useful to have a link to the maximum hidden set problem - finding the largest number of points in a polygon, such that no two points can see each other. See this MathOverflow question for some connections between the two problems. --Erel Segal (talk) 07:16, 12 July 2013 (UTC)[reply]

Do you have a reliable source for this connection? MO doesn't really meet our standards for sourcing. —David Eppstein (talk) 07:27, 12 July 2013 (UTC)[reply]

I had changed the capitalisation on this, because the statement is that it is considered to be one of the "Proofs from the book". It is, also, a proof included in the book Proofs from THE BOOK, which is a separate, but related, thing. I can't see any evidence that that capitalisation is used except in the case of the printed book. The sentence is not referring to the specific, printed book that the wikilink links to. Porphyro (talk) 21:23, 22 May 2017 (UTC)[reply]

In this case, WTH "proofs form the book"? Is this an idiomatic English expression I am not aware of? In this case I fail to see why you wikilinked it to THE BOOK. Also, this is an expression of judgement and must be attributed/referenced. Finally, if it is in THE BOOK, then " that is considered to be one of the Proofs from THE BOOK. " is kinda meaningless. Staszek Lem (talk) 22:01, 22 May 2017 (UTC)[reply]

P.S. OK. I got it; Proofs from THE BOOK refers to Erdos's witticism about "The Book". In any case, the sentence must be rephrased (a) either attributed or otherwise restated without WP:WEASELy "is considered to be" and (b) "The Book" must be explained, if the term used. Staszek Lem (talk) 22:01, 22 May 2017 (UTC)[reply]

I fully agree and like what you've changed it to. Porphyro (talk) 09:29, 23 May 2017 (UTC)[reply]

Hello fellow Wikipedians,

I have just modified one external link on Art gallery problem. Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:

• Added archive https://web.archive.org/web/20030624032504/http://www.inf.ethz.ch/personal/eidenben/publications/eidenbenz_algorithmica2001.pdf to http://www.inf.ethz.ch/personal/eidenben/publications/eidenbenz_algorithmica2001.pdf

When you have finished reviewing my changes, you may follow the instructions on the template below to fix any issues with the URLs.

This message was posted before February 2018. After February 2018, "External links modified" talk page sections are no longer generated or monitored by InternetArchiveBot. No special action is required regarding these talk page notices, other than regular verification using the archive tool instructions below. Editors have permission to delete these "External links modified" talk page sections if they want to de-clutter talk pages, but see the RfC before doing mass systematic removals. This message is updated dynamically through the template {{source check}} (last update: 5 June 2024).

• If you have discovered URLs which were erroneously considered dead by the bot, you can report them with this tool.
• If you found an error with any archives or the URLs themselves, you can fix them with this tool.

Cheers.—InternetArchiveBot (Report bug) 17:35, 9 July 2017 (UTC)[reply]

The article currently claims that there is a constant factor approximation algorithm. There is no source for this. There circulated a preprint that made this claim, but during the review phase there were errors discovered that were not repaired. I suggest to just remove this one sentence. — Preceding unsigned comment added by Tillmann Miltzow (talk • contribs) 14:40, 12 April 2022 (UTC)[reply]