tailieunhanh - Báo cáo toán học: "Orthogonal art galleries with holes: a coloring proof of Aggarwal’s Theorem"

Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: Orthogonal art galleries with holes: a coloring proof of Aggarwal’s Theorem. | Orthogonal art galleries with holes a coloring proof of Aggarwal s Theorem Pawel Zylinski Institute of Mathematics University of Gdansk 80952 Gdansk Poland pz@ Submitted Sep 29 2005 Accepted Feb 27 2006 Published Mar 7 2006 Mathematics Subject Classifications 05C15 05C90 Abstract We prove that L n hJ vertex guards are always sufficient to see the entire interior of an n-vertex orthogonal polygon P with an arbitrary number h of holes provided that there exists a quadrilateralization whose dual graph is a cactus. Our proof is based upon 4-coloring of a quadrilateralization graph and it is similar to that of Kahn and others for orthogonal polygons without holes. Consequently we provide an alternate proof of Aggarwal s theorem asserting that L n hJ vertex guards always suffice to cover any n-vertex orthogonal polygon with h 2 holes. 1 Introduction The art gallery problem was originally posed by Victor Klee in 1973 as the question of determining the minimum number of guards sufficient to see every point of the interior of an n-vertex simple polygon. The guard was assumed to be a stationary point which can see any point that can be connected to it with a line segment within the polygon. The first result was due to Chvátal 2 who proved that LnJ guards are sometimes necessary and always sufficient to cover a polygon with n vertices. His entirely combinatorial proof started with an arbitrary triangulation of the polygon and then cut off a small piece for the inductive step. Three years later in 1978 Fisk 3 offered a simpler proof of Chvátal s result based upon a 3-coloring of the triangulation graph. Since then many different variations of this problem have arisen see 7 8 for more details. An orthogonal gallery is a polygon whose edges are either horizontal or vertical see Fig. 1 a . An orthogonal gallery with holes is an orthogonal polygon P enclosing some other orthogonal polygons H1 . Hh known as the holes. None of the boundaries of Supported by the State