On the construction of abstract voronoi diagrams

We show that the abstract Voronoi diagram ofn sites in the plane can be constructed in timeO(n logn) by a randomized algorithm. This yields an alternative, but simpler,O(n logn) algorithm in many previously considered cases and the firstO(n logn) algorithm in some cases, e.g., disjoint convex sites with the Euclidean distance function. Abstract Voronoi diagrams are given by a family of bisecting curves and were recently introduced by Klein [13]. Our algorithm is based on Clarkson and Shor's randomized incremental construction technique [7]. This work was supported by the DFG, Me 620/6, and ESPRIT P3075 ALCOM. A preliminary version of this paper has been presented at STACS '90, Rouen, France.     

An Optimal Deterministic Algorithm for Computing the Diameter of a Three-Dimensional Point Set

We describe a deterministic algorithm for computing the diameter of a finite set of points in R ³ , that is, the maximum distance between any pair of points in the set. The algorithm runs in optimal time O(nlog n) for a set of n points. The first optimal, but randomized, algorithm for this problem was proposed more than 10 years ago by Clarkson and Shor [11] in their ground-breaking paper on geometric applications of random sampling. Our algorithm is relatively simple except for a procedure by Matoušek [25] for the efficient deterministic construction of epsilon-nets. This work improves previous deterministic algorithms by Ramos [31] and Bespamyatnikh [7], both with running time O(nlog ² n) . The diameter algorithm appears to be the last one in Clarkson and Shor's paper that up to now had no deterministic counterpart with a matching running time. Received May 10, 2000, and in revised form November 3, 2000. Online publication June 22, 2001.     

Computing a centerpoint of a finite planar set of points in linear time

The notion of a centerpoint of a finite set of points in two and higher dimensions is a generalization of the concept of the median of a set of reals. In this paper we present a linear-time algorithm for computing a centerpoint of a set ofn points in the plane, which is optimal compared with theO(n log³ n) complexity of the previously best-known algorithm. We use suitable modifications of the hamsandwich cut algorithm in [Me2] and the prune-and-search technique of Megiddo [Me1] to achieve this improvement.     

Sorting on a ring of processors

We study the time necessary to sort on a ring of processors. We show that the amount of space available to each processor determines the time required. We prove a lower bound of 2[n/2] − 1 steps for sorting on a ring of n processors, under the constraint that each processor retains only a single value at any time. In contrast, we show an algorithm that sorts in [n/2] + 1 steps if each processor is allowed to store six values.     

Combinatorial obstructions to the lifting of weaving diagrams

This paper deals with various connections of oriented matroids [3] and weaving diagrams of lines in space [9], [16], [27]. We encode the litability problem of a particular weaving diagramD onn lines by the realizability problem of a partial oriented matroid χ _D with2n elements in rank 4. We prove that the occurrence of a certain substructure inD implies that χD is noneuclidean in the sense of Edmonds, Fukuda, and Mandel [12], [14]. Using this criterion we construct an infinite class of minor-minimal noneuclidean oriented matroids in rank 4. Finally, we give an easy algebraic proof for the nonliftability of the alternating weaving diagram on a bipartite grid of 4×4 lines [16].     

An O(n 3 L) adaptive path following algorithm for a linear complementarity problem

In this paper we propose an O(n ³ L) algorithm which is a modification of the path following algorithm [8] for a linear complementarity problem. The path following algorithm has to take a short step size in each iteration in order to bound the number of overall arithmetic operations by O(n ³ L). In practical computation, we can determine the step size adaptively. Mizuno, Yoshise, and Kikuchi [11] reported that such an adaptive algorithm required about O(L) iterations for some test problems. Here we show that we can use a rank one update technique in the adaptive algorithm so that the number of overall arithmetic operations is theoretically bounded by O(n ³ L).Research supported in part by the U.S. Army Research Office through the Mathematical Sciences Institute of Cornell University.Research supported in part by NSF grants ECS-8602534 and DMS-8904406 and ONR contract N-00014-87-K0212.     

Parallel QR decomposition of a rectangular matrix

Summary We show that the greedy algorithm introduced in [1] and [5] to perform the parallel QR decomposition of a dense rectangular matrix of sizem×n is optimal. Then we assume thatm/n ² tends to zero asm andn go to infinity, and prove that the complexity of such a decomposition is asymptotically2n, when an unlimited number of processors is available.     

Random walks in a convex body and an improved volume algorithm

We give a randomized algorithm using O(n⁷ log² n) separation calls to approximate the volume of a convex body with a fixed relative error. The bound is O(n⁶ log⁴ n) for centrally symmpetric bodies and for polytopes with a polynomial number of facets, and O(n⁵ log⁴ n) for centrally symmetric polytopes with a polynomial number of facets. We also give an O(n⁶ log n) algorithm to sample a point from the uniform distribution over a convex body. Several tools are developed that may be interesting on their own. We extend results of Sinclair–Jerrum [43] and the authors [34] on the mixing rate of Markov chains from finite to arbitrary Markov chains. We also analyze the mixing rate of various random walks on convex bodies, in particular the random walk with steps from the uniform distribution over a unit ball. © 1993 John Wiley & Sons, Inc.     

Batch sizing and job sequencing on a single machine

We study a single-machine scheduling problem in which the items to be processed have to be batched as well as sequenced. Since processed items become available in batches, flow times are defined to be the same for all items in the same batch. A constant set-up delay is incurred between consecutive batches. For any fixed, but arbitrary item sequence, we present an algorithm that finds a sequence of batches such that the total flow time of the items is minimized; we prove that for a set ofn items, the algorithm runs inO(n) time. We show that, among all sequences, the one leading to the minimum flow time has the items in non-decreasing order of running times. Thus, the optimal algorithm for the combined problem, called thebatch-sizing problem, runs inO(n logn) time. We also prove that this algorithm yields an improved solution to a scheduling problem recently studied by Baker [1].     

On an inverse eigenproblem for Jacobi matrices

Recently Xu [13] proposed a new algorithm for computing a Jacobi matrix of order 2n with a given n×n leading principal submatrix and with 2n prescribed eigenvalues that satisfy certain conditions. We compare this algorithm to a scheme proposed by Boley and Golub [2], and discuss a generalization that allows the conditions on the prescribed eigenvalues to be relaxed. This revised version was published online in June 2006 with corrections to the Cover Date.     

On structures of bisubmodular polyhedra

A bisubmodular polyhedron is defined in terms of a so-called bisubmodular function on a family of ordered pairs of disjoint subsets of a finite set. We examine the structures of bisubmodular polyhedra in terms of signed poset and exchangeability graph. We give a characterization of extreme points together with an O(n ²) algorithm for discerning whether a given point is an extreme point, wheren is the cardinality of the underlying set, and we assume a function evaluation oracle for the bisubmodular function. The algorithm also determines the signed posetructure associated with the given point if it is an extreme point. We reveal the adjacency relation of extreme points by means of the Hasse diagrams of the associated signed posets. Moreover, we investigate the connectivity and the decomposition of a bisubmodular system into its connected components.     

AnO (n)-algorithm for LP-knapsacks with a fixed number of GUB constraints

AnO (n+r logn) algorithm is presented for the linear programming knapsack problem withr generalized upper bounds andn variables. This result which is based on parametric programming and well-known ideas for the design of linear-time algorithms improvesO (n logn) algorithms given byGlover/Klingman [1979] andZemel [1980].

---

Zusammenfassung Es wird einO (n+r logn)-Algorithmus vorgestellt, der LP-Rucksackprobleme mitn Variablen undr verallgemeinerten oberen Schranken für die Variablen löst. Grundlage des Verfahrens ist ein parametrischer Ansatz kombiniert mit bekannten Methoden zur Konstruktion von Algorithmen mit linearer Laufzeit. Der vorgestellte Algorithmus verbessertO (n logn)-Verfahren vonGlover/Klingman [1979] undZemel [1980].

     

The average performance of a parallel stable marriage algorithm

In this paper, Tseng and Lee's parallel algorithm to solve the stable marriage prolem is analyzed. It is shown that the average number of parallel proposals of the algorithm is of ordern by usingn processors on a CREW PRAM, where each parallel proposal requiresO(loglog(n) time on CREW PRAM by applying the parallel selection algorithms of Valiant or Shiloach and Vishkin. Therefore, our parallel algorithm requiresO(nloglog(n)) time. The speed-up achieved is log(n)/loglog(n) since the average number of proposals required by applying McVitie and Wilson's algorithm to solve the stable marriage problem isO(nlog(n)).     

An algebraic approach to approximate evaluation of a polynomial on a set of real points

The previous best algorithm for approximate evaluation of a polynomial on a real set was due to Rokhlin and required of the order ofmu+nu ³ infinite precision arithmetic operations to approximate [on a fixed bounded setX(m) ofm+1 real points] a degreen polynomial within the error bound . We develop an approximation algorithm which exploits algebraic computational techniques and decreases Rokhlin's record estimate toO(mlog² u+nmin-u, logn}). For logu=o(logn), this result may also be favorably compared with the record boundO(m+n)log² n) on the complexity of the exact multipoint polynomial evaluation. The new algorithm can be performed in the fields (or rings) generated by the input values, which enables us to decrease the precision of the computations [by using modular (residue) arithmetic] and to simplify our computations further in the case whereu=O(logn). Our algorithm allows NC and simultaneously processor efficient parallel implementation. Because of the fundamental nature of the multipoint polynomial evaluation, our results have further applications to numerical and algebraic computational problems. In passing, we also show a substantial improvement in the Chinese remainder algorithm for integers based on incorporating Kaminski's fast residue computation.     

Cellularity of a New Class of Diagram Algebras

A diagram algebra in which the diagrams include n rows of n points is constructed. Moreover, we prove that the algebra is cellular and quasi-hereditary.     

A new duality result concerning voronoi diagrams

A new duality between order-k Voronoi diagrams inE ^d and convex hulls inE ^d+1 is established. It implies a reasonably simple algorithm for computing the order-k diagram forn points in the plane inO(k ² n logn) time and optimalO(k(n–k)) space.Research was supported by the Austrian Fond zur Foerderung der wissenschaftlichen Forschung.     

The analysis of a nested dissection algorithm

Summary Nested dissection is an algorithm invented by Alan George for preserving sparsity in Gaussian elimination on symmetric positive definite matrices. Nested dissection can be viewed as a recursive divide-and-conquer algorithm on an undirected graph; it usesseparators in the graph, which are small sets of vertices whose removal divides the graph approximately in half. George and Liu gave an implementation of nested dissection that used a heuristic to find separators. Lipton and Tarjan gave an algorithm to findn ^1/2-separators in planar graphs and two-dimensional finite element graphs, and Lipton, Rose, and Tarjan used these separators in a modified version of nested dissection, guaranteeing bounds ofO (n logn) on fill andO(n ^3/2) on operation count. We analyze the combination of the original George-Liu nested dissection algorithm and the Lipton-Tarjan planar separator algorithm. This combination is interesting because it is easier to implement than the Lipton-Rose-Tarjan version, especially in the framework of existïng sparse matrix software. Using some topological graph theory, we proveO(n logn) fill andO(n ^3/2) operation count bounds for planar graphs, twodimensional finite element graphs, graphs of bounded genus, and graphs of bounded degree withn ^1/2-separators. For planar and finite element graphs, the leading constant factor is smaller than that in the Lipton-Rose-Tarjan analysis. We also construct a class of graphs withn ^1/2-separators for which our algorithm does not achieve anO(n logn) bound on fill.The work of this author was supported in part by the Hertz Foundation under a graduate fellowship and by the National Science Foundation under Grant MCS 82-02948The work of this author was supported in part by the National Science Foundation under Grant MCS 78-26858 and by the Office of Naval Research under Contract N00014-76-C-0688     

Union curvature of a vector field in a subspace

The differential equations of union curves on a hypersurfaceV _n immersed in a RiemannianV _n+1 have been obtained by Springer [1]. These results were generalized later for a subspace in a Riemannian space by Mishra [2]. The author [3] has defined the union curvature of a vector field with respect to a curve on a hypersurfaceV _n of a RiemannianV _n+1. The purpose of this paper is to consider union curvature of a vector field with respect to a curve in a subspaceV _n of a RiemannianV _m. The author is indebted to the referee for helpful suggestions.