Search

A number of applications in computer-aided manufacturing, CAD, and computer-aided geometric design ask for triangulating pieces of material with defects. These tasks are known collectively as constrained triangulations. Recently, a powerful architecture called the reconfigurable mesh has been proposed: In essence, a reconfigurable mesh consists of a mesh-connected architecture augmented by a dynamically reconfigurable bus system. The main contribution of this paper is to show that the flexibility of the reconfigurable mesh can be exploited for the purpose of obtaining constant-time algorithms for a number of constrained triangulation problems. These include triangulating a convex planar region containing any constant number of convex holes, triangulating a convex planar region in the presence of a collection of rectangular holes, and triangulating a set of ordered line segments. Specifically with a collection of O(n) such objects as input, our algorithms run in O(1) time on a reconfigurable mesh of size n/spl times/n. To the best of our knowledge, this is the first time constant time solutions to constrained triangulations are reported on this architecture.

Sorting is a fundamental problem with applications in all areas of computer science and engineering. In this work, we address the problem of sorting on mesh connected computers enhanced by endowing each row and each column with its own dedicated high-speed bus. This architecture, commonly referred to as a mesh with multiple broadcasting, is commercially available and has been adopted by the DAP family of multiprocessors. Somewhat surprisingly, the problem of sorting m, (m/spl les/n), elements on a mesh with multiple broadcasting of size /spl radic/n/spl times//spl radic/n has been studied, thus far, only in the sparse case, where m/spl isin//spl Theta/(/spl radic/n) and in the dense case, where m/spl isin//spl Theta/O(/spl radic/n). Yet, many applications require using an existing platform of size /spl radic/n/spl times//spl radic/n for sorting m elements, with /spl radic/n

Query processing is a crucial component of various application domains including information retrieval, database design and management, pattern recognition, robotics, and VLSI. Many of these applications involve data stored in a matrix satisfying a number of properties. One property that occurs time and again specifies that the rows and the columns of the matrix are independently sorted. It is customary to refer to such a matrix as sorted. An instance of the batched searching and ranking problem (BSR) involves a sorted matrix A of items from a totally ordered universe, along with a collection Q of queries. Q is an arbitrary mix of the following query types: for a search query q/sub j/, one is interested in an item of A that is closest to q/sub j/; for a rank query q/sub j/ one is interested in the number of items of A that are strictly smaller than q/sub j/. The BSR problem asks for solving all queries in Q. The authors consider the BSR problem in the following context: the matrix A is pretiled, one item per processor, onto an enhanced mesh of size /spl radic/n/spl times//spl radic/n; the m queries are stored, one per processor, in the first m//spl radic/n~ columns of the platform. Their main contribution is twofold. First, they show that any algorithm that solves the BSR problem must take at least /spl Omega/(max{logn, /spl radic/m}) time in the worst case. Second, they show that this time lower bound is tight on meshes of size /spl radic/n/spl times//spl radic/n enhanced with multiple broadcasting, by exhibiting an algorithm solving the BSR problem in /spl Theta/(max{logn, /spl radic/m}) time on such a platform.

The main contribution of this paper is to present simple and elegant podality-based algorithms for a variety of computational tasks motivated by, and finding applications to, pattern recognition, computer graphics, computational morphology, image processing, robotics, computer vision, and VLSI design. The problems that we address involve computing the convex hull, the diameter, the width, and the smallest area enclosing rectangle of a set of points in the plane, as well as the problems of finding the maximum Euclidian distance between two planar sets of points, and of constructing the Minkowski sum of two convex polygons. Specifically, we show that once we fix a positive constant /spl epsiv/, all instances of size m, (n/sup 1/2 +/spl epsiv///spl les/m/spl les/n) of the problems above, stored in the first [m//spl radic/n] columns of a mesh with multiple broadcasting of size /spl radic/n/spl times//spl radic/n can be solved time-optimally in /spl Theta/(m//spl radic/n) time.

Recently it has been noticed that for semigroup computations and for selection, rectangular meshes with multiple broadcasting yield faster algorithms than their square counterparts. The contribution of the paper is to provide yet another example of a fundamental problem for which this phenomenon occurs. Specifically, we show that the problem of computing the convex hull of a set of n sorted points in the plane can be solved in O(n/sup 1/8/ log /sup 3/4/) time on a rectangular mesh with multiple broadcasting of size n/sup 3/8/ log/sup 1/4/ n/spl times/n/sup 5/8//log/sup 1/4/n. The fastest previously known algorithms on a square mesh of size /spl radic/n/spl times//spl radic/n run in O(n/sup 1/6/) time in case the n points are pixels in a binary image, and in O(n/sup 1/6/log/sup 3/2/ n) time for sorted points in the plane.

Computing the convex hull of a planar set of points is one of the most extensively investigated topics in computational geometry. Our main contribution is to present the first known general-case, time- and VLSI-optimal, algorithm for convex hull computation on meshes with multiple broadcasting. Specifically, we show that for every choice of a positive integer constant c, the convex hull of a set of m(n/sup 1/2 + 1/2 c//spl les/m/spl les/n) points in the plane stored in the first [m//spl radic/n] columns of a mesh with multiple broadcasting of size /spl radic/n/spl times//spl radic/n can be computed in /spl Theta/(m//spl radic/n) time. Our algorithm features a very attractive additional property, namely that the time to input the data, the time to compute the convex hull, as well as the time to output the result are essentially the same. >

The main contribution of this work is to show that a number of digital geometry problems can be solved elegantly on meshes with multiple broadcasting by using a time-optimal solution to the leftmost one problem as a basic subroutine. Consider a binary image pretiled onto a mesh with multiple broadcasting of size [Formula: see text] one pixel per processor. Our first contribution is to prove an Ω(n1/6) time lower bound for the problem of deciding whether the image contains at least one black pixel. We then obtain time lower bounds for many other digital geometry problems by reducing this fundamental problem to all the other problems of interest. Specifically, the problems that we address are: detecting whether an image contains at least one black pixel, computing the convex hull of the image, computing the diameter of an image, deciding whether a set of digital points is a digital line, computing the minimum distance between two images, deciding whether two images are linearly separable, computing the perimeter, area and width of a given image. Our second contribution is to show that the time lower bounds obtained are tight by exhibiting simple O(n1/6) time algorithms for these problems. As previously mentioned, an interesting feature of these algorithms is that they use, directly or indirectly, an algorithm for the leftmost one problem recently developed by one of the authors.

Given a collection of objects in the plane along with a viewpoint /spl omega/, the visibility problem involves determining the portion of each object that is visible to an observer positioned at /spl omega/. The visibility problem is central to various application areas including computer graphics, image processing, VLSI design, and robot navigation, among many others. The main contribution of this work is to provide time-optimal solutions to this problem for several classes of objects, namely ordered line segments, disks, and iso-oriented rectangles in the plane. In addition, our visibility algorithm for line segments is at the heart of time-optimal solutions for determining, for each element in a given sequence of real numbers, the position of the nearest larger element within that sequence, triangulating a set of points in the plane, determining the visibility pairs among a set of vertical line segments, and constructing the dominance and visibility graphs of a set of iso-oriented rectangles in the plane. All the algorithms in this paper involve an input of size n and run in O(log n) time on a mesh with multiple broadcasting of size n/spl times/n. This is the first instance of time-optimal solutions for these problems on this architecture. >

The purpose of this paper is to demonstrate that the versatility of the reconfigurable mesh can be exploited to devise constant-time algorithms for a number of important computational tasks relevant to robotics, computer graphics, image processing, and computer vision. In all our algorithms, we assume that one or two n -vertex (convex) polygons are pretiled, one vertex per processor, onto a reconfigurable mesh of size √ n × √ n . In this setup, we propose constant-time solutions for testing an arbitrary polygon for convexity, solving the point location problem, solving the supporting lines problem, solving the stabbing problem, determining the minimum area/perimeter corner triangle for a convex polygon, determining the k -maximal vertices of a restricted class of convex polygons, constructing the common tangents of two separable convex polygons, deciding whether two convex polygons intersect, answering queries concerning two convex polygons, and computing the smallest distance between the boundaries of two convex polygons. To the best of our knowledge, this is the first time that O (1) time algorithms to solve dense instances of these problems are proposed on reconfigurable meshes.

Given a matrix of size √ n ×√ n with every entry being a 0 or a 1, the leftmost-one problem asks to determine the position of the leftmost 1, if any, in each row of the matrix. The leftmost-one problem finds applications in image processing, digitized geometry and computer graphics, among others. Recently, an O( n 1 6 ) time solution to the leftmost-one problem on a mesh with row buses has been proposed. However, the computational model assumes that processors have unbounded memory. We show that the problem can be solved in O( n 1 6 ) time on a √ n ×√ n mesh with row broadcasting, even if each processor has only a constant number of registers.

The main contribution of this work is to show that a number of seemingly unrelated problems in database design, pattern recognition, robotics, and image processing can be solved simply and elegantly by formulating them as instances of a general problem-the multiple query (MQ) problem. An arbitrary instance of the multiple query problem consists of a collection A={a/sub 1/, a/sub 2/, ..., a/sub n/} of items, a collection Q={q/sub 1/, q/sub 2/, ..., q/sub m/} (1/spl les/m/spl les/n) of queries, a decision problem /spl phi/:Q/spl times/A/spl rarr/{"yes", "no"}, and an associative and commutative function f operating on subsets of A. For every query q/sub i/, let S/sub i/ be the set of items a/sub j/ in A for which /spl phi/(q/sub i/, a/sub j/)="yes". The solution of q/sub i/ is defined to be f(S/sub i/). In this context, the multiple query problem involves solving all the queries in Q. We begin by showing that if the collections A and Q are stored one item and at most one query per processor on a mesh with multiple broadcasting of size /spl radic/n/spl times//spl radic/n then any algorithm that solves the MQ problem requires /spl Omega/(m1/3n1/6) time in the worst case. Second, we show that a number of fundamental problems can be solved simply and elegantly by formulating them as instances of the MQ problem.

Triangulating a set of points in the plane is a central theme in computer-aided manufacturing, robotics, CAD, VLSI design, geographic data processing, and computer graphics. Even more challenging are constrained triangulations, where a triangulation is sought in the presence of a number of constraints such as prescribed edges and/or forbidden areas. In this paper, we show that the flexibility of the reconfigurable mesh architecture can be exploited to obtain constant-time algorithms for a number of triangulation problems. These include triangulating an arbitrary set of points in the plane, a convex planar region with a convex hole, and a convex planar region in the presence of rectangular holes. Specifically, with a collection of O(n) such constraints as input, our algorithms run in O(1) time on a reconfigurable mesh of size n/spl times/n. To the best of our knowledge, these are the first constant time solutions to constrained triangulations reported on this architecture. >

Given a sequence of objects in the plane along with a viewpoint O, the visibility problem involves determining the portion of each object that is visible to an observer positioned at O. The main contribution of this work is to provide time-optimal solutions to this problem for two classes of objects, namely disks and iso-oriented rectangles in the plane. This problem is of importance in various fields like computer graphics, VLSI design, and robot navigation. Additionally, the visibility algorithm provides the basis for a time-optimal algorithm to triangulate a set of points in the plane. Specifically, all algorithms presented involve an input of size n and run in O(log n) time on a mesh with multiple broadcasting of site n/spl times/n. This is the first instance of time-optimal solutions for these problems on this architecture. >

Answering rank queries is a recurring operation in various application domains including geographic data processing, information retrieval, database design, information management, and medical image processing. Many of these applications involve data stored in a matrix satisfying a number of properties. One property that occurs time and again in applications specifies that the rows and the columns of the matrix are independently sorted. It is customary to refer to such a matrix as sorted. An instance of the Batched Ranking problem, (BR, for short) involves a sorted matrix A of items from a totally ordered universe, along with a collection Q of queries of the following type: for a query q/sub j/ one is interested in the number of items in A that are smaller than q/sub j/. The BR problem asks for solving all queries in Q. In this work, we consider the BR problem in the following context: the matrix A is pretiled, one item per processor, onto an enhanced mesh of size /spl radic/n/spl times//spl radic/n; the m queries are stored, one per processor, in the first m//spl radic/n columns of the platform. Our main contribution is twofold. First, we show that any algorithm that solves the BR problem must take at least /spl Omega/(log n+/spl radic/m) time in the worst case. Second, we show that this time lower bound is tight on meshes of size /spl radic/n/spl times//spl radic/n enhanced with multiple broadcasting, by exhibiting an algorithm solving the BR problem in O(log n+/spl radic/m) time on such a platform.

The compaction step of integrated circuit design motivates associating several kinds of graphs with a collection of non-overlapping rectangles in the plane. These graphs are intended to capture various visibility relations amongst the rectangles in the collection. The contribution of this paper is to propose time- and cost-optimal algorithms to construct two such graphs, namely, the dominance graph (DG, for short) and the visibility graph (VG, for short). Specifically, we show that with a collection of n non-overlapping rectangles as input, both these structures can be constructed in θ(log n) time using n processors in the CREW model.

Consider a binary image pretiled, one pixel per processor, onto mesh of size (root)n X (root)n, enhanced with row and column buses. Our first contribution is to show an (Omega) (n1/6) time lower bound for the problem of deciding whether the image contains at least one black pixel. We then obtain time lower bounds for many other digital geometry problems by reducing this fundamental problem to all the other problems of interest. Specifically, the problems that we address are: detecting whether an image contains at least one black pixel, computing the convex hull of the image, computing the diameter of an image, deciding whether a set of digital points is a digital line, computing the minimum distance between two images, deciding whether two images are linearly separable, computing the perimeter, area and width of a given image. Our second contribution is to show that the time lower bounds obtained are tight by exhibiting simple O(n1/6) time algorithms for these problems. An interesting feature of these algorithms is that they use, directly or indirectly, an algorithm for the leftmost one problem recently developed by one of the authors.© (1995) COPYRIGHT SPIE--The International Society for Optical Engineering. Downloading of the abstract is permitted for personal use only.

The purpose of this paper is to demonstrate that the versatility of the reconfigurable mesh can be exploited for the purpose of devising constant time algorithms for a number of important computational geometry tasks relevant to image processing, computer graphics, and computer vision. In all our algorithms we assume that one or two n-vertex (convex) polygons are pretiled, one vertex per processor, onto a reconfigurable mesh of size √n × √n. In this context, we propose constant-time solutions for testing an arbitrary polygon for convexity, solving the point location problem, the supporting lines problem, the stabbing problem, constructing the common tangents for separable convex polygons, deciding whether two convex polygons intersect, and computing the smallest distance between the boundaries of two convex polygons. To the best of our knowledge this is the first time that O(1) time algorithms are proposed for these problems on this architecture for the “dense” case. The proposed algorithms translate immediately into constant-time algorithms that work on binary images.

In this work, we present a time-and VLSI-optimal sorting algorithm for meshes with multiple broadcasting. Specifically, we show that for every choice of a positive integer constant c, m items \left( {n^{\frac{1} {2} + \frac{1} {{2c}}} \leqslant m \leqslant n} \right) stored in the first \left\lceil {\frac{m} {{\sqrt n }}} \right\rceil columns of a mesh with multiple broadcasting of size \sqrt {n} x \sqrt {n} can be sorted in O({\frac{m} {{\sqrt n }}}) time.

The main goal of this work is to fathom the suitability of the mesh with multiple broadcasting architecture (MMB) for some tree-related computations. We view our contribution at two levels: on the one hand, we exhibit time lower bounds for a number of tree-related problems on the MMB. On the other hand, we show that these lower bounds are tight by exhibiting time-optimal tree algorithms on the MMB. Specifically, we show that the task of encoding and/or decoding n-node binary and ordered trees cannot be solved faster than Ω(log n) time even if the MMB has an infinite number of processors. We then go on to show that this lower bound is tight. We also show that the task of reconstructing n-node binary trees and ordered trees from their traversais can be performed in O(1) time on the same architecture. Our algorithms rely on novel time-optimal algorithms on sequences of parentheses that we also develop.