An efficient algorithm for guard placement in polygons with holes

In this paper we consider the problem of placing guards to supervise an art gallery with holes. No gallery withn vertices andh holes requires more than [(n+h)/3] guards. For some galleries this number of guards is necessary. We present an algorithm which places the [(n+h)/3] guards inO(n ²) time. Work by the first author was done at Rutgers University and was supported in part by a DIMACS research assistantship. The second author was supported in part by National Science Foundation Grants CCR-88-03549 and CCR-91-04732.     

L1-embeddability of rectilinear polygons with holes

The following result is established. LetP be a rectilinear polygon whose all holes are rectangles. If there are no maximal cut segments ofP whose end-points lie on the boundary of different holes thenP isL ₁-embeddable.Supported by the Alexander von Humboldt Stiftung     

Wrapping polygons in polygons

This paper is developed toI ₂(2g).c-geometries, namely, point-line-plane structures where planes are generalized 2g-gons with exactly two lines on every point and any two intersecting lines belong to a unique plane.I ₂(2g).c-geometries appear in several contexts, sometimes in connection with sporadic simple groups. Many of them are homomorphic images of truncations of geometries belonging to Coxeter diagrams. TheI ₂(2g).c-geometries obtained in this way may be regarded as the standard ones. We characterize them in this paper. For everyI ₂(2g).c-geometry , we define a numberw(), which counts the number of times we need to walk around a 2g-gon contained in a plane of , building up a wall of planes around it, before closing the wall. We prove thatw()=1 if and only if is standard and we apply that result to a number of special cases.     

Tiling polygons with parallelograms

Under what conditions can a simple polygon be tiled by parallelograms? In this paper we give matching necessary and sufficient conditions on the polygon to be tilable and characterize the set of possible tilings. We also provide an efficient algorithm for constructing a tiling.     

Generalized polygons with valuation

Archiv der Mathematik -     

Point retrieval for polygons

We present a solution to the following polygon retrieval problem: given a set of n points on the plane, build a data structure so that for any query polygon P the set of points lying in P can be retrieved efficiently. Our solution uses space O(n²) and reports the s points lying in a k-sided polygon P in time O(k log n + s).     

Extremal problems for convex polygons

Consider a convex polygon V _n with n sides, perimeter P _n , diameter D _n , area A _n , sum of distances between vertices S _n and width W _n . Minimizing or maximizing any of these quantities while fixing another defines 10 pairs of extremal polygon problems (one of which usually has a trivial solution or no solution at all). We survey research on these problems, which uses geometrical reasoning increasingly complemented by global optimization methods. Numerous open problems are mentioned, as well as series of test problems for global optimization and non-linear programming codes.     

Finding largest small polygons with GloptiPoly

A small polygon is a convex polygon of unit diameter. We are interested in small polygons which have the largest area for a given number of vertices n. Many instances are already solved in the literature, namely for all odd n, and for n = 4, 6 and 8. Thus, for even n ≥ 10, instances of this problem remain open. Finding those largest small polygons can be formulated as nonconvex quadratic programming problems which can challenge state-of-the-art global optimization algorithms. We show that a recently developed technique for global polynomial optimization, based on a semidefinite programming approach to the generalized problem of moments and implemented in the public-domain Matlab package GloptiPoly, can successfully find largest small polygons for n = 10 and n = 12. Therefore this significantly improves existing results in the domain. When coupled with accurate convex conic solvers, GloptiPoly can provide numerical guarantees of global optimality, as well as rigorous guarantees relying on interval arithmetic.     

Tilings of polygons with similar triangles

We prove that if a polygonP is decomposed into finitely many similar triangles then the tangents of the angles of these triangles are algebraic over the field generated by the coordinates of the vertices ofP. IfP is a rectangle then, apart from four sporadic cases, the triangles of the decomposition must be right triangles. Three of these sporadic triangles tile the square. In any other decomposition of the square into similar triangles, the decomposition consists of right triangles with an acute angle such that tan is a totally positive algebraic number. Most of the proofs are based on the following general theorem: if a convex polygonP is decomposed into finitely many triangles (not necessarily similar) then the coordinate system can be chosen in such a way that the coordinates of the vertices ofP belong to the field generated by the cotangents of the angles of the triangles in the decomposition.This work was completed while the author had a visiting position at the Mathematical Institute of the Hungarian Academy of Sciences.     

Covering the plane with convex polygons

It is proved that for any centrally symmetric convex polygonal domainP and for any natural numberr, there exists a constantk=k(P, r) such that anyk-fold covering of the plane with translates ofP can be split intor simple coverings.     

Discrepancy with respect to convex polygons

We study the problem of discrepancy of finite point sets in the unit square with respect to convex polygons, when the directions of the edges are fixed, when the number of edges is bounded, as well as when no such restrictions are imposed. In all three cases, we obtain estimates for the supremum norm that are very close to best possible.     

Generalized polygons with split Levi factors

¶Theorem. Suppose that the group G has an irreducible spherical BN-pair of rank 2. If for every 2-transitive subgroup L of the Levi factors of G the one-point stabilizer B splits as B = U 2 T with [B, B] = U, then the Tits-building associated to the BN-pair of G is Moufang.¶¶This implies in particular that a simple group G with a spherical BN-pair of rank 2 whose Levi factors are permutation equivalent to subgroups of PGL₂(K) or the Suzuki group GSz(K) is (essentially) classical.