Search

In this paper we present deterministic parallel algorithms for the coarse-grained multicomputer (CGM) and bulk synchronous parallel (BSP) models for solving the following well-known graph problems: (1) list ranking, (2) Euler tour construction in a tree, (3) computing the connected components and spanning forest, (4) lowest common ancestor preprocessing, (5) tree contraction and expression tree evaluation, (6) computing an ear decomposition or open ear decomposition, and (7) 2-edge connectivity and biconnectivity (testing and component computation). The algorithms require O(log p) communication rounds with linear sequential work per round (p = no. processors, N = total input size). Each processor creates, during the entire algorithm, messages of total size O(log (p) (N/p)) . The algorithms assume that the local memory per processor (i.e., N/p ) is larger than p e , for some fixed e > 0 . Our results imply BSP algorithms with O(log p) supersteps, O(g log (p) (N/p)) communication time, and O(log (p) (N/p)) local computation time. It is important to observe that the number of communication rounds/ supersteps obtained in this paper is independent of the problem size, and grows only logarithmically with respect to p . With growing problem size, only the sizes of the messages grow but the total number of messages remains unchanged. Due to the considerable protocol overhead associated with each message transmission, this is an important property. The result for Problem (1) is a considerable improvement over those previously reported. The algorithms for Problems (2)—(7) are the first practically relevant parallel algorithms for these standard graph problems.

We show that the wavefront approach to Voronoi diagrams (a deterministic line-sweep algorithm that does not use geometric transform) can be generalized to distance measures more general than the Euclidean metric. In fact, we provide the first worst-case optimal (O (n logn) time,O(n) space) algorithm that is valid for the full class of what has been callednice metrics in the plane. This also solves the previously open problem of providing anO (nlogn)-time plane-sweep algorithm for arbitraryL k -metrics. Nice metrics include all convex distance functions but also distance measures like the Moscow metric, and composed metrics. The algorithm is conceptually simple, but it copes with all possible deformations of the diagram.

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 processorPij 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., allLp 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.

Image processin9 is one of the major fields of application for parallel processing. Some of the first multiprocessors were mainly built for processing images (e.g., the MPP for analyzing LANDSAT satellite data) because for such applications data volumes are often so large that the use of standard sequential machines becomes impracticable. In addition to standard image processing operations such as noise removal, edge detection, filtering, etc., researchers have recently also started to study other "high-level" geometric operations which are well known in computational 9eometry. This special issue of Algorithmica is devoted to parallel algorithms for computational-geometry problems on digitized pictures. The motivation for studying such operations is that in practice geometric data for computationalgeometry applications is often given in the form of an image; hence, parallel algorithms which can be applied directly to the image may be more efficient than applying "standard" parallel computational-geometry methods which require that the image is first converted into, e.g., a set of polygonal chains. For example, consider the standard path-plannin9 problem in robotics: given a set of simple polygons in the plane representing the obstacles and a polygon representing the robot, find the shortest path for the robot to move from point A to point B without colliding with any obstacle. In practice, the robot might be moving in a factory hall; instead of first creating a polygonal description of the obstacles and the robot, it may be more efficient to use as input an image obtained from a camera mounted to the ceiling of the factory. Using an image from a camera might also be more practical for dynamic environments where the locations and shapes of the obstacles are changing. Since the factory, and thus the image of the obstacles, could be very large and the robot's path has to be determined in real-time, a parallel method for solving the path-planning problem directly on the image is desirable. 2 When solving computational-geometry problems for images in parallel, researchers have several different types of parallel machines available. The papers selected for this special issue consider four very commonly used ones: the parallel