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] .     

Three problems about simple polygons

We give three related algorithmic results concerning a simple polygon P:

1. Improving a series of previous work, we show how to find a largest pair of disjoint congruent disks inside P in linear expected time.

2. As a subroutine for the above result, we show how to find the convex hull of any given subset of the vertices of P in linear worst-case time.

3. More generally, we show how to compute a triangulation of any given subset of the vertices or edges of P in almost linear time.

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.     

A Helly-type theorem for simple polygons

Let be a family of simple polygons in the plane. If every three (not necessarily distinct) members of have a simply connected union and every two members of have a nonempty intersection, then {P:P in } . Applying the result to a finite family of orthogonally convex polygons, the set {C:C in } will be another orthogonally convex polygon, and, in certain circumstances, the dimension of this intersection can be determined.Supported in part by NSF grant DMS-9207019.     

Kinetic collision detection between two simple polygons

We design a kinetic data structure for detecting collisions between two simple polygons in motion. In order to do so, we create a planar subdivision of the free space between the two polygons, called the external relative geodesic triangulation, which certifies their disjointness. We show how this subdivision can be maintained as a kinetic data structure when the polygons are moving, and analyze its performance in the kinetic setting.     

On the perimeters of simple polygons contained in a disk

A simple n-gon is a polygon with n edges with each vertex belonging to exactly two edges and every other point belonging to at most one edge. Brass et?al. (Research Problems in Discrete Geometry, 2005) asked the following question: For n ???5 odd, what is the maximum perimeter of a simple n-gon contained in a Euclidean unit disk? In 2009, Audet et?al. (Discrete Comput Geom 41:208?C215) answered this question, and showed that the optimal configuration is an isosceles triangle with a multiple edge, inscribed in the disk. In this note we give a shorter and simpler proof of their result, which we generalize also for hyperbolic disks, and for spherical disks of sufficiently small radii.     

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.     

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.     

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.     

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.     

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.     

A new necessary condition for the vertex visibility graphs of simple polygons

A new necessary condition conjectured by Everett [2], which is essentially a stronger version of a necessary condition by Ghosh [3], for a graph to be the vertex visibility graph of a simple polygon is established. This work was carried out while G. Srinivasaraghavan was at the Indian Institute of Technology, Kanpur, India.     

Shortest Paths with Shortest Detours

This paper is concerned with a biobjective routing problem, called the shortest path with shortest detour problem, in which the length of a route is minimized as one criterion and, as second, the maximal length of a detour route if the chosen route is blocked is minimized. Furthermore, the relation to robust optimization is pointed out, and we present a new polynomial time algorithm, which computes a minimal complete set of efficient paths for the shortest path with shortest detour problem. Moreover, we show that the number of nondominated points is bounded by the number of arcs in the graph.     

Dynamic programming in cricket: choosing a night watchman

In cricket, when a batsman is dismissed towards the end of a day's play, he is often replaced by a lower-order batsman (a ‘night watchman’), in the hope that the remaining recognised batsmen can start their innings on the following day. A dynamic programming analysis suggests that the common practice of using a lower-order batsman is often sub-optimal. Towards the end of a day's play, when the conventional wisdom seems to be to use a night watchman, it may be best to send in the next recognised batsman in the batting order. Sending in a night watchman may be good judgement when there are several recognised batsman and several lower order batsmen still to play (say four of each). However, with smaller numbers (two of each, for example), then, with very few overs left to play, it may be better to send in a recognised batsman.