International Journal of Computational Geometry & Applications

Assume that an ordered set of imprecise points is given, where each point is specified by a region in which the point may lie. This set determines an imprecise polygon. We show that it is NP-hard to decide whether it is possible to place the points inside their regions in such a way that the resulting polygon is simple. Furthermore, it is NP-hard to minimize the length of a simple tour visiting the regions in order, when the connections between consecutive regions are not needed to be straight line segments. We also present two linear-time algorithms to compute the shortest and longest possible tour for the case where the polygon is not required to be simple and the regions are squares.

Given a set of n points in the plane, we show how to compute various enclosing isosceles triangles where different parameters such as area or perimeter are optimized. We then study a 3-dimensional version of the problem where we enclose a point set with a cone of fixed apex angle α.

Boundary approximation of planar shapes by circular arcs has quantitative and qualitative advantages compared to using straight-line segments. We demonstrate this by way of three basic and frequent computations on shapes – convex hull, decomposition, and medial axis. In particular, we propose a novel medial axis algorithm that beats existing methods in simplicity and practicality, and at the same time guarantees convergence to the medial axis of the original shape.

In an orthogonal projection of a convex polyhedron P, the visibility ratio of a face f (of an edge e) is the ratio of orthogonally projected area of f (length of e) and its actual area (length). In this paper, we give algorithms for nice projections of P such that the minimum visibility ratio among all visible faces (among all visible edges) is maximized.

Given a planar polygon (or chain) with a list of edges {e₁, e₂, e₃, …, e_n-1, e_n}, we examine the effect of several operations that permute this edge list, resulting in the formation of a new polygon. The main operations that we consider are: reversals which involve inverting the order of a sublist, transpositions which involve interchanging subchains (sublists), and edge-swaps which are a special case and involve interchanging two consecutive edges. When each edge of the given polygon has also been assigned a direction we say that the polygon is signed. In this case any edge involved in a reversal changes direction.

We show that a star-shaped polygon can be convexified using O(n²) edge-swaps, while maintaining simplicity, and that this is tight in the worst case. We show that determining whether a signed polygon P can be transformed to one that has rotational or mirror symmetry with P, using transpositions, takes Θ(n log n) time. We prove that the problem of deciding whether transpositions can modify a polygon to fit inside a rectangle is weakly NP-complete. Finally we give an O(n log n) time algorithm to compute the maximum endpoint distance for an oriented chain.

This article develops an algorithm for a group of guards statically positioned in a non-convex polygonal environment with holes. Each guard possesses a single searchlight, a ray sensor which can rotate about the guard's position but cannot penetrate the boundary of the environment. A point is detected by a searchlight if and only if the point is on the ray at some instant. Targets are points which move arbitrarily fast. The objective of the proposed algorithm is to compute a schedule to rotate a set of searchlights in such a way that any target in an environment will necessarily be detected in finite time. This is known as the Searchlight Scheduling Problem and was described originally in 1990 by Sugihara et al. We take an approach known as exact cell decomposition in the motion planning literature. The algorithm operates by decomposing the searchlights' joint configuration space and the environment, and then by constructing a so-called information graph. Searching the information graph for a path between desired states yields a search schedule. We also introduce a new problem called the ϕ-Searchlight Scheduling Problem in which ϕ-searchlights sense not just along a ray, but over a finite field of view. We show that our results for searchlight scheduling can be directly extended for ϕ-searchlight scheduling. Proofs of completeness, complexity bounds, and computed examples are presented.