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.     

Parallel methods for visibility and shortest-path problems in simple polygons

In this paper we give efficient parallel algorithms for solving a number of visibility and shortest-path problems for simple polygons. Our algorithms all run inO(logn) time and are based on the use of a new data structure for implicitly representing all shortest paths in a simple polygonP, which we call thestratified decomposition tree. We use this approach to derive efficient parallel methods for computing the visibility ofP from an edge, constructing the visibility graph of the vertices ofP (using an output-sensitive number of processors), constructing the shortest-path tree from a vertex ofP, and determining all-farthest neighbors for the vertices inP. The computational model we use is the CREW PRAM.     

Parallel methods for visibility and shortest-path problems in simple polygons

In this paper we give efficient parallel algorithms for solving a number of visibility and shortest-path problems for simple polygons. Our algorithms all run inO(logn) time and are based on the use of a new data structure for implicitly representing all shortest paths in a simple polygonP, which we call thestratified decomposition tree. We use this approach to derive efficient parallel methods for computing the visibility ofP from an edge, constructing the visibility graph of the vertices ofP (using an output-sensitive number of processors), constructing the shortest-path tree from a vertex ofP, and determining all-farthest neighbors for the vertices inP. The computational model we use is the CREW PRAM.This research was announced in preliminary form in theProceedings of the 6th ACM Symposium on Computational Geometry, 1990, pp. 73–82. The research of Michael T. Goodrich was supported by the National Science Foundation under Grants CCR-8810568 and CCR-9003299, and by the NSF and DARPA under Grant CCR-8908092.     

Dispersion in Disks

We present three new approximation algorithms with improved constant ratios for selecting n points in n disks such that the minimum pairwise distance among the points is maximized.

1. A very simple O(nlog?n)-time algorithm with ratio 0.511 for disjoint unit disks.
2. An LP-based algorithm with ratio 0.707 for disjoint disks of arbitrary radii that uses a linear number of variables and constraints, and runs in polynomial time.
3. A hybrid algorithm with ratio either 0.4487 or 0.4674 for (not necessarily disjoint) unit disks that uses an algorithm of Cabello in combination with either the simple O(nlog?n)-time algorithm or the LP-based algorithm.

The LP algorithm can be extended for disjoint balls of arbitrary radii in ? ^d , for any (fixed) dimension d, while preserving the features of the planar algorithm. The algorithm introduces a novel technique which combines linear programming and projections for approximating Euclidean distances. The previous best approximation ratio for dispersion in disjoint disks, even when all disks have the same radius, was 1/2. Our results give a positive answer to an open question raised by Cabello, who asked whether the ratio 1/2 could be improved.     

Broadcasting in All-Output-Port Meshes of Trees with Distance-Insensitive Switching

Meshes of trees are hybrids of meshes and trees with outstanding properties, namely small degree and diameter and large bisection width. Moreover, they are known to be area universal, i.e., they can simulate any network with the same wire area with only a polylogarithmic slowdown. Meshes of trees are known to outperform meshes in execution of algorithms with local communication patterns, e.g., sorting, for which distance-sensitive switching, such as store-and-forward, suffices. Nowadays, parallel machines use distance-insensitive, e.g., wormhole, switching. A challenging problem is to design optimal or efficient algorithms for one-to-all broadcast in all-output-port networks with distance-insensitive switching, since the lower bound on the number of rounds, log_Δ+1N, where Δ is the node degree, is very strict. This problem has been solved for tori and hypercubes quite recently. In this paper, we present nearly optimal algorithms for one-to-all broadcast in both square and rectangular 2-D meshes of trees and cube 3-D meshes of trees. The algorithms need at most one round more than the trivial lower bound. We also show requirements for deadlock-free execution of the algorithms. Meshes of trees are not node-symmetric, they are not even regular. This paper shows that, in contrast to meshes, the irregularity is not an obstacle for designing efficient schemes for such an intensive communication pattern, as the all-output-port broadcast.     

Simple algorithms for searching a polygon with flashlights

The k-searcher is a mobile guard whose visibility is limited to k rays emanating from her position, where the direction of each ray can be changed continuously with bounded angular rotation speed. Given a polygonal region P, is it possible for the k-searcher to eventually see a mobile intruder that is arbitrarily faster than the searcher within P? We present O(n²)-time algorithms for constructing a search schedule of the 1-searcher and the 2-searcher, respectively. Our framework for the 1-searcher can be viewed as a modification of that of LaValle et al. [Proc. 16th ACM Symp. on Computational Geometry, 2000, pp. 260-269] and is naturally extended for the 2-searcher.     

Optimal parallel algorithms for point-set and polygon problems

In this paper we give parallel algorithms for a number of problems defined on point sets and polygons. All our algorithms have optimalT(n) * P(n) products, whereT(n) is the time complexity andP(n) is the number of processors used, and are for the EREW PRAM or CREW PRAM models. Our algorithms provide parallel analogues to well-known phenomena from sequential computational geometry, such as the fact that problems for polygons can oftentimes be solved more efficiently than point-set problems, and that nearest-neighbor problems can be solved without explicitly constructing a Voronoi diagram.     

Systolic algorithms for computing the visibility polygon and triangulation of a polygonal region

This paper first presents a naive systolic algorithm for finding a closest point for each of n given points in linear time. Then, based on the algorithm, we propose linear-time systolic algorithms for the computation of the visibility polygon and for the trapezoidal partition or triangulation of a polygonal region which may contain holes. The visibility problem among n vertical line segments in the plane is also solved.     

A fast algorithm for computing sparse visibility graphs

AnO(¦E¦log² n) algorithm is presented to construct the visibility graph for a collection ofn nonintersecting line segments, where ¦E¦ is the number of edges in the visibility graph. This algorithm is much faster than theO(n ²)-time andO(n ²)-space algorithms by Asanoet al., and by Welzl, on sparse visibility graphs. Thus we partially resolve an open problem raised by Welzl. Further, our algorithm uses onlyO(n) working storage.     

Optimal algorithms for rectangle problems on a mesh-connected computer

In this paper, Mesh-Connected Computer (MCC) algorithms for computing several properties of a set of, possibly intersecting rectangles are presented. Given a set of n iso-oriented rectangles, we describe MCC algorithms for determining the following properties: (i) the area of the logic “OR” of these rectangles (i.e., the area of the region covered by at least one rectangle); (ii) the area of the union of pairwise “AND” of the rectangles (i.e., the area of the region covered by two or more rectangles); (iii) the largest number of rectangles that overlap (this solves the fixed-size rectangle placement problem, i.e., given a set of planar points and a rectangle, find a placement of the rectangle in the plane so that the number of points covered by the rectangle is maximal); (iv) the minimum separation between any pair of a set of nonoverlapping rectangles. All these algorithms can be implemented on a 2√n × 2√n MCC in O(√n) time which is optimal. The algorithms compare favorably with the known sequential algorithms that have O(n log n) time complexity.     

Parallel geometric algorithms on a mesh-connected computer

We show that a number of geometric problems can be solved on a √n × √n mesh-connected computer (MCC) inO(√n) time, which is optimal to within a constant factor, since a nontrivial data movement on an MCC requires Ω(√n) time. The problems studied here include multipoint location, planar point location, trapezoidal decomposition, intersection detection, intersection of two convex polygons, Voronoi diagram, the largest empty circle, the smallest enclosing circle, etc. TheO(√n) algorithms for all of the above problems are based on the classical divide-and-conquer problem-solving strategy.     

Exact algorithms for the two-dimensional guillotine knapsack

The two-dimensional knapsack problem requires to pack a maximum profit subset of “small” rectangular items into a unique “large” rectangular sheet. Packing must be orthogonal without rotation, i.e., all the rectangle heights must be parallel in the packing, and parallel to the height of the sheet. In addition, we require that each item can be unloaded from the sheet in stages, i.e., by unloading simultaneously all items packed at the same either y or x coordinate. This corresponds to use guillotine cuts in the associated cutting problem.In this paper we present a recursive exact procedure that, given a set of items and a unique sheet, constructs the set of associated guillotine packings. Such a procedure is then embedded into two exact algorithms for solving the guillotine two-dimensional knapsack problem. The algorithms are computationally evaluated on well-known benchmark instances from the literature.The C++ source code of the recursive procedure is available upon request from the authors.     

Combining Decision Algorithms for Matching in the Union of Disjoint Equational Theories

This paper addresses the problem of systematically building a matching algorithm for the union of two disjoint theoriesE₁∪E₂provided that matching algorithms are known in both theoriesE₁andE₂. In general, the blind use of combination techniques introduces unification. Two different restrictions are considered in order to reduce this unification to matching. First, we show that combining matching algorithms (with linear constant restriction) is always sufficient for solving a pure fragment of combined matching problems. Second, the investigated method is complete for the largest class of theories where unification is not needed, including regular collapse-free theories and linear theories. Syntactic conditions are given to define this class of theories in which solving the combined matching problem is performed in a modular way.     

Layered interval codes for TCAM-based classification

Ternary content-addressable memories (TCAMs) are increasingly used for high-speed packet classification. TCAMs compare packet headers against all rules in a classification database in parallel and thus provide high throughput.TCAMs are not well-suited, however, for representing rules that contain range fields and previously published algorithms typically represent each such rule by multiple TCAM entries. The resulting range expansion can dramatically reduce TCAM utilization because it introduces a large number of redundant TCAM entries. This redundancy can be mitigated by making use of extra bits, available in each TCAM entry.We present a scheme for constructing efficient representations of range rules, based on the simple observation that sets of disjoint ranges may be encoded much more efficiently than sets of overlapping ranges. Since the ranges in real-world classification databases are, in general, non-disjoint, the algorithms we present split ranges between multiple layers, each of which consists of mutually disjoint ranges. Each layer is then coded and assigned its own set of extra bits.Our layering algorithms are based on approximations for specific variants of interval-graph coloring. We evaluate these algorithms by performing extensive comparative analysis on real-life classification databases. Our analysis establishes that our algorithms reduce the number of redundant TCAM entries caused by range rules by more than 60% as compared with best range-encoding prior work.     

Computing H-Joins with Application to 2-Modular Decomposition

We present here a general framework to design algorithms that compute H-join. For a given bipartite graph H, we say that a graph G admits a H-join decomposition or simply a H-join, if the vertices of G can be partitioned in |H| parts connected as in H. This graph H is a kind of pattern, that we want to discover in G. This framework allows us to present fastest known algorithms for the computation of P ₄-join (aka N-join), P ₅-join (aka W-join), C ₆-join (aka 6-join). We also generalize this method to find a homogeneous pair (also known as 2-module), a pair {M ₁,M ₂} such that for every vertex x?(M ₁∪M ₂) and i∈{1,2}, x is either adjacent to all vertices in M _i or to none of them. First used in the context of perfect graphs (Chvátal and Sbihi in Graphs Comb. 3:127–139, 1987), it is a generalization of splits (a.k.a. 1-joins) and of modules. The algorithmics to compute them appears quite involved. In this paper, we describe an O(mn ²)-time algorithm computing all maximal homogeneous pairs of a graph, which not only improves a previous bound of O(mn ³) for finding only one pair (Everett et al. in Discrete Appl. Math. 72:209–218, 1997), but also uses a nice structural property of homogenous pairs, allowing to compute a canonical decomposition tree for sesquiprime graphs (i.e., graphs G having no module and such that for every vertex v∈G, G?v also has no module).     

Computing convexity properties of images on a pyramid computer

We present efficient parallel algorithms for using a pyramid computer to determine convexity properties of digitized black/white pictures and labeled figures. Algorithms are presented for deciding convexity, identifying extreme points of convex hulls, and using extreme points in a variety of fashions. For a pyramid computer with a base ofn simple processing elements arranged in ann ^1/2 ×n ^1/2 square, the running times of the algorithms range from Θ(logn) to find the extreme points of a convex figure in a digitized picture, to Θ(n ^1/6) to find the diameter of a labeled figure, Θ(n ^1/4 logn) to find the extreme points of every figure in a digitized picture, to Θ(n ^1/2) to find the extreme points of every labeled set of processing elements. Our results show that the pyramid computer can be used to obtain efficient solutions to nontrivial problems in image analysis. We also show the sensitivity of efficient pyramid-computer algorithms to the rate at which essential data can be compressed. Finally, we show that a wide variety of techniques are needed to make full and efficient use of the pyramid architecture.     

Unification in the Union of Disjoint Equational Theories: Combining Decision Procedures

Most of the work on the combination of unification algorithms for the union of disjoint equational theories has been restricted to algorithms that compute finite complete sets of unifiers.Thus the developed combination methods usually cannot be used to combine decision procedures,i.e., algorithms that just decide solvability of unification problems without computing unifiers.In this paper we describe a combination algorithm for decision procedures that works for arbitrary equational theories, provided that solvability of so–called unification problems with constant restrictions—a slight generalization of unification problems with constants—is decidable for these theories.As a consequence of this new method, we can, for example, show that generalA-unifiability, i.e.,solvability ofA-unification problems with free function symbols, is decidable. HereAstandsfor the equational theory of one associative function symbol.Our method can also be used to combine algorithms that compute finite complete sets of unifiers. Manfred Schmidt–Schauß' combination result, the until now most general result in this direction, can be obtained as a consequence of this fact.We also obtain the new result that unification in the union of disjoint equational theories is finitary, if general unification—i.e., unification of terms with additional free function symbols—is finitary in the single theories.     

Multidimensional analogs of the kendall equation for priority queueing systems: computational aspects

An analogy between celebrated Kendall equation for busy periods in the system M|GI|1 and analytical results for busy periods in the priority systemsM _r |GI _r |1 is drawn. These results can be viewed as generalizations of the functional Kendall equation. The methodology and algorithms of numerical solution of recurrent functional equations which appear in the analysis of such queueing systems are developed. The efficiency of the algorithms is achieved by acceleration of the numerical procedure of solving the classical Kendall equation. An algorithm of calculation of the system workload coefficient calculation is given.     

Parallel bioinspired algorithms for NP complete graph problems

It is no longer believed that DNA computing will outperform digital computers when it comes to the computation of intractable problems. In this paper, we emphasise the in silico implementation of DNA-inspired algorithms as the only way to compete with other algorithms for solving NP-complete problems. For this, we provide sticker algorithms for some of the most representative NP-complete graph problems. The simple data structures and bit-vertical operations make them suitable for some parallel architectures. The parallel algorithms might solve either moderate-size problems in an exact manner or, when combined with a heuristic, large problems in polynomial time.     

An efficient parallel algorithm for finding rectangular duals of plane triangular graphs

We present an efficient parallel algorithm for constructing rectangular duals of plane triangular graphs. This problem finds applications in VLSI design and floor-planning problems. No NC algorithm for solving this problem was previously known. The algorithm takesO(log² n) time withO(n) processors on a CRCW PRAM, wheren is the number of vertices of the graph.This research was supported by NSF Grants CCR-9011214 and CCR-9205982.