We present an algorithm that constructs a strictly convex quadrilateral mesh for a simple polygonal region in which no newly created angle is smaller than D(18.43) (=arctan(1/3)). This is the first known result on quadrilateral mesh generation with a provable guarantee on the minimum angle.

We show that the space of polygonizations of a fixed planar point set $S$ of $n$ points is connected by $O(n^2)$ ``moves'' between simple polygons. Each move is composed of a sequence of atomic moves called ``stretches'' and ``twangs''. These atomic moves walk between weakly simple ``polygonal wraps'' of $S$. These moves show promise to serve as a basis for generating random polygons.

We study the problem of determining whether a manufactured disk of certain radius r is within tolerance. More precisely, we present algorithms that, given a set of n probe points on the surface of the manufactured object, compute the thinnest annulus whose outer (or inner, or median) radius is r and that contains all the probe points. Our algorithms run in O(nlogn) time.

The motion planning problem of an object with two degrees of freedom moving in the plane can be stated as follows: Given a set of polygonal obstacles in the plane, and a two-dimensional mobile object B with two degrees of freedom, determine if it is possible to move B from a start position to a final position while avoiding the obstacles. If so, plan a path for such a motion. Techniques from computational geometry have been used to develop exact algorithms for this fundamental case of motion planning. In this paper we obtain optimal mesh implementations of two different methods for planning motion in the plane. We do this by first presenting optimal mesh algorithms for some geometric problems that, in addition to being important substeps in motion planning, have numerous independent applications in computational geometry. In particular, we first show that the Voronoi diagram of a set of n nonintersecting (except possibly at endpoints) line segments in the plane can be constructed in O(√ n) time on a √ n × √ n mesh, which is optimal for the mesh. Consequently, we obtain an optimal mesh implementation of the sequential motion planning algorithm described by Ó′Dúlainy and Yap (J. Algorithms 6 (1985), 104-111); in other words, given a disc B and a polygonal obstacle set of size n, we can plan a path (if it exists) for the motion of B from a start position to a final position in O(√ n) time on a mesh of size n. We also show that the shortest path motion between a start position and a final position for a convex object B (of constant size) moving among convex polygonal obstacles of total size n can be found in O(n) time on an n × n mesh, which is worst-case optimal.

In this paper, we present an optimal parallel randomized algorithm for the Voronoi diagram of a set of n non-intersecting (except possibly at endpoints) line segments in the plane. Our algorithm runs in O(logn) time with very high probability and uses O(n) processors on a CRCW PRAM. This algorithm is optimal in terms of P.T bounds since the sequential time bound for this problem is Ω(nlogn). Our algorithm improves by an O(logn) factor the previously best known deterministic parallel algorithm which runs in O(log2n) time using O(n) processors. We obtain this result by using random sampling at “two stages” of our algorithm and using efficient randomized search techniques. This technique gives a direct optimal algorithm for the Voronoi diagram of points as well (all other optimal parallel algorithms for this problem use reduction from the 3-d convex hull construction).