Narrow Results

We present algorithms for the approximation of a convex n-gon by a convex k-gon (k<n) which inscribes or circumscribes the original polygon. Our algorithms run in O(n+(n-k) log n) time and are easy to implement. Their accuracy, in the sense of area-difference, is analyzed and shown to be of the best order possible for a general algorithm. In particular, this analysis settles a question raised by O'Rourke on the performance of the approximation algorithm of Dori and Ben-Bassat.

Assume a robot that, when directed to move in a particular direction, is guaranteed to move inside a cone of angle α centered at the specified direction. The robot has to reach a convex polygonal goal G, while avoiding polygonal obstacles of complexity n. We show that the complexity of the safe region, from where the robot can reach the goal with a single motion with uncertainty α, is O(m+n), and can be computed in time O((m+n) log (m+n)), if α is assumed constant.

Given two convex polygons P and Q in the plane that are free to translate and rotate, a convex packing of them is the convex hull of a placement of P and a placement of Q whose interiors do not intersect. A minimum area convex packing of P and Q is one whose area is minimized. The problem of designing a deterministic algorithm for finding a minimum area convex packing of two convex polygons has remained open. We address this problem by first studying the contact configurations between P and Q and their algebraic structures. Crucial geometric and algebraic properties on the area function are then derived and analyzed which enable us to successfully discretize the search space. This discretization, together with a delicate algorithmic design and careful complexity analysis, allows us to develop an efficient O((n + m)nm) time deterministic algorithm for finding a true minimum area convex packing of P and Q, where n and m are the numbers of vertices of P and Q, respectively.

Two points a and b are said to be L-visible among a set of polygonal obstacles if the length of the shortest path from a to b avoiding these obstacles is no more than L. For a given convex polygon P with n vertices, Gewali et al.¹ addressed the guard placement problem on the boundary of P that covers the maximum area outside to the polygon under L-visibility with P as obstacle. Their proposed algorithm runs in O(n) time if , where π(P) denotes the perimeter of P. They conjectured that if , then the problem can be solved in subquadratic time. In this paper, we settle the conjecture in the affirmative sense, by proposing an easy to implement linear time algorithm for any arbitrary value of L.

Let R and B be two disjoint sets of red points and blue points in the plane, respectively, such that no three points of R ∪ B are collinear, and let a,b and g be positive integers. We show that if ag ≤ |R| < (a + 1)g and bg ≤ |B| < (b + 1)g, then we can subdivide the plane into g convex polygons so that every open convex polygon contains exactly a red points and b blue points and that the remaining points lie on the boundary of the subdivision. This is a generalization of equitable subdivision of ag red points and bg blue points in the plane.

This paper considers a problem of locating the given number of disks into a container so that the area covered by the disks is maximized. In the problem, the radii of the disks can be changed arbitrarily unless they overlap outside of the container, and the disks are allowed to overlap with each other. We present an approximation algorithm for this problem assuming that the container is a convex polygon. Our algorithm achieves approximation ratio (0.78 - ϵ) for any small ϵ > 0. Since the computation time of our algorithm depends on the number of corners of the convex polygon exponentially, we also give a heuristic to reduce the number of corners.

This paper first presents an algorithm for enumerating all the integer-grid points in a given convex m-gon in O(K + m + log n) time where K is the number of such grid points and n is the dimension of the m-gon, i.e., the shorter length of the horizontal and vertical sides of an axis-parallel rectangle enclosing the m-gon. The paper next gives a simple algorithm which solves a two-variable integer programming problem with m constraints in O(m log m + log n) time where n is the dimension of a convex polygon corresponding to the feasible solution space. This improves the best known algorithm in complexity and simplicity. The paper finally presents algorithms for counting the number of grid points in a triangle or a simple polygon.