Pointed binary encompassing trees: Simple and optimal

For n disjoint line segments in the plane we construct in optimal O(nlogn) time and linear space an encompassing tree of maximum degree three such that at every vertex v all edges of the tree that are incident to v lie in a halfplane bounded by the line through the input segment which v is an endpoint of. In particular, this tree is pointed since every vertex has an incident angle greater than π. Such a pointed binary tree can be augmented to a minimum pseudo-triangulation. It follows that every set of disjoint line segments in the plane has a constrained minimum pseudo-triangulation whose maximum vertex degree is bounded by a constant.     

A Pedestrian Approach to Ray Shooting: Shoot a Ray, Take a Walk

We propose a very simple ray-shooting algorithm, whose only data structure is a triangulation. The query algorithm, after locating the triangle containing the origin of the ray, walks along the ray, advancing from one triangle to a neighboring one until the polygon boundary is reached. The key result of the paper is a Steiner triangulation of a simple polygon with the property that a ray can intersect at most O(log n) triangles before reaching the polygon boundary. We are able to compute such a triangulation in linear sequential time, or in O(log n) parallel time using O(n/log n) processors. This gives a simple, yet optimal, ray-shooting algorithm for a simple polygon. Using a well-known technique, we can extend our triangulation procedure to a multiconnected polygon with k components and n vertices, so that a ray intersects at most O(√k log n) triangles.     

AnO(n logn) algorithm for the voronoi diagram of a set of simple curve segments

LetX be a given set ofn circular and straight line segments in the plane where two segments may interest only at their endpoints. We introduce a new technique that computes the Voronoi diagram ofX inO(n logn) time. This result improves on several previous algorithms for special cases of the problem. The new algorithm is relatively simple, an important factor for the numerous practical applications of the Voronoi diagram.This work was supported by NSF Grants No. DCR-84-01898 and No. DCR-84-01633.     

Polygonizations of point sets in the plane

We examine the different ways a set ofn points in the plane can be connected to form a simple polygon. Such a connection is called apolygonization of the points. For some point sets the number of polygonizations is exponential in the number of points. For this reason we restrict our attention to star-shaped polygons whose kernels have nonempty interiors; these are callednondegenerate star-shaped polygons.We develop an algorithm and data structure for determining the nondegenerate star-shaped polygonizations of a set ofn points in the plane. We do this by first constructing an arrangement of line segments from the point set. The regions in the arrangement correspond to the kernels of the nondegenerate star-shaped polygons whose vertices are the originaln points. To obtain the data structure representing this arrangement, we show how to modify data structures for arrangements of lines in the plane. This data structure can be computed inO(n ⁴) time and space. By visiting the regions in this data structure in a carefully chosen order, we can compute the polygon associated with each region inO(n) time, yielding a total computation time ofO(n ⁵) to compute a complete list ofO(n ⁴) nondegenerate star-shaped polygonizations of the set ofn points.     

Computing minimum-area rectilinear convex hull and L-shape

We study the problems of computing two non-convex enclosing shapes with the minimum area; the L-shape and the rectilinear convex hull. Given a set of n points in the plane, we find an L-shape enclosing the points or a rectilinear convex hull of the point set with minimum area over all orientations. We show that the minimum enclosing shapes for fixed orientations change combinatorially at most O(n) times while rotating the coordinate system. Based on this, we propose efficient algorithms that compute both shapes with the minimum area over all orientations. The algorithms provide an efficient way of maintaining the set of extremal points, or the staircase, while rotating the coordinate system, and compute both minimum enclosing shapes in O(n²) time and O(n) space. We also show that the time complexity of maintaining the staircase can be improved if we use more space.     

Polyhedral line transversals in space

Algorithms are developed for determining if a set of polyhedral objects inR ³ can be intersected by a common transversal (stabbing) line. It can be determined inO(n logn) time if a set ofn line segments in space has a line transversal, and such a transversal can be found in the same time bound. For a set of polyhedra with a total ofn vertices, we give anO(n ⁴ logn) algorithm for determining the existence of, and computing, a line transversal. Helly-type theorems for lines and segments are also given. In particular, it is shown that if every six of a set of lines in space are intersected by a common transversal, then the entire set has a common transversal.     

Enclosing a Set of Objects by Two Minimum Area Rectangles

In this paper, we face the problem of computing an enclosing pair of axis-parallel rectangles of a set of polygonal objects in the plane, serving as a simple container. We propose anO(nα(n)log n) worst-case time algorithm, where α( ) is the inverse Ackermann's function, for finding, given a setMof points, segments and polygons defined bynvertices, a pair of axis-parallel rectangles (s, t) such thats∪tencloses all objects inMand area(s)+area(t) is minimum. The algorithm works inO(nα(n) log log n) worst-case space. Moreover, we prove an Ω(n log n) lower bound for the one-dimensional version of the problem. We also show that for the special case of enclosing a set of polygons with axis-parallel sides, our algorithm runs in optimal worst-case timeO(n log n), using worst-case spaceO(n log log n).     

Boundary evaluation algorithms for Minkowski combinations of complex sets using topological analysis of implicit curves

Minkowski geometric algebra is concerned with sets in the complex plane that are generated by algebraic combinations of complex values varying independently over given sets in ℂ. This algebra provides an extension of real interval arithmetic to sets of complex numbers, and has applications in computer graphics and image analysis, geometrical optics, and dynamical stability analysis. Algorithms to compute the boundaries of Minkowski sets usually invoke redundant segmentations of the operand-set boundaries, guided by a “matching” criterion. This generates a superset of the true Minkowski set boundary, which must be extracted by the laborious process of identifying and culling interior edges, and properly organizing the remaining edges. We propose a new approach, whereby the matching condition is regarded as an implicit curve in the space ℝⁿ whose coordinates are boundary parameters for the n given sets. Analysis of the topological configuration of this curve facilitates the identification of sets of segments on the operand boundaries that generate boundary segments of the Minkowski set, and rejection of certain sets that satisfy the matching criterion but yield only interior edges. Geometrical relations between the operand set boundaries and the implicit curve in ℝⁿ are derived, and the use of the method in the context of Minkowski sums, products, planar swept volumes, and Horner terms is described.     

How to Cut Pseudoparabolas into Segments

Let Γ be a collection of unbounded x -monotone Jordan arcs intersecting at most twice each other, which we call pseudoparabolas, since two axis parallel parabolas intersect at most twice. We investigate how to cut pseudoparabolas into the minimum number of curve segments so that each pair of segments intersect at most once. We give an Ω( n ^4/3 ) lower bound and O(n ^5/3 ) upper bound on the number of cuts. We give the same bounds for an arrangement of circles. Applying the upper bound, we give an O(n ^23/12 ) bound on the complexity of a level in an arrangement of pseudoparabolas, and an O(n ^11/6 ) bound on the complexity of a combinatorially concave chain of pseudoparabolas. We also give some upper bounds on the number of transitions of the minimum weight matroid base when the weight of each element changes as a quadratic function of a single parameter. Received January 17, 1996, and in revised form November 7, 1996.     

Approximation of an open polygonal curve with a minimum number of circular arcs and biarcs

We present an algorithm for approximating a given open polygonal curve with a minimum number of circular arcs. In computer-aided manufacturing environments, the paths of cutting tools are usually described with circular arcs and straight line segments. Greedy algorithms for approximating a polygonal curve with curves of higher order can be found in the literature. Without theoretical bounds it is difficult to say anything about the quality of these algorithms. We present an algorithm which finds a series of circular arcs that approximate the polygonal curve while remaining within a given tolerance region. This series contains the minimum number of arcs of any such series. Our algorithm takes O(n²logn) time for an original polygonal chain with n vertices. Using a similar approach, we design an algorithm with a runtime of O(n²logn), for computing a tangent-continuous approximation with the minimum number of biarcs, for a sequence of points with given tangent directions.     

Improved heuristics for the minimum weight triangulation problem

Given a planar point setS, a triangulation ofS is a maximal set of non-intersecting line segments connecting the points. The minimum weight triangulation problem is to find a triangulation ofS such that the sum of the lengths of the line segments in it is the smallest. No polynomial time algorithm is known to produce the optimal or even a constant approximation of the optimal solution, and it is also unknown whether the problem is NP-hard. In this paper, we propose two improved heuristics, which triangulate a set ofn points in a plane inO(n ³) time and never do worse than the minimum spanning tree triangulation algorithm given by Lingas and the greedy spanning tree triangulation algorithm given by Heath and Pemmaraju. These two algorithms both produce an optimal triangulation if the points are the vertices of a convex polygon, and also do the same in some special cases.     

A note on maximal triangle-free graphs

We show that a maximal triangle-free graph on n vertices with minimum degree δ contains an independent set of 3δ ? n vertices which have identical neighborhoods. This yields a simple proof that if the binding number of a graph is at least 3/2 then it has a triangle. This was conjectured originally by Woodall. © 1993 John Wiley & Sons, Inc.     

Multiterminal xcut problems

Ani-j xcut of a setV={1, ...,n} is defined to be a partition ofV into two disjoint nonempty subsets such that bothi andj are contained in the same subset. When partitions are associated with costs, we define thei-j xcut problem to be the problem of computing ani-j xcut of minimum cost. This paper contains a proof that the minimum xcut problems have at mostn distinct optimal solution values. These solutions can be compactly represented by a set ofn partitions in such a way that the optimal solution to any of the problems can be found inO(n) time. For a special additive cost function that naturally arises in connection to graphs, some interesting properties of the set of optimal solutions that lead to a very simple algorithm are presented.     

Approximating the minimum weight steiner triangulation

We show that the length of the minimum weight Steiner triangulation (MWST) of a point set can be approximated within a constant factor by a triangulation algorithm based on quadtrees. InO(n logn) time we can compute a triangulation withO(n) new points, and no obtuse triangles, that approximates the MWST. We can also approximate the MWST with triangulations having no sharp angles. We generalize some of our results to higher-dimensional triangulation problems. No previous polynomial-time triangulation algorithm was known to approximate the MWST within a factor better thanO(logn).     

Generating thec *5-connected graphs

A planar 3-valent 3-connected graph is said to becyclically n-connected provided it is possible to separate two circuits by cutting edges, and at leastn edges must be cut to do so. The graph is said to bestrongly cyclically n-connected provided it is cyclicallyn-connected and any separation of two circuits by cutting edges leaves one component consisting of just a simple circuit. We give a method of generating all strongly cyclically 5-connected graphs by certain types of facet splitting.     

ON STABLE LINE SEGMENTS IN ALL TRIANGULATIONS OF A PLANAR POINT SET

Abstract. Let S be a set of finite plauar points. A llne segment L(p, q) with p, q E Sis called a stable line segment of S, if there is no Line segment with two endpoints in S intersecting L(p, q). In this paper, some geometric properties of the set of all stable line segments     

Induced Circuits in Planar Graphs

In McDiarmid, B. Reed, A. Schrijver, and B. Shepherd (Univ. of Waterloo Tech. Rep., 1990) a polynomial-time algorithm is given for the problem of finding a minimum cost circuit without chords (induced circuit) traversing two given vertices of a planar graph. The algorithm is based on the ellipsoid method. Here we give an O(n²) combinatorial algorithm to determine whether two nodes in a planar graph lie on an induced circuit. We also give a min-max relation for the problem of finding a maximum number of paths connecting two given vertices in a planar graph so that each pair of these paths forms an induced circuit.     

Enumerating Order Types for Small Point Sets with Applications

Order types are a means to characterize the combinatorial properties of a finite point configuration. In particular, the crossing properties of all straight-line segments spanned by a planar n-point set are reflected by its order type. We establish a complete and reliable data base for all possible order types of size n=10 or less. The data base includes a realizing point set for each order type in small integer grid representation. To our knowledge, no such project has been carried out before.We substantiate the usefulness of our data base by applying it to several problems in computational and combinatorial geometry. Problems concerning triangulations, simple polygonalizations, complete geometric graphs, and k-sets are addressed. This list of applications is not meant to be exhaustive. We believe our data base to be of value to many researchers who wish to examine their conjectures on small point configurations.     

Algorithms for minimum length partitions of polygons

We show that it is possible to find a diagonal partition of anyn-vertex simple polygon into smaller polygons, each of at mostm edges, minimizing the total length of the partitioning diagonals, in timeO(n ³ m ²). We derive the same asymptotic upper time-bound for minimum length diagonal partitions of simple polygons into exactlym-gons provided that the input polygon can be partitioned intom-gons. Also, in the latter case, if the input polygon is convex, we can reduce the upper time-bound toO(n ³ logm).     

On the complexity of cell flipping in permutation diagrams and multiprocessor scheduling problems

Permutation diagrams have been used in circuit design to model a set of single point nets crossing a channel, where the minimum number of layers needed to realize the diagram equals the clique number ω(G) of its permutation graph, the value of which can be calculated in O(nlogn) time. We consider a generalization of this model motivated by “standard cell” technology in which the numbers on each side of the channel are partitioned into consecutive subsequences, or cells, each of which can be left unchanged or flipped (i.e., reversed). We ask, for what choice of flippings will the resulting clique number be minimum or maximum. We show that when one side of the channel is fixed (no flipping), an optimal flipping for the other side can be found in O(nlogn) time for the maximum clique number, and that when both sides are free this can be solved in O(n²) time. We also prove NP-completeness of finding a flipping that gives a minimum clique number, even when one side of the channel is fixed, and even when the size of the cells is restricted to be less than a small constant. Moreover, since the complement of a permutation graph is also a permutation graph, the same complexity results hold for the stable set (independence) number. In the process of the NP-completeness proof we also prove NP-completeness of a restricted variant of a scheduling problem. This new NP-completeness result may be of independent interest.