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.This work was supported in part by the National Science Foundation under Grant DCR 8420814. A preliminary version was presented in the 1987 FJCC, Dallas, TX.     

An Efficient Algorithm for Ray Tracing

This paper presents a new algorithm that performs more efficient ray tracing compared to existing algorithms. This algorithm is based on the divide-and-conquer technique well known from the area of lists sorting, and speeds up the intersections and light-visibility tests for the first hit. A new definition of transitive-between-relations (TBR) is introduced. A simple shooting ray guide is embedded into a conventional ray tracer to reduce the number of intersection tests and thus speed-up the first hit calculation and the associated light conditions tests. The algorithm was tested in environments made up of convex polygons (random triangles, linearly positioned pyramids) but it can be used in environments with other primitives.     

Global bifurcation sets and stable projections of nonsingular algebraic surfaces

The view graph of a surface is a planar graph whose nodes are the stable views (projections) of the surface and whose edges represent transitional views of codimension one. The space of all directions of orthogonal projection can be identified with the projective plane. The set of bad projection directions, associated with the degenerate views of positive codimension, forms a graph in the projective plane (the view bifurcation set). This graph is dual to the view graph and divides the projective plane into a certain number of connected regions whose representatives are the nodes of the view graph. We assume that the projected surface is nonsingular and parameterized by polynomials of degree d. We present an estimate for the number of nodes in the view graph in terms of d and describe symbolic algorithms for computing the bifurcation set and the view graph of a surface from a parametrization.     

Coordinated motion planning for two independent robots

We present anO(n ²) algorithm for planning a coordinated collision-free motion of two independent robot systems of certain kinds, each having two degrees of freedom, which move in the plane amidst polygonal obstacles having a total ofn corners. We exemplify our technique in the case of two planar Stanford arms, but also discuss the case of two discs or convex translating objects. The algorithm improves previous algorithms for this kind of problems, and can be extended to a fairly simple general technique for obtaining efficient coordinated motion planning algorithms.     

Context-free graph languages of bounded degree are generated by apex graph grammars

The apex graph grammars generate precisely the context-free graph languages of bounded degree, independently of whether one considers hyperedge replacement systems or (boundary or confluent) NLC or edNCE graph grammars. The main feature of apex graph grammars is that nodes cannot be passed from nonterminal to nonterminal. The proof is based on a normal form result for arbitrary hyperedge replacement systems that forbids passing chains. This generalizes Greibach Normal Form.     

A general proof rule for procedures in predicate transformer semantics

Summary A proof rule for the procedure call is derived for procedures with value, result and value-result parameters. It is extended to procedures with unrestricted global variables and to recursive procedures. Like D. Gries's proof rule, it is based on the substitution rule for assignment. However, it is more general and much simpler to apply. Assume that {U} S {V} has been proved about the procedure body S. The proof rule for determining whether a call establishes predicate E is based on finding an adaptation A satisfying AV E, where E is derived from E by some substitution of parameters.     

Soft computing in engineering design: a hybrid dual cross-mapping neural network model

Contemporary design process requires the development of a new computational intelligence or soft computing methodology that involves intelligence integration and hybrid intelligent systems for design, analysis and evaluation, and optimization. This paper first presents a discussion of the need to incorporate intelligence into an automated design process and the various constraints that designers face when embarking on industrial design projects. Then, it presents the design problem as optimizing the design output against constraints and the use of soft computing and hybrid intelligent systems techniques. In this paper, a soft-computing-integrated intelligent design framework is developed. A hybrid dual cross-mapping neural network (HDCMNN) model is proposed using the hybrid soft computing technique based on cross-mapping between a back-propagation network (BPNN) and a recurrent Hopfield network (HNN) for supporting modeling, analysis and evaluation, and optimization tasks in the design process. The two networks perform different but complementary tasks—the BPNN decides if the design problem is a type 0 (rational) or type 1 (non-rational) problem, and the output layer weights are then used as the energy function for the HNN. The BPNN is used for representing design patterns, training classification boundaries, and outputting network weight values to the HNN, and then the HNN uses the calculated network weight values to evaluate and modify or re-design the design patterns. The developed system provides a unified soft-computing-integrated intelligent design framework with both symbolic and computational intelligence. The system has self-modifying and self-learning functions. Within the system, only one network training is needed for accomplishing the evaluation, rectification/modification, and optimization tasks in the design process. Finally, two case studies are provided to illustrate and validate the developed model and system.     

Expert systems and computer-controlled decision making in medicine

The search for usable expert systems is leading somemedical researchers to question the appropriate role of these programs. Most current systems assume a limited role for the human user, delegating situated decision-control to the machine. As expert systems are only able to replace a narrow range of human intellectual functions, this leaves the programs unable to cope with the constructivist nature of human knowledge-use. In returning practical control to the human doctor, some researchers are abandoning focusedproblem-solving in favour of supportiveproblem-analysis. Using ONCOCIN and QMR as examples, this article contrasts these approaches and suggests that the latter avoids many of the difficulties currently facing medical expert systems.After hearing for several decades that computers will soon be able to assist with difficult diagnoses, the practicing physician may well wonder why the the revolution has not occurred. Scepticism at this point is understandable. Few, if any, programs currently have active roles as consultants to physicians (Schwartz, Patil and Szolovits, 1987, p. 685)     

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.     

Edge crossings in drawings of bipartite graphs

Systems engineers have recently shown interest in algorithms for drawing directed graphs so that they are easy to understand and remember. Each of the commonly used methods has a step which aims to adjust the drawing to decrease the number of arc crossings. We show that the most popular strategy involves an NP-complete problem regarding the minimization of the number of arcs in crossings in a bipartite graph. The performance of the commonly employed barycenter heuristic for this problem is analyzed. An alternative method, the median heuristic, is proposed and analyzed. The new method is shown to compare favorably with the old in terms of performance guarantees. As a bonus, we show that the median heuristic performs well with regard to the total length of the arcs in the drawing.     

The input/output complexity of transitive closure

Suppose a directed graph has its arcs stored in secondary memory, and we wish to compute its transitive closure, also storing the result in secondary memory. We assume that an amount of main memory capable of holdings values is available, and thats lies betweenn, the number of nodes of the graph, ande, the number of arcs. The cost measure we use for algorithms is theI/O complexity of Kung and Hong, where we count 1 every time a value is moved into main memory from secondary memory, or vice versa.In the dense case, wheree is close ton ², we show that I/O equal toO(n ³/s) is sufficient to compute the transitive closure of ann-node graph, using main memory of sizes. Moreover, it is necessary for any algorithm that is standard, in a sense to be defined precisely in the paper. Roughly, standard means that paths are constructed only by concatenating arcs and previously discovered paths. For the sparse case, we show that I/O equal toO(n ²e/s) is sufficient, although the algorithm we propose meets our definition of standard only if the underlying graph is acyclic. We also show that(n ²e/s) is necessary for any standard algorithm in the sparse case. That settles the I/O complexity of the sparse/acyclic case, for standard algorithms. It is unknown whether this complexity can be achieved in the sparse, cyclic case, by a standard algorithm, and it is unknown whether the bound can be beaten by nonstandard algorithms.We then consider a special kind of standard algorithm, in which paths are constructed only by concatenating arcs and old paths, never by concatenating two old paths. This restriction seems essential if we are to take advantage of sparseness. Unfortunately, we show that almost another factor ofn I/O is necessary. That is, there is an algorithm in this class using I/OO(n ³e/s) for arbitrary sparse graphs, including cyclic ones. Moreover, every algorithm in the restricted class must use(n ³e/s/log³ n) I/O, on some cyclic graphs.The work of this author was partially supported by NSF grant IRI-87-22886, IBM contract 476816, Air Force grant AFOSR-88-0266 and a Guggenheim fellowship.     

Optimal algorithms for symmetry detection in two and three dimensions

Exact algorithms for detecting all rotational and involutional symmetries in point sets, polygons and polyhedra are described. The time complexities of the algorithms are shown to be (n) for polygons and (n logn) for two- and three-dimensional point sets. (n logn) time is also required for general polyhedra, but for polyhedra with connected, planar surface graphs (n) time can be achieved. All algorithms are optimal in time complexity, within constants.     

Shortest noncrossing paths in plane graphs

Let G be an undirected plane graph with nonnegative edge length, and letk terminal pairs lie on two specified face boundaries. This paper presents an algorithm for findingk noncrossing paths inG, each connecting a terminal pair, and whose total length is minimum. Noncrossing paths may share common vertices or edges but do not cross each other in the plane. The algorithm runs in timeO(n logn) wheren is the number of vertices inG andk is an arbitrary integer.     

The plane with parallel coordinates

By means ofParallel Coordinates planar graphs of multivariate relations are obtained. Certain properties of the relationship correspond tothe geometrical properties of its graph. On the plane a point line duality with several interesting properties is induced. A new duality betweenbounded and unbounded convex sets and hstars (a generalization of hyperbolas) and between Convex Unions and Intersections is found. This motivates some efficient Convexity algorithms and other results inComputational Geometry. There is also a suprising cusp inflection point duality. The narrative ends with a preview of the corresponding results inR ^N .     

Low-Rank Approximation of Integral Operators by Interpolation

A central component of the analysis of panel clustering techniques for the approximation of integral operators is the so-called -admissibility condition min {diam(),diam()} 2dist(,) that ensures that the kernel function is approximated only on those parts of the domain that are far from the singularity. Typical techniques based on a Taylor expansion of the kernel function require a subdomain to be far enough from the singularity such that the parameter has to be smaller than a given constant depending on properties of the kernel function. In this paper, we demonstrate that any is sufficient if interpolation instead of Taylor expansionisused for the kernel approximation, which paves the way for grey-box panel clustering algorithms.     

Backtracking Problem in the Traversal of an Unknown Directed Graph by a Finite Robot

A covering path in a directed graph is a path passing through all vertices and arcs of the graph, with each arc being traversed only in the direction of its orientation. A covering path exists for any initial vertex only if the graph is strongly connected. The traversal of an unknown graph implies that the topology of the graph is not a priori known, and we learn it only in the course of traversing the graph. This is similar to the problem of traversing a maze by a robot in the case where the plan of the maze is not available. If the robot is a general-purpose computer without any limitations on the number of its states, then traversal algorithms with the estimate O(nm) are known, where n is the number of vertices and m is the number of arcs. If the number of states is finite, then this robot is a finite automaton. Such a robot is an analogue of the Turing machine, where the tape is replaced by a graph and the cells are assigned to the graph vertices and arcs. The selection of the arc that has not been traversed yet among those originating from the current vertex is determined by the order of the outgoing arcs, which is a priori specified for each vertex. The best known traversal algorithms for a finite robot are based on constructing the output directed spanning tree of the graph with the root at the initial vertex and traversing it with the aim to find all untraversed arcs. In doing so, we face the backtracking problem, which consists in searching for all vertices of the tree in the order inverse to their natural partial ordering, i.e., from the leaves to the root. Therefore, the upper estimate of the algorithms is different from the optimal estimate O(nm) by the number of steps required for the backtracking along the outgoing tree. The best known estimate O(nm + n ²loglogn) has been suggested by the author in the previous paper [1]. In this paper, a finite robot is suggested that performs a backtracking with the estimate O(n ²log*(n)). The function log* is defined as an integer solution of the inequality 1 log₂ ^log*(n) < 2, where log ^t = log º log º ... º log (the superposition º is applied t – 1 times) is the tth compositional degree of the logarithm. The estimate O(nm + n ²log*(n)) for the covering path length is valid for any strongly connected graph for a certain (unfortunately, not arbitrary) order of the outgoing arcs. Interestingly, such an order of the arcs can be marked by symbols of the finite robot traversing the graph. Hence, there exists a robot that traverses the graph twice: first traversal with the estimate O(nm + n ²loglogn) and the second traversal with the estimate O(nm + n ²log*(n)).     

Decomposition and intersection of simple splinegons

A splinegon is a polygon whose edges have been replaced by well-behaved curves. We show how to decompose a simple splinegon into a union of monotone pieces and into a union of differences of unions of convex pieces. We also show how to use a fast triangulation algorithm to test whether two given simple splinegons intersect. We conclude with examples of splinegons that make the extension of algorithms from polygons to splinegons difficult.Work on this paper by David A. Dobkin and Diane L. Souvaine was partially supported by National Science Foundation Grants MCS 83-03926 and DCR 85-05517. Diane L. Souvaine was also partially supported by an Exxon Foundation Fellowship.     

(Incremental) Priority Algorithms

We study the question of which optimization problems can be optimally or approximately solved by greedy or greedy-like algorithms. For definiteness, we limit the present discussion to some well-studied scheduling problems although the underlying issues apply in a much more general setting. Of course, the main benefit of greedy algorithms lies in both their conceptual simplicity and their computational efficiency. Based on the experience from online competitive analysis, it seems plausible that we should be able to derive approximation bounds for greedy-like algorithms exploiting only the conceptual simplicity of these algorithms. To this end, we need (and will provide) a precise definition of what we mean by greedy and greedy-like.     

On-line Learning and the Metrical Task System Problem

The problem of combining expert advice, studied extensively in the Computational Learning Theory literature, and the Metrical Task System (MTS) problem, studied extensively in the area of On-line Algorithms, contain a number of interesting similarities. In this paper we explore the relationship between these problems and show how algorithms designed for each can be used to achieve good bounds and new approaches for solving the other. Specific contributions of this paper include: An analysis of how two recent algorithms for the MTS problem can be applied to the problem of tracking the best expert in the decision-theoretic setting, providing good bounds and an approach of a much different flavor from the well-known multiplicative-update algorithms. An analysis showing how the standard randomized Weighted Majority (or Hedge) algorithm can be used for the problem of combining on-line algorithms on-line, giving much stronger guarantees than the results of Azar, Y., Broder, A., & Manasse, M. (1993). Proc ACM-SIAM Symposium on Discrete Algorithms (pp. 432–440) when the algorithms being combined occupy a state space of bounded diameter. A generalization of the above, showing how (a simplified version of) Herbster and Warmuth's weight-sharing algorithm can be applied to give a finely competitive bound for the uniform-space Metrical Task System problem. We also give a new, simpler algorithm for tracking experts, which unfortunately does not carry over to the MTS problem.Finally, we present an experimental comparison of how these algorithms perform on a process migration problem, a problem that combines aspects of both the experts-tracking and MTS formalisms.     

Minimum dominating cycles in outerplanar graphs

Adominating cycle of a graph lies at a distance of at most one from all the vertices of the graph. The problem of finding the minimum size of such a cycle is proved to be difficult even when restricted to planar graphs. An efficient algorithm solving this problem is given for the class of two-connectedouterplanar graphs, in which all vertices lie on the exterior face in a plane embedding of the graph.On leave from Institute of Computer Science, University of Wrocaw, Wrocaw, Poland.