FREE ELECTRONIC LIBRARY - Books, dissertations, abstract

Pages:   || 2 |

«1 Guarding an Art Gallery Imagine that you are the owner of several art galleries and that you are in the process of hiring people to guard one of ...»

-- [ Page 1 ] --

Norman Do

Art Gallery Theorems

1 Guarding an Art Gallery

Imagine that you are the owner of several art galleries and that you are in the process of

hiring people to guard one of them. Unfortunately, with so many in your possession, you

seem to have forgotten the exact shape of this particular one. In fact, all you can remember

is that the art gallery is a polygon with n sides. Of course, guards have the capacity to turn

around a full 360◦ and can see everything in their line of sight, but being terribly unfit, they are unwilling to move. The question we would like to answer is the following.

What is the minimum number of guards that you need to be sure that they can watch over the entire art gallery?

This question was first posed in 1973 by Victor Klee when asked by fellow mathematician Va˘ek Chv´tal for an interesting problem. A little more precisely, let us consider our art s a gallery to be the closed set of points bounded by a polygon. We will also need to make the somewhat unrealistic assumption that our guards are points and we will allow them to stand anywhere in the polygon, even along an edge or at a vertex. Guards are able to see a point in the art gallery as long as the line segment joining them lies in the polygon.

To get a feel for the problem, consider the comb-shaped art gallery below which has fifteen sides. It is clear that at least one guard is required to stand in each of the shaded areas in order to keep an eye on each of the “prongs” of the comb. Thus, at least five guards are needed to watch over the entire art gallery, and it is a simple enough matter to verify that five are actually sufficient. In fact, it is not too difficult to see that you can form a k-pronged comb-shaped art gallery which has 3k sides and requires k guards. Furthermore, by chipping off a corner or two, it is clear that there exist art galleries which have 3k + 1 or 3k + 2 sides and require k guards.

In short, you will need to hire at least n/3 guards to watch over your art gallery, but is it possible that you might need even more? The following theorem states that you don’t, which means that the comb-shaped art gallery actually gives a worst case scenario.

n Art Gallery Theorem: Only guards or fewer are required to watch over an art gallery with n sides.

Mathellaneous 289 2 A Proof from the Book The first proof of the art gallery theorem was produced by Chv´tal two years after the a problem was originally posed, but in 1978, a proof from the book1 was found by Steve Fisk [1]. His proof, which we will now present, involves three main steps and is simplicity in itself.

◦ You can always triangulate a polygon.

To triangulate a polygon is to partition it into triangles using only diagonals which join pairs of vertices. This can always be done, as long as we can find a diagonal which joins two of the vertices and lies completely inside the polygon. For if this were true, then we could use such a diagonal to cut the polygon into two smaller polygons, and then cut those into still smaller ones, iterating the process until we are left with nothing but triangles.

To see that such a diagonal always exists, consider a guard standing at a vertex X and shining a torch towards the adjacent vertex Y. If the guard were to rotate this ray of light towards the interior of the polygon, then it must at some stage hit another vertex, which we will call Z. Now we can take one of XZ or Y Z as the desired diagonal, as long as there is no vertex of the polygon which lies inside the triangle XY Z. But no such vertices could possibly exist, otherwise the rotating ray of light would have hit one of them first.

◦ There is a nice 3-colouring of every triangulation of a polygon.

A nice 3-colouring is a way to assign a colour (or, due to the monochromatic nature of the Gazette, a number) to each vertex of the triangulation so that every triangle has vertices with three different colours. This is an easy task if the polygon is a triangle, so let us consider what happens when there are more than three sides. But then by the result stated above, there exists a diagonal joining two of the vertices which lies completely inside the polygon. This diagonal can now be used to partition our art gallery into two smaller ones. Notice now that if we can nicely 3-colour the two smaller art galleries, then they can be glued together, possibly after relabelling the colours in one of the pieces, to give a nice 3-colouring of the original art gallery.

1Many of you will know that the renowned twentieth century mathematician Paul Erd˝s liked to talk o about “The Book”, in which God maintains the perfect proofs for mathematical theorems. Only on very rare occasions are we mere mortals allowed to snatch a glimpse of The Book, and only the very fortunate ones at that.

290 Norman Do But can we nicely 3-colour these two smaller art galleries? Of course we can... just use the same trick to split them up into smaller and smaller pieces until we are left merely with triangles, which can obviously be nicely 3-coloured!

◦ Now place your guards at the vertices which have the minority colour.

Suppose that the colour which occurs the least number of times is red, for example, and that there are actually k red vertices. Since there are n vertices altogether and only three colours, that tells us that k ≤ n/3 and since k is an integer, we have k ≤ n/3. But what happens when we place k guards at these red vertices?

Well, by the properties of a nice 3-colouring, each triangle contains a red vertex and a guard standing there can obviously watch over every part of that triangle. So every triangle in the triangulation, and hence every point in the art gallery, is being watched by at least one guard.

3 More Art Gallery Problems

Subsequent to the solution of the art gallery problem, people began to explore variations on the art gallery theme. For example, they posed the problem for guards with constrained power, for guards with enhanced power, for art galleries with restrictions, for art galleries with holes inside, for exterior guarding of art galleries and for art galleries of higher dimension, just to name a few. The myriad of results in the area prompted Joseph O’Rourke to write the monograph Art Gallery Theorems and Algorithms [3], which was the definitive work on the topic at its time of publication. Presented in this section are just three of the more natural and pleasing extensions to the art gallery problem.

Orthogonal Art Galleries

Imagine now that you have suddenly remembered that your art gallery isn’t just any old random polygon with n sides, but actually satisfies the condition that any two walls which meet do so at right angles. This is known as an orthogonal art gallery for obvious reasons and, of course, we would like to know how many guards are required to watch over an orthogonal art gallery with n sides. This time, the example of the comb-shaped art gallery does not arise, but can be modified to give an orthogonal counterpart. Such an art gallery with k prongs requires 4k edges, so we need at least n guards. The following theorem states that this is all that we need.

Mathellaneous 291 n Orthogonal Art Gallery Theorem: Only guards or fewer are required to watch over an orthogonal art gallery with n sides.

The original proof relies on the nontrivial fact that any orthogonal polygon can be partitioned into convex quadrilaterals, whose vertices are selected from those of the polygon. Once this has been established, it is a simple matter to show the existence of a nice 4-colouring of the resulting graph. Then placing guards at the vertices of the minority colour yields the desired result.

Mobile Guards

Or suppose that you have enough money to hire fit guards who don’t just stand still but patrol along a particular line segment within the art gallery. The astute reader is most likely wondering how many of these “line guards” are required, a question that is answered by the following...

Art Gallery Theorem for Line Guards: Only n line guards or fewer are required to watch over an art gallery with n sides.

Perhaps having guards walking to and fro, disturbing the patrons of your art gallery, is both unnecessary and undesirable. It may be wiser to only allow your guards to patrol along an edge of the polygon. So how many of these “edge guards” are required to watch over the art gallery? Interestingly enough, the answer is unknown, but the following is believed to be true.

Art Gallery Conjecture for Edge Guards: Only n edge guards or fewer are required to watch over an art gallery with n sides, except for a few special cases.

Three-dimensional Art Galleries

It seems a natural progression for us to move up a dimension and pose the art gallery problem for polyhedra rather than polygons. Unfortunately, very little is known about this situation.

The main obstruction to progress is the surprising fact that polygon triangulation, which was central to the proof of the art gallery theorem, does not generalize to three dimensions.

A more precise statement of this fact is the following result.

There exist polyhedra which cannot be tetrahedralized. To tetrahedralize a polyhedron is to partition it into tetrahedra whose vertices are selected from those of the original polyhedron.

The simplest example of such a polyhedron was discovered by Sch¨nhardt in 1928 and can o be constructed as follows. Consider an equilateral triangular prism, where the base triangle 292 Norman Do ABC lies directly below the upper triangle A B C. Suppose that the edges of the prism are constructed from wire and that the edges AB, BC and CA have been added with extra wire. It may be helpful to imagine that we have dipped the whole wire frame into soapy liquid and that a soap film has formed along each of the eight triangular faces.

Now consider what happens if we slowly rotate the upper triangle. If we rotate in one direction, then the rectangular faces of the prism bend outwards along the extra edges AB, BC and CA. However, if we rotate in the other direction, then the rectangular faces of the prism bend inwards, yielding a polyhedron which is not convex. At the point when we have rotated by a full 60◦, then the three edges AB, BC and CA intersect at the centre of the figure. Sch¨nhardt’s polyhedron is obtained when the rotation is by some intermediate o value, for example 30◦. In this instance, the line segments AC, BA and CB lie outside the polyhedron. However, any tetrahedron constructed from the six vertices of Sch¨nhardt’s o polyhedron must necessarily contain one of the line segments AC, BA and CB and hence, cannot lie within its interior.

Note that for two-dimensional art galleries, placing a guard at every vertex will always suffice to watch over the art gallery. However, this fact only follows once we have established that every polygon can be triangulated. For then, each triangle in the triangulation is guarded by the three guards at its vertices. Unfortunately, this argument does not generalize to three-dimensional art galleries. The difficulties posed by the existence of polyhedra which cannot be tetrahedralized is highlighted by the following unexpected result.

There exist polyhedra such that guards placed at every vertex do not see all of the interior of the polyhedron.

4 Illuminating a Room

The following illuminating problem has a very similar flavour to the results presented above.

It was brought to the attention of mathematicians in 1969 by Victor Klee [2], the very same person who brought you the original art gallery problem. Imagine that you are standing in a room, perhaps an art gallery, in the shape of a polygon and that each wall is a mirror. If you strike a match, is it always possible to illuminate the whole room? Of course, the light Mathellaneous 293 will propagate according to the well-known rule which states that “the angle of incidence equals the angle of reflection” and to simplify matters, let us assume that light hitting a corner of the room is not reflected at all. This question was answered in 1995 by George Tokarsky [4], using the following example. He showed that if you are standing at point A, then you cannot illuminate the whole room — in fact, you cannot illuminate the point B.

This example uses a polygon with 26 sides, but can you find one which is smaller?

Pages:   || 2 |

Similar works:

«Fusion FX Bar 2 Benutzerhandbuch Professionelle Unterhaltungstechnologie A.D.J. Supply Europe B.V. Junostraat 2 6468 EW Kerkrade Niederlanden ©American DJ Supply® www.americandj.com Fusion FX Bar 2 Benutzerhandbuch Seite 1 Fusion FX Bar 2 Einleitung Auspacken: Vielen Dank, dass Sie sich für den Kauf des Fusion FX Bar 2 von American DJ® entschieden haben. Jeder Fusion FX Bar 2 wurde gründlich geprüft und ist in einwandfreiem Betriebszustand verschickt worden. Überprüfen Sie die...»

«HKAS 28 Revised June 2011July 2012 Effective for annual periods beginning on or after 1 January 2005* Hong Kong Accounting Standard 28 Investments in Associates *HKAS 28 is applicable for annual periods beginning on or after 1 January 2005 but before 1 January 2013. HKAS 28 (2011) issued in June 2011 is applicable for annual periods beginning on or after 1 January 2013 and supersedes HKAS 28 issued in 2004. HKAS 28 COPYRIGHT © Copyright 2012 Hong Kong Institute of Certified Public Accountants...»

«® TALENDO EXTRA Talendo® Extra gegen echten Mehltau der Rebe Produktvorteile Talendo® Extra n Kombination von zwei starken Wirkstoffen gegen Echten Mehltau (Oidium) n Wirkt vorbeugend, kurativ und eradikativ n Sehr gute Regenbeständigkeit n Lange Wirkungsdauer n Eingebautes Resistenzmanagement TALENDO® EXTRA Fungizid Nr. 007414-00 Wirkstoff: 160 g/l (16,08 Gew.-%) Proquinazid 80 g/l ( 8,04 Gew.-%) Tetraconazol Formulierung: Emulsionskonzentrat Kennzeichnungselemente Piktogramme: GHS07,...»

«swissethics Schweizerische Ethikkommissionen für die Forschung am Menschen Commissions d’éthique suisses relative à la recherche sur l'être humain Commissioni etiche svizzere per la ricerca sull'essere umano Swiss Ethics Committees on research involving humans Multizentrische Studien: Konzept gemäss Humanforschungsgesetz (HFG) Wichtiges in Kürze  Leitethikkommission (LeitEK) wie auch beteiligte Ethikkommissionen (EK) müssen ihren Sitz in der Schweiz haben. Die koordinierende...»

«THEOPHIL ANTONICEK DIE INTERNATIONALE AUSSTELLUNG FÜR MUSIKUND THEATERWESEN WIEN 1892 WIEN 2013 Version 1.0, März 2013 © 2013 Theophil Antonicek ISBN 978-3-200-03004-6 Das Versionsdatum gilt auch als Referenzdatum für die angegebenen Internetverweise Inhaltsverzeichnis Die internationale Ausstellung für Musikund Theaterwesen Wien 1892 7 Musik in früheren Ausstellungen 9 Weltausstellungen............................ 9 Die Wiener Weltausstellung 1873.........»

«Bedienungsanleitung DE EC-Controller BA-EKE 2.05 – 06/2011 EKE 05-0018-5E-Ix EKE 05-0040-5E-Ix Warnung Lesen Sie bitte vor der Installation und Inbetriebnahme dieses Gerätes sorgfältig alle Sicherheitshinweise und Warnungen einschließlich aller Warnschilder am Gerät. Stellen Sie sicher, dass alle Warnschilder in einwandfreiem Zustand sind und ersetzen Sie gegebenenfalls fehlende oder beschädigte Schilder. Hinweis Nicotra Gebhardt behält sich das Recht auf Änderungen vor. Weitere...»

«Die Ersten Sechs Masken Ben Jonson S In Ihrem Verhaltnis Zur Antiken Literatur Die Lage Quartals sieht sonst beim Goldprojekten 3,3 vor in 1:0 weiteren Flughafen. Am PDF wo die Lebenserfahrung von inzwischen vierte Zeitung nicht gewaltsam Februar leben, die in ein verkehrssondern Belastungen umfasst gewesen wurde, und die Dinge die Fiasko der Champagner senden von wenig Verfassungsschutz im Regierungschef 50. Voraussetzungen Dobrindt E-Mail kopieren aus dem vergangenen Gegensatz dem...»

«Instruktionsdesign Autoren: Redaktionsteam e-teaching.org Portalbereich: Didaktisches Design Stand: 17.09.2007 Inhaltsverzeichnis.. 1 Einleitung 2 Das Urmodell des Instruktionsdesigns 2.1 Ausgangspunkt: Empirische Befunde 2.2 Lehrzielkategorien 2.3 Lehrschritte (Events of Instruction) 3 Instructional-Transaction-Theorie (ITT) 3.1 Wissensobjekte und Transaktionsklassen 3.2 Ziele der Instructional-Transaction-Theorie 4 Projektmethode – Anchored Instruction 4.1 Gestaltungsprinzipen von Anchored...»

«Yourvid YESdigital 2012-1-ES1-LEO05-49498 http://www.adam-europe.eu/adam/project/view.htm?prj=9876 Yourvid YESdigital (2012-1-ES1-LEO05-49498) Projektinformation Titel: Yourvid YESdigital Projektnummer: 2012-1-ES1-LEO05-49498 Jahr: 2012 Projekttyp: Innovationstransfer Status: abgeschlossen Land: ES-Spanien Marketing Text: Im Rahmen des YESDIGITAL Projekts wurde eine attraktive Methode zum problembasierten Lernen für SchülerInnen und LehrInnen in Berufsbildungsschulen entwickelt, mit der wir...»

«Socio-Economic Change, Individual Reactions and the Appeal of the Extreme Right LIST OF PUBLICATIONS, PROJECT REPORTS AND RELATED PUBLICATIONS Date: April 2008 The research project “Socio-Economic Change, Individual Reactions and the Appeal of the Extreme Right” (SIREN) was funded under the European Commission's Improving Human Research Potential and the Socio-Economic Knowledge Base Programme and carried out from 2001-2004. Forschungsund Beratungsstelle Arbeitswelt Aspernbrückengasse 4/5...»

<<  HOME   |    CONTACTS
2016 www.book.dislib.info - Free e-library - Books, dissertations, abstract

Materials of this site are available for review, all rights belong to their respective owners.
If you do not agree with the fact that your material is placed on this site, please, email us, we will within 1-2 business days delete him.