The problem of finding a minimum cut of n arcs on a unit circle is considered. It is shown that this problem can be solved in $\Theta (n \log n)$ time, which is optimal to within a constant factor. If the endpoints of the arcs are sorted, the problem can be solved in linear time. The solution to the minimum cut problem can be used to solve a minimum new facility problem in competitive location and a minimum partition set problem for the intersection model of a circle graph. As a by-product it is also shown that the maximum independent set of n arcs can be obtained in linear time, assuming the endpoints are sorted, which is much simpler than the most recent result of Masuda and Nakajima [SIAMI. Comput., 17 (1988), pp. 41–52].

In VLSI design, technology requirements often dictate the use of only two orthogonal orientations, determining both the shape of objects and the distance function, the $L_1 $-metric, to be used for wiring objects. More recent VLSI fabrication technology is capable of creating edges and wires in both the orthogonal and diagonal orientations. We generalize the distance concept to the case where any fixed set of orientations is allowed, and introduce a family of naturally induced metrics, and the subsequent generalization of geometrical concepts. A shortest connection between two points is in this case a path composed of line segments with only the given orientations. We derive optimal solutions for various basic planar distance problems in this setting, such as the computation of a Voronoi diagram, a minimum spanning tree, and the (minimum and maximum) distance between two convex polygons. Many other theoretically interesting and practically relevant problems remain to be solved. In particular, the new family of metrics may help bridge the gap between the $L_1 $- and $L_2 $-metrics, as those are the limiting cases for two and infinitely many regularly distributed orientations.

We study the rectilinear shortest paths and minimum spanning tree (MST) problems for a set of points in the plane in the presence of rectilinear obstacles. We use the track graph, a suitably defined grid-like structure, to obtain efficient solutions for both problems. The track graph consists of rectilinear tracks defined by the obstacles and the points for which shortest paths and a minimum spanning tree are sought. We use a growth process like Dijkstra's on the track graph to find shortest paths from any point in the set to all other points (the one-to-all shortest paths problem). For the one-to-all shortest paths problem for n points we derive an O(n min {log n, log e} + (e + k) log t) time algorithm, where e is the total number of edges of all obstacles, t is the number of extreme edges of all obstacles, and k is the number of intersections among obstacle tracks (all bounds are for the worst case). The MST for the points is constructed also in time O(n log n + (e + k) log t) by a hybrid method of searching for shortest paths while simultaneously constructing an MST. An interesting application of the MST algorithm is the approximation of Steiner trees in graphs.

We address ourselves to an instance of the Shortest Path problem with obstacles where a shortest path in the Manhattan (or L1) distance is sought between two points (source and destination) and the obstacles are n disjoint rectangles with sides parallel to the coordinate axes. A plane sweep technique is applied rather than the graph theoretic approach frequently used in the literature. We show that there has to be a path of minimum length between the two given points which is monotone in at least one of x or y directions. Then we present an algorithm of time complexity Ο(n log n) for constructing that path and show that our algorithm is optimal.

In computational geometry, problems involving only rectilinear objects with edges parallel to the x -and y-axes have attracted great attention. They are often easier to solve than the same problems for arbitrary objects, and solutions are of high practical value, for instance in VLSI design. This is because in VLSI design technology requirements often dictate the use of only two orthogonal orientations for the boundary edges of objects as well as wires.