Proximity problems for points on a rectilinear plane with rectangular obstacles

We consider the following four problems for a setS ofk points on a plane, equipped with the rectilinear metric and containing a setR ofn disjoint rectangular obstacles (so that distance is measured by a shortest rectilinear path avoiding obstacles inR): (a) find aclosest pair of points inS, (b) find anearest neighbor for each point inS, (c) compute the rectilinearVoronoi diagram ofS, and (d) compute a rectilinearminimal spanning tree ofS. We describeO ((n+k) log(n+k))-time sequential algorithms for (a) and (b) based onplane-sweep, and the consideration of geometrically special types of shortest paths, so-calledz-first paths. For (c) we present anO ((n+k) log(n+k) logn)-time sequential algorithm that implements a sophisticateddivide-and-conquer scheme with an addedextension phase. In the extension phase of this scheme we introduce novel geometric structures, in particular so-calledz-diagrams, and techniques associated with the Voronoi diagram. Problem (d) can be reduced to (c) and solved inO ((n+k) log(n+k) logn) time as well. All our algorithms arenear-optimal, as well as easy to implement. An extended abstract appeared inProc. 13th Conf. on the Foundations of Software Technology and Theoretical Computer Science, Bombay, 1993, Springer-Verlag, pp. 218–227. Sumanta Guha was supported in part by a UW-Milwaukee Graduate School Research Committee Award. Ichiro Suzuki was supported in part by the National Science Foundation under Grants CCR-9004346 and IRI-9307506, the Office of Naval Research under Grant N00014-94-1-0284, and an endowed chair supported by Hitachi Ltd. at the Faculty of Engineering Science, Osaka University.     

A CFD Analysis of Ventilation Effectiveness in a Partitioned Room

A numerical model has been developed to investigate the contaminant removal and air freshness in a ventilated two-zone enclosure. The average contaminants and the distributions of air age in each zone under variable positions of door, supply and exhaust are compared. The correlation between the average contaminants and each of the main parameters, such as door location, supply and exhaust positions etc., are presented, and the average air ages in both zones are illustrated against door position. It is found that the average air age in the upstream zone is less affected by the door position than that in the downstream zone, and that the door position near the side-walls seems to give better air circulation. It is also concluded that the supply and door positions affect the concentration in the upstream zone significantly, while the exhaust location does not seem to influence the average concentration in either the upstream or the downstream zone.     

The numerical modeling of acoustic wave propagation using the multiple pressure variables approach

Based on an asymptotic analysis of the compressible Navier–Stokes equations, the basic concept of the Multiple Pressure Variables (MPV) approach is to split up the pressure into three different terms representing global background effects, acoustic waves and the incompressible pressure, respectively. Special attention is payed to aeroacoustic phenomena and the numerical treatment of the generation and spreading of sound waves. To this aim, further perturbation analysis is done about the incompressible limit solution. This gives hints how to extract acoustic waves responsible for the noise generation from the flow field.This work has been supported by Deutsche Forschungsgemeinschaft (DFG).     

Molecular image-processing devices based on chemical reaction systems. I: General principles for implementation

Potentialities for implementing simple neural information-processing devices based on chemical and biochemical dynamical media are discussed. Pilot ‘hardware’ models of neural molecualr devices that able to perform image-processing operations were constructed.     

Generation of configuration space obstacles: The case of moving algebraic curves

We present algebraic algorithms to generate the boundary of planar configuration space obstacles arising from the translatory motion of objects among obstacles. Both the boundaries of the objects and obstacles are given by segments of algebraic plane curves.Research supported in part by NSF Grant MIP-85-21356 and a David Ross Fellowship. An earlier version of this paper appeared in theProceedings of the 1987 IEEE International Conference on Robotics and Automation, pp. 979–984.     

Simulation of heat transfer and hydrodynamics for metal structured packed bed

Modeling and simulation based on computational hydrodynamics and heat transfer for metal structured packed bed are carried out to predict the flow field and temperature field, and to evaluate its performance in transport aspect. The comparison between the simulation results for the metal structured packed bed and the experimental heat transfer performance as well as pressure drop of the conventional pellet packed bed is made, which quantitatively validates that transport performance of the metal structured packed bed is much better. Furthermore, the effects of geometric parameters and the property of solid phase on heat transfer of the metal structured packed bed are discussed. It is found that at low Re, the specific surface area is a key factor to determine the heat transfer capability of the structured bed. However, when Re turns to be high, the property of solid phase and voidage of the structured packed bed will play an important role in the evaluation of its heat transfer. In light of above results, some feasible methods are available to enhance the heat transfer performance.     

O(log logn)-time integer geometry on the CRCW PRAM

We study problems in computational geometry on PRAMs under the assumption that input objects are specified by points withO(logn)-bit coordinates, or, equivalently, with polynomially bounded integer coordinates. We show that in this setting many geometric problems can be solved in time O(log logn). The following five specific problems are investigated:closest pair of points, intersection of convex polygons, intersection of manhattan line segments, dominating set, andlargest empty square. Algorithms solving them are developed which operate in time O(log logn) on the arbitrary CRCW PRAM. The number of processors used is eitherO(n) orO(n logn).This research was supported in part by Grants KBN 2-2044-92-03, KBN 2-2043-92-03, and KBN 2-1190-91-01.     

On the analysis of cooperation and antagonism in networks of communicating processes

We propose a new method for the analysis of cooperative and antagonistic properties of communicating finite state processes (FSPs). This algebraic technique is based on a composition operator and on the notion of possibility equivalence among FSPs. We demonstrate its utility by showing that potential blocking, termination, and lockout can be decided in polynomial time for loosely connected networks of tree FSPs. Potential blocking and termination are examples of cooperative properties, while lockout is an antagonistic one. For loosely connected networks of (the more general) acyclic FSPs, the cooperative properties become NP-complete and the antagonistic ones PSPACE-complete. For tightly coupled networks of tree FSPs, we also have NP-completeness for the cooperative properties. For the harder case of FSPs with cycles, we provide a natural extension of the method.A preliminary version of this paper appeared as an extended abstract in theProceedings of the Fourth Annual ACM Symposium on Principles of Distributed Computing, August, 1985, pp. 23–38. P. C. Kanellakis was supported by ONR-DARPA Grant N00014-83-K-0146, NSF Grant DCR-8302391, and by the Office of Army Research under contract DAAG29-84-K-0058. S. A. Smolka was supported by National Science Foundation Grant DCR-8505873.     

Computational and experimental crash analysis of the road safety barrier

The paper describes the computational analysis and experimental crash tests of a new road safety barrier. The purpose of this research was to develop and evaluate a full-scale computational model of the road safety barrier for use in crash simulations and to further compare the computational results with real crash test data. The impact severity and stiffness of the new design have been evaluated with the dynamic nonlinear elasto-plastic analysis of the three-dimensional road safety barrier within the framework of the finite element method with LS-DYNA code. Comparison of computational and experimental results proved the correctness of the computational model. The tests have also shown that the new safety barrier assures controllable crash energy absorption which in turn increases the safety of vehicle occupants.     

Computation of logical effort in high level languages

A new measure of software complexity is introduced, that of logical effort. This measure is an attempt to quantify program complexity by an analysis of the control structure of the program, using the concepts of language virtuality and segment independence. A program is decomposed by the use of these concepts until measurements can be made at the statement level. These measurements, along with measurements of I, the effort necessary to perform a loop, and Q, the effort necessary to determine which branch to take in a decision, are then used to calculate recursively the effort in larger and larger structures, until the program level is reached. An example of this process is given for a short program, along with a brief comparison of the results obtained with a similar measure, that of cyclomatic complexity.

Algorithms for the computation of I and Q are also given, along with examples of their calculation. This process is essentially a decomposition of a Boolean function into disjunctive normal form, followed by a minimization of the form using a weighting measure involving weights on both the operators and the variables in the function.