An approximate algorithm for the minimal vertex nested polygon problem

Given two simple polygons, the Minimal Vertex Nested Polygon Problem is one of finding a polygon nested between the given polygons having the minimum number of vertices. In this paper, we suggest efficient approximate algorithms for interesting special cases of the above using the shortest-path finding graph algorithms.

Design of crosspoint-irredundant PLAs using minimal number of control inputs

The problem of determining a minimal number of control inputs for converting a programmable logic array (PLA) with undetectable faults to crosspoint-irredundant PLA for testing has been formulated as a nonstandard set covering problem. By representing subsets of sets as cubes, this problem has been reformulated as familiar problems. It is noted that this result has significance because a crosspoint-irredundant PLA can be converted to a completely testable PLA in a straightforward fashion, thus achieving very good fault coverage and easy testability.

A Triggering Mechanism for Enhanced Star-Formation in Colliding Galaxies

We propose a physical mechanism to explain the origin of the intense burst of massive-star formation seen in colliding/merging, gas-rich, field spiral galaxies. We explicitly take account of the different parameters for the two main mass components, H-2 and H I, of the interstellar medium within a galaxy and follow their consequent different evolution during a collision between two galaxies. We also note that, in a typical spiral galaxy-like our galaxy, the Giant Molecular Clouds (GMCs) are in a near-virial equilibrium and form the current sites of massive-star formation, but have a low star formation rate. We show that this star formation rate is increased following a collision between galaxies. During a typical collision between two field spiral galaxies, the H I clouds from the two galaxies undergo collisions at a relative velocity of approximately 300 km s-1. However, the GMCs, with their smaller volume filling factor, do not collide. The collisions among the H I clouds from the two galaxies lead to the formation of a hot, ionized, high-pressure remnant gas. The over-pressure due to this hot gas causes a radiative shock compression of the outer layers of a preexisting GMC in the overlapping wedge region. This makes these layers gravitationally unstable, thus triggering a burst of massive-star formation in the initially barely stable GMCs.The resulting value of the typical IR luminosity from the young, massive stars from a pair of colliding galaxies is estimated to be approximately 2 x 10(11) L., in agreement with the observed values. In our model, the massive-star formation occurs in situ in the overlapping regions of a pair of colliding galaxies. We can thus explain the origin of enhanced star formation over an extended, central area approximately several kiloparsecs in size, as seen in typical colliding galaxies, and also the origin of starbursts in extranuclear regions of disk overlap as seen in Arp 299 (NGC 3690/IC 694) and in Arp 244 (NGC 4038/39). Whether the IR emission from the central region or that from the surrounding extranuclear galactic disk dominates depends on the geometry and the epoch of the collision and on the initial radial gas distribution in the two galaxies. In general, the central starburst would be stronger than that in the disks, due to the higher preexisting gas densities in the central region. The burst of star formation is expected to last over a galactic gas disk crossing time approximately 4 x 10(7) yr. We can also explain the simultaneous existence of nearly normal CO galaxy luminosities and shocked H-2 gas, as seen in colliding field galaxies.This is a minimal model, in that the only necessary condition for it to work is that there should be a sufficient overlap between the spatial gas distributions of the colliding galaxy pair.

A divisive scheme for constructing minimal spanning trees in coordinate space

An algorithm to generate a minimal spanning tree is presented when the nodes with their coordinates in some m-dimensional Euclidean space and the corresponding metric are given. This algorithm is tested on manually generated data sets. The worst case time complexity of this algorithm is O(n log2n) for a collection of n data samples.

Minimal three-component SU(2) gadget for polarization optics

Two identities involving quarter-wave plates and half-wave plates are established. These are used to improve on an earlier gadget involving four wave plates leading to a new gadget involving just three plates, a half-wave plate and two quarter-wave plates, which can realize all SU(2) polarization transformations. This gadget is shown to involve the minimum number of quarter-wave and half-wave plates. The analysis leads to a decomposition theorem for SU (2) matrices in terms of factors which are symmetric fourth and eighth roots of the identity.

Exact analysis of Burgers equation on semiline with flux condition at the origin

The initial boundary value problem for the Burgers equation in the domain x greater-or-equal, slanted 0, t > 0 with flux boundary condition at x = 0 has been solved exactly. The behaviour of the solution as t tends to infinity is studied and the “asymptotic profile at infinity” is obtained. In addition, the uniqueness of the solution of the initial boundary value problem is proved and its inviscid limit as var epsilon → 0 is obtained.

Minimal sets of generators for the relation ideals of certain monomial curves

Let O be a monomial curve in the affine algebraic e-space over a field K and P be the relation ideal of O. If O is defined by a sequence of e positive integers some e - 1 of which form an arithmetic sequence then we construct a minimal set of generators for P and write an explicit formula for mu(P).

On Walkup's class K (d) and a minimal triangulation of (S-3 (sic) S-1)(#3)

For d >= 2, Walkup's class K (d) consists of the d-dimensional simplicial complexes all whose vertex-links are stacked (d - 1)-spheres. Kalai showed that for d >= 4, all connected members of K (d) are obtained from stacked d-spheres by finitely many elementary handle additions. According to a result of Walkup, the face vector of any triangulated 4-manifold X with Euler characteristic chi satisfies f(1) >= 5f(0) - 15/2 chi, with equality only for X is an element of K(4). Kuhnel observed that this implies f(0)(f(0) - 11) >= -15 chi, with equality only for 2-neighborly members of K(4). Kuhnel also asked if there is a triangulated 4-manifold with f(0) = 15, chi = -4 (attaining equality in his lower bound). In this paper, guided by Kalai's theorem, we show that indeed there is such a triangulation. It triangulates the connected sum of three copies of the twisted sphere product S-3 (sic) S-1. Because of Kuhnel's inequality, the given triangulation of this manifold is a vertex-minimal triangulation. By a recent result of Effenberger, the triangulation constructed here is tight. Apart from the neighborly 2-manifolds and the infinite family of (2d + 3)-vertex sphere products Sd-1 X S-1 (twisted for d odd), only fourteen tight triangulated manifolds were known so far. The present construction yields a new member of this sporadic family. We also present a self-contained proof of Kalai's result. (C) 2011 Elsevier B.V. All rights reserved.

Low-power pipelined LMS adaptive filter architectures with minimal adaptation delay

The use of delayed coefficient adaptation in the least mean square (LMS) algorithm has enabled the design of pipelined architectures for real-time transversal adaptive filtering. However, the convergence speed of this delayed LMS (DLMS) algorithm, when compared with that of the standard LMS algorithm, is degraded and worsens with increase in the adaptation delay. Existing pipelined DLMS architectures have large adaptation delay and hence degraded convergence speed. We in this paper, first present a pipelined DLMS architecture with minimal adaptation delay for any given sampling rate. The architecture is synthesized by using a number of function preserving transformations on the signal flow graph representation of the DLMS algorithm. With the use of carry-save arithmetic, the pipelined architecture can support high sampling rates, limited only by the delay of a full adder and a 2-to-1 multiplexer. In the second part of this paper, we extend the synthesis methodology described in the first part, to synthesize pipelined DLMS architectures whose power dissipation meets a specified budget. This low-power architecture exploits the parallelism in the DLMS algorithm to meet the required computational throughput. The architecture exhibits a novel tradeoff between algorithmic performance (convergence speed) and power dissipation. (C) 1999 Elsevier Science B.V. All rights resented.

Minimal set of generators for the derivation module of certain monomial curves

Let K be a field of characteristic zero and let m(0),..., m(e-1) be a sequence of positive integers. Let C be an algebroid monomial curve in the affine e-space A(K)(e) defined parametrically by X-0 = T-m0,..., Xe-1 = Tme-1 and let A be the coordinate ring of C. In this paper, we assume that some e - 1 terms of m(0),..., m(e-1) form an arithmetic sequence and construct a minimal set of generators for the derivation module Der(K)(A) of A and write an explicit formula for mu (Der(K)(A)).

Cross-polarization from the dipolar reservoir under the mismatched Hartmann-Hahn condition

Cross-polarization from the dipolar reservoir for a range of mismatched Hartmann-Hahn conditions has been considered. Experiment, in general, agrees with the dispersive Lorentzian behavior expected on the basis of quasi-equilibrium theory. It is observed that inclusion of additional mechanisms of polarization transfer lead to an improvment of the fit of the experimental results. The utility of extending the technique to the case of ordered long chain molecules, such as liquid crystals, for the measurement of the local dipolar field is also presented. (C) 2002 Elsevier Science (USA).