On separating two simple polygons by a single translation

LetP andQ be two disjoint simple polygons havingn sides each. We present an algorithm which determines whetherQ can be moved by a single translation to a position sufficiently far fromP, and which produces all such motions if they exist. The algorithm runs in timeO(t(n)) wheret(n) is the time needed to triangulate ann-sided polygon. Since Tarjan and Van Wyk have recently shown thatt(n)=O(n log logn) this improves the previous best result for this problem which wasO(n logn) even after triangulation.This research was supported by NSERC Grant A9293, FCAR Grant EQ-1678, and a Killam Fellowship from the Canada Council.     

On recognizing and characterizing visibility graphs of simple polygons

In this paper we establish four necessary conditions for recognizing visibility graphs of simple polygons and conjecture that these conditions are sufficient. We present an 0(n²)-time algorithm for testing the first and second necessary conditions and leave it open whether the third and fourth necessary conditions can be tested in polynomial time. We also show that visibility graphs of simple polygons do not possess the characteristics of a few special classes of graphs Part of this work was done when the author visited the John Hopkins University and was Supported by NSF Grant DCR83-51468 and a grant from IBM.     

Large triangles contained in the unit disk of a Minkowski plane

We prove that the unit disk C of an arbitrary Minkowski plane contains an equilateral triangle in at least one of the orientations, whose oriented side lengths are ${\frac{3}{2}}$ . We also prove that C permits to inscribe a triangle whose sides are of lengths at least ${\frac{3}{2}}$ in the positive orientation, or that they are of lengths at least ${\frac{3}{2}}$ in the negative orientation. The ratio ${\frac{3}{2}}$ in both the theorems is best possible.     

Multiple-guard kernels of simple polygons

We study a generalization of the kernel of a polygon. A polygonP isk guardable if there arek points inP such that, for all pointsp inP, there is at least one of thek points that seesp. We call thek points ak-guard set ofP and thek-kernel of a polygonP is the union of allk-guard sets ofP. The usual definition of the kernel of a polygon is now the one-kernel in this notation.We show that the two-kernel of a simple polygonP withn edges has O(n⁴) components and that there are polygons whose two-kernel has (n) components. Moreover, we show that the components of the two-kernel of a simple polygon can be paired in a natural manner which implies that the two-kernel of a simple polygon has either one component or an even number of components. Finally, we consider the question of whether there is a non-star-shaped simple polygonP such that 2-kernel(P) = P. We show that when the two-kernel has only one component, it contains a hole; hence, the two-kernel of a simple polygonP is neverP itself. For everyk 1, there are, however, polygonsP _k with holes such thatk-kernel(P_k) = P_k.This work was supported under grant No. Ot 64/8-1, Diskrete Probleme from the the Deutsche Forschungsgemeinschaft, grants from the Natural Sciences and Engineering Council of Canada, from the Information Technology Research Centre of Ontario, and from the Research Grants Council of Hong Kong.     

Efficient visibility queries in simple polygons

We present a method of decomposing a simple polygon that allows the preprocessing of the polygon to efficiently answer visibility queries of various forms in an output sensitive manner. Using O(n³logn) preprocessing time and O(n³) space, we can, given a query point q inside or outside an n vertex polygon, recover the visibility polygon of q in O(logn+k) time, where k is the size of the visibility polygon, and recover the number of vertices visible from q in O(logn) time.

The key notion behind the decomposition is the succinct representation of visibility regions, and tight bounds on the number of such regions. These techniques are extended to handle other types of queries, such as visibility of fixed points other than the polygon vertices, and for visibility from a line segment rather than a point. Some of these results have been obtained independently by Guibas, Motwani and Raghavan [18] .     

Shortest watchman routes in simple polygons

In this paper we present an O(n ⁴, log logn) algorithm to find a shortest watchman route in a simple polygon through a point,s, in its boundary. A watchman route is a route such that each point in the interior of the polygon is visible from at least one point along the route. S. Ntafos was supported in part by a grant from Texas Instruments, Inc.     

Separating two simple polygons by a sequence of translations

LetP andQ be two disjoint simple polygons havingm andn sides, respectively. We present an algorithm which determines whetherQ can be moved by a sequence of translations to a position sufficiently far fromP without colliding withP, and which produces such a motion if it exists. Our algorithm runs in timeO(mn(mn) logm logn) where (k) is the extremely slowly growing inverse Ackermann's function. Since in the worst case (mn) translations may be necessary to separateQ fromP, our algorithm is close to optimal.Work on this paper by the first author has been supported by National Science Foundation Grant No. DMS-8501947. Work on this paper by the second author has been supported by Office of Naval Research Grant No. N00014-82-K-0381, National Science Foundation Grant No. NSP-DCR-83-20085, and by grants from the Digital Equipment Corporation, and the IBM Corporation. Work by the second and third authors has also been supported by a grant from the joint Ramot-Israeli Ministry of Industry Foundation. Part of the work on this paper has been carried out at the Workshop on Movable Separability of Sets at the Bellairs Research Institute of McGill University, Barbados, February 1986.     

Decomposing a simple polygon into pseudo-triangles and convex polygons

In this paper we consider the problem of decomposing a simple polygon into subpolygons that exclusively use vertices of the given polygon. We allow two types of subpolygons: pseudo-triangles and convex polygons. We call the resulting decomposition PT-convex. We are interested in minimum decompositions, i.e., in decomposing the input polygon into the least number of subpolygons. Allowing subpolygons of one of two types has the potential to reduce the complexity of the resulting decomposition considerably.The problem of decomposing a simple polygon into the least number of convex polygons has been considered. We extend a dynamic-programming algorithm of Keil and Snoeyink for that problem to the case that both convex polygons and pseudo-triangles are allowed. Our algorithm determines such a decomposition in O(n³) time and space, where n is the number of the vertices of the polygon.     

On perimeters of sections of convex polytopes

In his book “Geometric Tomography” Richard Gardner asks the following question. Let P and Q be origin-symmetric convex bodies in R³ whose sections by any plane through the origin have equal perimeters. Is it true that P=Q? We show that the answer is “Yes” in the class of origin-symmetric convex polytopes. The problem is treated in the general case of Rn.     

On the volume product of polygons

We present a method that allows us to prove that the volume product of polygons in ℝ² with at most n vertices is bounded from above by the volume product of regular polygons with n vertices. The same method shows that the volume product of polygons is bounded from below by the volume product of triangles (or parallelograms in the centrally symmetric case). These last results give a new proof of theorems of K. Mahler. The cases of equality are completely described.     

On the modality of convex polygons

Under two definitions of random convex polygons, the expected modality of a random convex polygon grows without bound as the number of vertices grows. This refutes a conjecture of Aggarwal and Melville.     

On order in generalized polygons

Geometriae Dedicata -     

On polygons circumscribing a closed convex curve

Length and area formulas for closed polygonal curves are derived, as functions of the vertex angles and the distances to the lines containing the sides. Applications of the formulas are made to the class of polygons which circumscribe a given convex curve and have a prescribed sequence of vertex angles. Geometric conditions are given for polygons in the class which have extremal perimeter or area.     

On a measure of asymmetry for Reuleaux polygons

In a previous paper, we showed that for regular Reuleaux polygons R _n the equality ${{\rm as}_\infty(R_n) = 1/(2\cos \frac\pi{2n} -1)}$ holds, where ${{\rm as}_\infty(\cdot)}$ denotes the Minkowski measure of asymmetry for convex bodies, and ${{\rm as}_\infty(K)\leq \frac 12(\sqrt{3}+1)}$ for all convex domains K of constant width, with equality holds iff K is a Reuleaux triangle. In this paper, we investigate the Minkowski measures of asymmetry among all Reuleaux polygons of order n and show that regular Reuleaux polygons of order n (n ?? 3 and odd) have the minimal Minkowski measure of asymmetry.