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 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.

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)).

Minimal Triangulations of Manifolds

Finding vertex-minimal triangulations of closed manifolds is a very difficult problem. Except for spheres and two series of manifolds, vertex-minimal triangulations are known for only few manifolds of dimension more than 2 (see the table given at the end of Section 5). In this article, we present a brief survey on the works done in last 30 years on the following:(i) Finding the minimal number of vertices required to triangulate a given pl manifold. (ii) Given positive integers n and d, construction of n-vertex triangulations of different d-dimensional pl manifolds. (iii) Classifications of all the triangulations of a given pl manifold with same number of vertices.In Section 1, we have given all the definitions which are required for the remaining part of this article. A reader can start from Section 2 and come back to Section 1 as and when required. In Section 2, we have presented a very brief history of triangulations of manifolds. In Section 3,we have presented examples of several vertex-minimal triangulations. In Section 4, we have presented some interesting results on triangulations of manifolds. In particular, we have stated the Lower Bound Theorem and the Upper Bound Theorem. In Section 5, we have stated several results on minimal triangulations without proofs. Proofs are available in the references mentioned there. We have also presented some open problems/conjectures in Sections 3 and 5.

Minimal unsatisfiable sets: Classification and bounds

Proving the unsatisfiability of propositional Boolean formulas has applications in a wide range of fields. Minimal Unsatisfiable Sets (MUS) are signatures of the property of unsatisfiability in formulas and our understanding of these signatures can be very helpful in answering various algorithmic and structural questions relating to unsatisfiability. In this paper, we explore some combinatorial properties of MUS and use them to devise a classification scheme for MUS. We also derive bounds on the sizes of MUS in Horn, 2-SAT and 3-SAT formulas.

Minimal triangulation, complementarity and projective planes

Brehm and Kuhnel proved that if M-d is a combinatorial d-manifold with 3d/2 + 3 vertices and \ M-d \ is not homeomorphic to Sd then the combinatorial Morse number of M-d is three and hence d is an element of {0, 2, 4, 8, 16} and \ M-d \ is a manifold like a projective plane in the sense of Eells and Kuiper. We discuss the existence and uniqueness of such combinatorial manifolds. We also present the following result: ''Let M-n(d) be a combinatorial d-manifold with n vertices. M-n(d) satisfies complementarity if and only if d is an element of {0, 2, 4, 8, 16} with n = 3d/2 + 3 and \ M-n(d) \ is a manifold like a projective plane''.

Real-time monitoring of critical nodes with minimal number of Phasor Measurement Units

This paper presents a method for placement of Phasor Measurement Units, ensuring the monitoring of vulnerable buses which are obtained based on transient stability analysis of the overall system. Real-time monitoring of phase angles across different nodes, which indicates the proximity to instability, the very purpose will be well defined if the PMUs are placed at buses which are more vulnerable. The issue is to identify the key buses where the PMUs should be placed when the transient stability prediction is taken into account considering various disturbances. Integer Linear Programming technique with equality and inequality constraints is used to find out the optimal placement set with key buses identified from transient stability analysis. Results on IEEE-14 bus system are presented to illustrate the proposed approach.

Minimal residual method provides optimal regularization parameter for diffuse optical tomography

The inverse problem in the diffuse optical tomography is known to be nonlinear, ill-posed, and sometimes under-determined, requiring regularization to obtain meaningful results, with Tikhonov-type regularization being the most popular one. The choice of this regularization parameter dictates the reconstructed optical image quality and is typically chosen empirically or based on prior experience. An automated method for optimal selection of regularization parameter that is based on regularized minimal residual method (MRM) is proposed and is compared with the traditional generalized cross-validation method. The results obtained using numerical and gelatin phantom data indicate that the MRM-based method is capable of providing the optimal regularization parameter. (C) 2012 Society of Photo-Optical Instrumentation Engineers (SPIE). DOI: 10.1117/1.JBO.17.10.106015]