An optimal algorithm for the boundary of a cell in a union of rays

In this paper we study a cell of the subdivision induced by a union ofn half-lines (or rays) in the plane. We present two results. The first one is a novel proof of theO(n) bound on the number of edges of the boundary of such a cell, which is essentially of methodological interest. The second is an algorithm for constructing the boundary of any cell, which runs in optimal (n logn) time. A by-product of our results are the notions of skeleton and of skeletal order, which may be of interest in their own right.This work was partly supported by CEE ESPRIT Project P-940, by the Ecole Normale Supérieure, Paris, and by NSF Grant ECS-84-10902.This work was done in part while this author was visiting the Ecole Normale Supérieure, Paris, France.     

The Role of Arithmetic in Fast Parallel Matrix Inversion

In the last two decades several NC algorithms for solving basic linear algebraic problems have appeared in the literature. This interest was clearly motivated by the emergence of a parallel computing technology and by the wide applicability of matrix computations. The traditionally adopted computation model, however, ignores the arithmetic aspects of the applications, and no analysis is currently available demonstrating the concrete feasibility of many of the known fast methods. In this paper we give strong evidence to the contrary, on the sole basis of the issue of robustness, indicating that some theoretically brilliant solutions fail the severe test of the ``Engineering of Algorithms.' We perform a comparative analysis of several well-known numerical matrix inversion algorithms under both fixed- and variable-precision models of arithmetic. We show that, for most methods investigated, a typical input leads to poor numerical performance, and that in the exact-arithmetic setting no benefit derives from conditions usually deemed favorable in standard scientific computing. Under these circumstances, the only algorithm admitting sufficiently accurate NC implementations is Newton's iterative method, and the word size required to guarantee worst-case correctness appears to be the critical complexity measure. Our analysis also accounts for the observed instability of the considered superfast methods when implemented with the same floating-point arithmetic that is perfectly adequate for the fixed-precision approach. Received March 28, 1998; revised February 2, 1999, and April 21, 1999.     

Area-time lower-bound techniques with applications to sorting

Thearea-time complexity of VLSI computations is constrained by the flow and the storage of information in the two-dimensional chip. We study here the information exchanged across the boundary of the cells of asquare-tessellation of the layout. When the information exchange is due to thefunctional dependence between variables respectively input and output on opposite sides of a cell boundary, lower bounds are obtained on theAT ² measure (which subsume bisection bounds as a special case). When information exchange is due to thestorage saturation of the tessellation cells, a new type of lower bound is obtained on theAT measure.In the above arguments, information is essentially viewed as a fluid whose flow is uniquely constrained by the available bandwidth. However, in some computations, the flow is kept below capacity by the necessity to transform information before an output is produced. We call this mechanismcomputational friction and show that it implies lower bounds on theAT/logA measure.Regimes corresponding to each of the three mechanisms described above can appear by varying the problem parameters, as we shall illustrate by analyzing the problem of sortingn keys each ofk bits, for whichAT ²,AT, andAT/logA bounds are derived. Each bound is interesting, since it dominates the other two in a suitable range of key lengths and computations times.This work was supported in part by the National Science Foundation ECS-84-10902, by an IBM predoctoral fellowship, and by the Joint Services Electronics Program under Contract N00014-84-C-0149. A preliminary version was presented at the 19th Conference on Information Sciences and Systems.     

Traffic analysis of a buffered digital data acquisition system

A digital data acquisition system is analyzed under the traffic standpoint. This system receives a random stream of digital messages, accumulates them in an electronic buffer storage and unloads them on a magnetic tape. The system is representable as a single waiting line, the service mechanism of which is ruled by the characteristics of the cascaded functional blocks. Queueing theory methods are applied to determine the queue length distribution under stationary conditions as a function of the system parameters; this, conversely, provides some criteria for the selection of the values of the parameters, necessary to achieve a given statistical behavior. The expected message loss due to temporary system saturation is also computed.     

Processor—Time Tradeoffs under Bounded-Speed Message Propagation: Part I, Upper Bounds

Upper bounds are derived for the processor—time tradeoffs of machines such as linear arrays and two-dimensional meshes, which are compatible with the physical limitation expressed by bounded-speed propagation of messages (due to the finiteness of the speed of light). It is shown that parallelism and locality combined may yield speedups superlinear in the number of processors. The speedups are inherent, due to the optimality of the obtained tradeoffs as established in a companion paper. Simulations of multiprocessor machines are developed by analogous machines with fewer processors. A crucial role is played by the hierarchical nature of the memory system. A divide-and-conquer technique for hierarchical memories is developed, based on the graph-theoretic notion of a topological separator. For multiprocessors, this technique also requires a careful balance of memory access and interprocessor communication costs, which leads to nonintuitive orchestrations of the simulation process. Received November 2, 1995, and in final form September 12, 1996.     

Finding the intersection of two convex polyhedra

Given two convex polyhedra in three-dimensional space, we develop an algorithm to (i) test whether their intersection is empty, and (ii) if so to find a separating plane, while (iii) if not to find a point in the intersection and explicitly construct their intersection polyhedron. The algorithm runs in timeO (nlogn), where n is the sum of the numbers of vertices of the two polyhedra. The part of the algorithm concerned with (iii) (constructing the intersection) is based upon the fact that if a point in the intersection is known, then the entire intersection is obtained from the convex hull of suitable geometric duals of the two polyhedra taken with respect to this point.     

Output-sensitive generation of the perspective view of isothetic parallelepipeds

We present a new hidden-line elemination technique for displaying the perspective view of a scene of three-dimensional isothetic parallelepipeds (3D-rectangles). We assume that the 3D-rectangles are totally ordered based upon the dominance relation of occlusion. The perspective view is generated incrementally, starting with the closest 3D-rectangle and proceeding away from the view point. Our algorithm is scene-sensitive and uses0((n +d) logn log logn) time, wheren is the number of 3D-rectangles andd is the number of edges of the display. This improves over the heretofore best known technique. The primary data structure is an efficient alternative to dynamic fractional cascading for use with augmented segment and range trees when the universe is fixed beforehand. It supports queries inO((logn +k) log logn) time, wherek is the size of the response, and insertions and deletions inO(logn log logn) time, all in the worst case.An extended abstract of this work appeared inProceedings of the 2nd Scandinavian Workshop on Algorithm Theory (SWAT '90) (edited by J. R. Gilbert and R. Karlsson), Lecture Notes in Computer Science, Volume 447, Springer-Verlag, Berlin, 1990, pp. 71–84. Franco P. Preparata's support was provided in part by NSF research grant CCR-8906419. This research was done while on the faculty of the University of Illinois and partly while visiting Ecole Normale Supérieure in Paris, France. Jeffrey S. Vitter's support was provided in part by NSF Presidential Young Investigator Award CCR-8947808 with matching funds from an IBM research contract and by NSF research grant DCR-8403613. Part of this research was done while visiting Ecole Normale Supérieure in Paris, France. Mariette Yvinec's support was provided by CNRS.