Applications of a semi-dynamic convex hull algorithm

We obtain new results for manipulating and searching semi-dynamic planar convex hulls (subject to deletions only), and apply them to derive improved bounds for two problems in geometry and scheduling. The new convex hull results are logarithmic time bounds for set splitting and for finding a tangent when the two convex hulls are not linearly separated. Using these results, we solve the following two problems optimally inO(n logn) time: (1) [matching] givenn red points andn blue points in the plane, find a matching of red and blue points (by line segments) in which no two edges cross, and (2) [scheduling] givenn jobs with due dates, linear penalties for late completion, and a single machine on which to process them, find a schedule of jobs that minimizes the maximum penalty.     

A sublogarithmic convex hull algorithm

We present a parallel algorithm for finding the convex hull of a sorted set of points in the plane. Our algorithm runs inO(logn/log logn) time usingO(n log logn/logn) processors in theCommon crcw pram computational model, which is shown to be time and cost optimal. The algorithm is based onn ^1/3 divide-and-conquer and uses a simple pointer-based data structure.Part of this work was done when the last three authors were at the Department of Computer and Information Science, Linköping University. The research of the second author was supported by the Academy of Finland.     

Relaxed outer projections,weighted averages and convex feasibility

A new algorithmic scheme is proposed for finding a common point of finitely many closed convex sets. The scheme uses weighted averages (convex combinations) of relaxed projections onto approximating halfspaces. By varying the weights we generalize Cimmino's and Auslender's methods as well as more recent versions developed by Iusem & De Pierro and Aharoni & Censor. Our approach offers great computational flexibility and encompasses a wide variety of known algorithms as special instances. Also, since it is block-iterative, it lends itself to parallel processing.The research of the first author was partially supported by Ruhrgas under a NAVF grant.     

Optimal convex hull algorithms on enhanced meshes

In this paper we propose time-optimal convex hull algorithms for two classes of enhanced meshes. Our first algorithm computes the convex hull of an arbitrary set ofn points in the plane inO (logn) time on a mesh with multiple broadcasting of sizen×n. The second algorithm shows that the same problem can be solved inO (1) time on a reconfigurable mesh of sizen×n. Both algorithms achieve time lower bounds for their respective model of computation.This work was supported by NASA under grant NCCI-99.Additional support by the National Science Foundation under grant CCR-8909996 is gratefully acknowledged.     

A linear time algorithm for the maximum matching problem on cographs

In this paper, we develop a sequential algorithm for the maximum matching problem on cographs. The input is a parse tree of some cograph. The time complexity of our algorithm is linear.Supported by National Science Council of Taiwan, R.O.C. under Grant NSC81-0415-E-005-03.     

A new systolic architecture for convex hull and half-plane intersection problems

In this paper we will present systolic algorithms for static versions of the convex hull problem and the half-plane intersection problem. The systolic algorithms are based on a cyclic shift operation that makes each object meet all the other objects.     

An optimal time algorithm for finding a maximum weight independent set in a tree

The maximum weight independent set problem for a general graph is NP-hard. But for some special classes of graphs, polynomial time algorithms do exist for solving it. Based on the divide-and-conquer strategy, Pawagi has presented anO(|V|log|V|) time algorithm for solving this problem on a tree. In this paper, we propose anO(|V|) time algorithm to improve Pawagi's result. The proposed algorithm is based on the dynamic programming strategy and is time optimal within a constant factor.     

An unfeasible matching problem

LetG be a bipartite graph with natural edge weights, and letW be a function from the set of vertices ofG into natural numbers. AW-matching ofG is a subset of the set of edges ofG such that for each vertexv the total weight of edges in the subset incident tov does not exceedW(v). Letm be a natural number. We show that the problem of deciding whether there is aW-matching inG whose total weight is not less thanm is NP-complete even ifG is bipartite and its edge weights as well as theW(v)-constraints are constantly bounded.     

A note on the largest empty rectangle problem

We consider the following problem: given a rectangle containingn points, find the largest perimeter subrectangle whose sides are parallel to those of the original rectangle, whose aspect ratio is below a given bound, and which does not contain any of the given points. Chazelle, Drysdale and Lee have studied a variant of this problem with areas as the quantity to be maximized. They gave anO(nlog³ n) algorithm for that problem. We adopt a similar divide-and-conquer approach and are able to use the simpler properties of the perimeter measure to obtain anO(nlog² n) algorithm for our problem.The work of the first author was supported by the Academy of Finland and that of the second by the Natural Sciences and Engineering Research Council of Canada Grant No. A-5692.     

A linear time and space algorithm for finding isomorphic subtrees of a binary tree

This paper shows that it is possible to find all isomorphic subtrees of a binary tree in linear time and space.     

Probabilistic analysis of an algorithm for solving thek-dimensional all-nearest-neighbors problem by projection

A well-known simple heuristic algorithm for solving the all-nearest-neighbors problem in thek-dimensional Euclidean spaceE ^k ,k>1, projects the given point setS onto thex-axis. For each pointq S a nearest neighbor inS under anyL _p -metric (1 p ) is found by sweeping fromq into two opposite directions along thex-axis. If _q denotes the distance betweenq and its nearest neighbor inS the sweep process stops after all points in a vertical 2 _q -slice centered aroundq have been examined. We show that this algorithm solves the all-nearest-neighbors problem forn independent and uniformly distributed points in the unit cube [0,1] ^k in (n ^2–1/k ) expected time, while its worst-case performance is (n ²).     

Reconstructing visible regions from visible segments

An algorithm is presented for reconstructing visible regions from visible edge segments in object space. This has applications in hidden surface algorithms operating on polyhedral scenes and in cartography. A special case of reconstruction can be formulated as a graph problem: Determine the faces of a straight-edge planar graph given in terms of its edges. This is accomplished inO(n logn) time using linear space for a graph withn edges, and is worst-case optimal. The graph may have separate components but the components must not contain each other. The general problem of reconstruction is then solved by applying our algorithm to each component in the containment relation.Research of this author is supported by the National Science Foundation under grant no. ECS-8351942, and by the Schlumberger-Doll Research Labs, Ridgefield, Connecticut.     

A generalized hypergreedy algorithm for weighted perfect matching

We give a generalization of the hypergreedy algorithm for minimum weight perfect matching on a complete edge weighted graph whose weights satisfy the triangle inequality. With a modified version of this algorithm we obtain a logn-approximate perfect matching heuristic for points in the Euclidean plane, inO(n log² n) time.This research was supported in part by the DIMACS Grant No. NSF-STC88-09648.This research was supported in part by the NSF under Grant No. CCR 88-07518.     

A select and insert sorting algorithm

A general sorting algorithm, having the well knownO(n ²) algorithmsStraight Insertion Sort andSelection Sort as special cases, is described. This algorithm is analyzed in the case that certain choices in the algorithm are done randomly, and this yields an algorithm that has an average complexity ofO(n ^1.5) and a worst case complexity ofO(n ²). However, making random choices (by some random number generator) is time consuming, and a simple quasi-random scheme is therefore implemented. Test runs indicate that also this version has average complexity ofO(n ^1.5), and it even seems to perform better than the version using real random choices (even if we disregard the time used for the random choices). This version also needs very little administrative overhead, and it therefore compares favourably to many other sorting algorithms for small and medium sized arrays.     

A maximum stable matching for the roommates problem

The stable roommates problem is that of matchingn people inton/2 disjoint pairs so that no two persons, who are not paired together, both prefer each other to their respective mates under the matching. Such a matching is called a complete stable matching. It is known that a complete stable matching may not exist. Irving proposed anO(n ²) algorithm that would find one complete stable matching if there is one, or would report that none exists. Since there may not exist any complete stable matching, it is natural to consider the problem of finding a maximum stable matching, i.e., a maximum number of disjoint pairs of persons such that these pairs are stable among themselves. In this paper, we present anO(n ²) algorithm, which is a modified version of Irving's algorithm, that finds a maximum stable matching.This research was supported by National Science Council of Republic of China under grant NSC 79-0408-E009-04.     

Efficient parallel algorithms for shortest paths in planar digraphs

Efficient parallel algorithms are presented, on the CREW PRAM model, for generating a succinct encoding of all pairs shortest path information in a directed planar graphG with real-valued edge costs but no negative cycles. We assume that a planar embedding ofG is given, together with a set ofq faces that cover all the vertices. Then our algorithm runs inO(log² n) time and employsO(nq+M(q)) processors (whereM(t) is the number of processors required to multiply twot×t matrices inO(logt) time). Let us note here that wheneverq<n then our processor bound is better than the best previous one (M(n)).O(log² n) time,n-processor algorithms are presented for various subproblems, including that of generating all pairs shortest path information in a directedouterplanar graph. Our work is based on the fundamental hammock-decomposition technique of G. Frederickson. We achieve this decomposition inO(logn log*n) parallel time by usingO(n) processors. The hammock-decomposition seems to be a fundamental operation that may help in improving efficiency of many parallel (and sequential) graph algorithms.This work was partially supported by the EEC ESPRIT Basic Research Action No. 3075 (ALCOM) and by the Ministry of Industry, Energy and Technology of Greece.     

A parallel derangement generation algorithm

A parallel algorithm to generate allD _n derangements ofn distinct elements is presented in this paper. The algorithm requiresO([D _n /P]nlogn) time whenP processors are available on a Single Instruction Multiple Data Stream (SIMD) computer.     

AnO(n 2) algorithm for finding the compact sets of a graph

A special clustering problem is discussed in this paper, called the compact set problem. The goal of the problem is to find all compact sets in a complete, weighted, undirected graph withn vertices. A subsetC of vertices is called a compact set if 1<|C|<n and the maximum weight among all edges inC is smaller than the minimum weight among all edges connecting one vertex inC and the other vertex not inC. An algorithm with complexityO(n ²) is given for the problem improving the previous results.This research was partially supported by the National Science Council of the Republic of China under Grant NSC81-0408-E-216-502.     

Optimal algorithms for total exchange without buffering on the hypercube

Two methods are given for constructing total exchange algorithms for hypercubic processor networks. This is done by means of bit sequences with special properties. The algorithms are optimal with respect to a given time model, need no intermediate message buffering and are local in the sense that every processor executes basically the same program.     

On Shellsort and the frobenius problem

A boundO(N ^1+1/k ) for the running time of Shellsort, withO(logN) passes, is proved very simply by application of a Frobenius basis withk elements.