Computational geometry algorithms for the systolic screen

Adigitized plane of sizeM is a rectangular M × M array of integer lattice points called pixels. A M × M mesh-of-processors in which each processorP _ij represents pixel (i,j) is a natural architecture to store and manipulate images in ; such a parallel architecture is called asystolic screen. In this paper we consider a variety of computational-geometry problems on images in a digitized plane, and present optimal algorithms for solving these problems on a systolic screen. In particular, we presentO(M)-time algorithms for determining all contours of an image; constructing all rectilinear convex hulls of an image (peeling); solving the parallel and perspective visibility problem forn disjoint digitized images; and constructing the Voronoi diagram ofn planar objects represented by disjoint images, for a large class of object types (e.g., points, line segments, circles, ellipses, and polygons of constant size) and distance functions (e.g., allL _p metrics). These algorithms implyO(M)-time solutions to a number of other geometric problems: e.g., rectangular visibility, separability, detection of pseudo-star-shapedness, and optical clustering. One of the proposed techniques also leads to a new parallel algorithm for determining all longest common subsequences of two words.Research supported by the Naural Sciences and Engineering Research Council of Canada. With the Editor-in-Chief's permission, this paper was sent to the referees in a form which kept them unaware of the fact that the Guest Editor is one of the co-authors.     

Optimal randomized parallel algorithms for computational geometry

We present parallel algorithms for some fundamental problems in computational geometry which have a running time ofO(logn) usingn processors, with very high probability (approaching 1 asn → ∞). These include planar-point location, triangulation, and trapezoidal decomposition. We also present optimal algorithms for three-dimensional maxima and two-set dominance counting by an application of integer sorting. Most of these algorithms run on a CREW PRAM model and have optimal processor-time product which improve on the previously best-known algorithms of Atallah and Goodrich [5] for these problems. The crux of these algorithms is a useful data structure which emulates the plane-sweeping paradigm used for sequential algorithms. We extend some of the techniques used by Reischuk [26] and Reif and Valiant [25] for flashsort algorithm to perform divide and conquer in a plane very efficiently leading to the improved performance by our approach.     

Computational experiments with algorithms for stiff ODEs

The numerical performance of computer codes available to solve stiff systems of ODEs is evaluated. Three widely used codes of Gear/Hindmarsh, Gottwald/Wanner and Deuflhard/Bader are tested by numerous randomly generated examples which permit an arbitrary choice of the position and the number of the eigenvalues of the Jacobian. Besides a detailed evaluation of the results with regard to reliability and efficiency, examples with specified distributions of the eigenvalues and various structures of the ODEs are presented and their influence on the performance of the algorithms is discussed.     

Optimal randomized parallel algorithms for computational geometry

We present parallel algorithms for some fundamental problems in computational geometry which have a running time ofO(logn) usingn processors, with very high probability (approaching 1 asn ). These include planar-point location, triangulation, and trapezoidal decomposition. We also present optimal algorithms for three-dimensional maxima and two-set dominance counting by an application of integer sorting. Most of these algorithms run on a CREW PRAM model and have optimal processor-time product which improve on the previously best-known algorithms of Atallah and Goodrich [5] for these problems. The crux of these algorithms is a useful data structure which emulates the plane-sweeping paradigm used for sequential algorithms. We extend some of the techniques used by Reischuk [26] and Reif and Valiant [25] for flashsort algorithm to perform divide and conquer in a plane very efficiently leading to the improved performance by our approach.This is a substantially revised version of the paper that appeared as Optimal Randomized Parallel Algorithms for Computational Geometry in theProceedings of the 16th International Conference on Parallel Processing, St. Charles, Illinois, August 1987.This research was supported by DARPA/ARO Contract DAAL03-88-K-0195, Air Force Contract AFOSR-87-0386, DARPA/ISTO Contracts N00014-88-K-0458 and N00014-91-J-1985, and by NASA Subcontract 550-63 of Primecontract NAS5-30428.     

Mechanical certification of systolic algorithms

We present in this paper an approach for mechanically certifying the correctness of systolic algorithms and detail the correctness proof of a systolic algorithm for a dynamic programming (optimal parenthesization) problem.     

A processor-time-minimal systolic array for cubical mesh algorithms

Using a directed acyclic graph (DAG) model of algorithms, the paper focuses on time-minimal multiprocessor schedules that use as few processors as possible. Such a processor-time-minimal scheduling of an algorithm's DAG first is illustrated using a triangular shaped 2-D directed mesh (representing, for example, an algorithm for solving a triangular system of linear equations). Then, algorithms represented by an n×n×n directed mesh are investigated. This cubical directed mesh is fundamental; it represents the standard algorithm for computing matrix product as well as many other algorithms. Completion of the cubical mesh required 3n-2 steps. It is shown that the number of processing elements needed to achieve this time bound is at least [3n^2/4]. A systolic array for the cubical directed mesh is then presented. It completes the mesh using the minimum number of steps and exactly [3n ^2/4] processing elements it is processor-time-minimal. The systolic array's topology is that of a hexagonally shaped, cylindrically connected, 2-D directed mesh     

Computational algorithms for computing the fractional derivatives of functions

In this paper, we propose algorithms to compute the fractional derivatives of a function by a weighted sum of function values at specified points. The fractional derivatives are considered in the Caputo sense. The error analysis of the algorithms and some illustrative examples are presented. The numerical results confirm that the new algorithms are accurate, efficient and readily implemented.     

On mapping systolic algorithms onto the hypercube

Consideration is given to the problem of mapping systolic array algorithms into efficient algorithms for a fixed-size hypercube architecture. The authors describe in detail several optimal implementations of algorithms given for one-way one- and two-dimensional systolic arrays. Since interprocessor communication is many times slower than local computation in parallel computers built to date, the problem of efficient communication is specifically addressed for these mappings. In order to validate the technique experimentally, five systolic algorithms were mapped in various ways onto a 64-node NCUBE/7 MIMD hypercube machine. The algorithms are for the following problems: the shuffle scheduling problem, finite impulse response filtering, linear context-free language recognition, matrix multiplication, and computing the Boolean transitive closure. Experimental evidence indicates that good performance is obtained for the mappings     

Computational fractal geometry with WFA

We define two measures of “fractalness” of gray-tone images: the degree of self-similarity and the gray-tone fractal dimension as a generalization of Minkovski dimension of compact sets. We show how to compute both these measures from the WFA-representation of a gray-tone image. Since we have developed a WFA-inference algorithm which computes a good approximation of any gray-tone image we can compute a close approximation of both our measures of fractalness for any gray-tone image. Received: 15 November 1994 / 6 October 1995     

Models and algorithms for the screen line-based traffic-counting location problems

We consider an overlooked, but important, practical problem about the optimal selection of cordon–screen lines for traffic census study in road networks. The problem can be stated as: (1) how to select the optimal locations of a given number of counting stations to separate as many origin–destination (O–D) pairs as possible, (2) how to determine the minimum number of counting stations and their locations required for separating all O–D pairs. Here, an O–D pair is said to be separated if trips between this O–D pair are entirely intercepted by the current traffic-counting stations. The problems of interest are formulated as integer linear-programming models. After exploring the relaxed linear-programming problems and their dual problems, a solution scheme that combines a shortest path-based column generation procedure and a branch-and-bound technique is developed to find an optimal counting location solution. The proposed models and algorithms are illustrated with numerical examples and compared with the genetic algorithm.     

Computational algorithms for algebraic operations on multidimensional polynomials

Algebraic operations on m-D (m-dimensional) polynomials (m≥ 2) are considered. In particular the addition, multiplication and division of such polynomials are described by means of algorithms in appropriate computational form. The special case of division of a multidimensional polynomial by a polynomial of lower order in each variable is examined, and, apart from the corresponding algorithm, necessary and sufficient conditions for the existence of the quotient and a remainder polynomial of lower order than the divisor are introduced. These conditions can be formulated by inspection of the coefficients of the dividend and divisor polynomials.     

A lattice model for cellular (systolic) algorithms

In this paper a lattice model (here ‘lattice’ means a net of points) is introduced for homogeneous cellular algorithms. On the basis of this model a transformation methodology is developed, which makes it possible to produce many different versions of a given cellular algorithm. These versions may have quite different structural properties, but they perform the same computation as the original algorithm. In this way a great variety of cellular algorithms can be offered to choose the best version in practice and, on the other hand, cellular algorithms can be classified according to their inherent structures.     

Computational geometry in a curved world

We extend the results of straight-edged computational geometry into the curved world by defining a pair of new geometric objects, thesplinegon and thesplinehedron, as curved generalizations of the polygon and polyhedron. We identify three distinct techniques for extending polygon algorithms to splinegons: the carrier polygon approach, the bounding polygon approach, and the direct approach. By these methods, large groups of algorithms for polygons can be extended as a class to encompass these new objects. In general, if the original polygon algorithm has time complexityO(f(n)), the comparable splinegon algorithm has time complexity at worstO(Kf(n)) whereK represents a constant number of calls to members of a set of primitive procedures on individual curved edges. These techniques also apply to splinehedra. In addition to presenting the general methods, we state and prove a series of specific theorems. Problem areas include convex hull computation, diameter computation, intersection detection and computation, kernel computation, monotonicity testing, and monotone decomposition, among others.     

Computational algebraic geometry of projective configurations

This article deals with algorithmic and structural aspects related to the computer-aided study of incidence configurations in plane projective geometry. We describe invariant-theoretic algorithms and complexity results for computing the realization space and deciding the coordinatizability of configurations. A practical procedure for automated theorem proving in projective geometry is obtained as a special case. We use the final polynomial technique of Bokowski and Whiteley for encoding the resulting proofs, and we apply Buch-berger's Gröbner basis method for computing minimum degree final polynomials and final syzygies, thus attaining the bounds in the recent effective versions of Hubert's Nullstellen-satz.     

Computational geometry in a curved world

We extend the results of straight-edged computational geometry into the curved world by defining a pair of new geometric objects, thesplinegon and thesplinehedron, as curved generalizations of the polygon and polyhedron. We identify three distinct techniques for extending polygon algorithms to splinegons: the carrier polygon approach, the bounding polygon approach, and the direct approach. By these methods, large groups of algorithms for polygons can be extended as a class to encompass these new objects. In general, if the original polygon algorithm has time complexityO(f(n)), the comparable splinegon algorithm has time complexity at worstO(Kf(n)) whereK represents a constant number of calls to members of a set of primitive procedures on individual curved edges. These techniques also apply to splinehedra. In addition to presenting the general methods, we state and prove a series of specific theorems. Problem areas include convex hull computation, diameter computation, intersection detection and computation, kernel computation, monotonicity testing, and monotone decomposition, among others.This research was partially supported by National Science Foundation Grants MCS 83-03926, DCR85-05517, and CCR87-00917.This author's research was also partially supported by an Exxon Foundation Fellowship, by a Henry Rutgers Research Fellowship, and by National Science Foundation Grant CCR88-03549.     

Constant time algorithms for computational geometry on thereconfigurable mesh

The reconfigurable mesh consists of an array of processors interconnected by a reconfigurable bus system. The bus system can be used to dynamically obtain various interconnection patterns among the processors. Recently, this model has attracted a lot of attention. The authors show O(1) time solutions to the following computational geometry problems on the reconfigurable mesh: all-pairs nearest neighbors, convex hull, triangulation, two-dimensional maxima, two-set dominance counting, and smallest enclosing box. All these solutions accept N planar points as input and employ an N×N reconfigurable mesh. The basic scheme employed in the implementations is to recursively find an O(1) time solution. The number of recursion levels and the size of the subproblems at each level of recursion are optimized such that the problem decomposition and the solution to the problem can be obtained in constant time. As a result, they have developed some efficient merge techniques to combine the solutions for subproblems on the reconfigurable mesh. These techniques exploit reconfigurability in nontrivial ways leading to constant time solutions using optimal size of the mesh