The authors show that for every fixed $\delta > 0$ the following holds: If F is a union of n triangles, all of whose angles are at least $\delta $, then the complement of F has $O(n)$ connected components and the boundary of F consists of $O(n\log \log n)$ straight segments (where the constants of proportionality depend on $\delta $). This latter complexity becomes linear if all triangles are of roughly the same size or if they are all infinite wedges.

It is shown that for every fixed delta >0 the following holds: if F is a union of n triangles, all of whose angles are at least delta , then the complement of F has O(n) connected components, and the boundary of F consists of O(n log log n) segments. This latter complexity becomes linear if all triangles are of roughly the same size or if they are all infinite wedges. A randomized algorithm that computes F in expected time O(n2/sup alpha (n)/ log n) is given. Several applications of these results are presented.>

We show that, under reasonable assumptions, any collision-avoiding motion planning problem for a moving system with two degrees of freedom can be solved in time Ο(λs(n) log2n), where n is the number of collision constraints imposed on the system, s is a fixed parameter depending e.g. on the maximum algebraic degree of these constraints, and λs(n) is the (almost linear) maximum length of (n,s) Davenport Schinzel sequences. This follows from an upper bound of Ο(λs(n)) that we establish for the combinatorial complexity of a single connected component of the space of all free placements of the moving system. Although our study is motivated by motion planning, it is actually a study of topological, combinatorial, and algorithmic issues involving a single face in an arrangement of curves. Our results thus extend beyond the area of motion planning, and have applications in many other areas.

We present an Ο(n2) algorithm for planning a coordinated collision-free motion of two independent robot systems of certain kinds, each having two degrees of freedom, which move in the plane amidst polygonal obstacles having a total of n corners. We exemplify our technique in the case of two “planar Stanford arms”, but also discuss the case of two discs or convex translating objects. The algorithm improves previous algorithms for this kind of problems, and can be extended to a fairly simple general technique for obtaining efficient coordinated motion planning algorithms.

We present here a new and efficient algorithm for planning collision-free motion of a rod in the plane amidst polygonal obstacles. The algorithm calculates the boundary of the space of free positions of the rod, and then uses this boundary for determining the existence of required motions. The algorithm runs in time Ο(K log n) where n is the number of obstacle corners and where K is the total number of pairs of obstacle walls or corners lying from one another at distance less than or equal to the length of the rod. Since K = Ο(n2), the algorithm has the same worst-case complexity as the best previously developed algorithm of Leven and Sharir [LS1], but if the obstacles are not too cluttered together it will run much more efficiently.

We present efficient algorithms for the following geometric problems: (i) Preprocessing of a 2-D polyhedral terrain so as to support fast ray shooting queries from a fixed point. (ii) Determining whether two disjoint interlocking simple polygons can be separated from one another by a sequence of translations. (iii) Determining whether a given convex polygon can be translated and rotated so as to fit into another given polygonal region. (iv) Motion planning for a convex polygon in the plane amidst polygonal barriers. All our algorithms make use of Davenport Schinzel sequences and on some generalizations of them; these sequences are a powerful combinatorial tool applicable in contexts which involve the calculation of the pointwise maximum or minimum of a collection of functions.