Optimal polygon placement by translation

Let M be an m-sided simple polygon and N be an n-sided polygon with holes. In this paper we consider the problem of computing the feasible region, i.e., the set of all placements by translation of M so that M lies inside N without intersecting any hole. First we propose an O (mn(2)) time algorithm for computing the feasible region for the case when M is a monotone polygon. Then we consider the general case when M is a simple polygon and propose an O(m(2)n(2)) time algorithm for computing the feasible region. Both algorithms are optimal upto a constant factor.

MAST: multi-script annotation toolkit for scenic text

This paper describes a semi-automatic tool for annotation of multi-script text from natural scene images. To our knowledge, this is the maiden tool that deals with multi-script text or arbitrary orientation. The procedure involves manual seed selection followed by a region growing process to segment each word present in the image. The threshold for region growing can be varied by the user so as to ensure pixel-accurate character segmentation. The text present in the image is tagged word-by-word. A virtual keyboard interface has also been designed for entering the ground truth in ten Indic scripts, besides English. The keyboard interface can easily be generated for any script, thereby expanding the scope of the toolkit. Optionally, each segmented word can further be labeled into its constituent characters/symbols. Polygonal masks are used to split or merge the segmented words into valid characters/symbols. The ground truth is represented by a pixel-level segmented image and a '.txt' file that contains information about the number of words in the image, word bounding boxes, script and ground truth Unicode. The toolkit, developed using MATLAB, can be used to generate ground truth and annotation for any generic document image. Thus, it is useful for researchers in the document image processing community for evaluating the performance of document analysis and recognition techniques. The multi-script annotation toolokit (MAST) is available for free download.

Spectral-spatial MODIS image analysis using swarm intelligence algorithms and region based segmentation for flood assessment

This paper discusses an approach for river mapping and flood evaluation based on multi-temporal time-series analysis of satellite images utilizing pixel spectral information for image clustering and region based segmentation for extracting water covered regions. MODIS satellite images are analyzed at two stages: before flood and during flood. Multi-temporal MODIS images are processed in two steps. In the first step, clustering algorithms such as Genetic Algorithm (GA) and Particle Swarm Optimization (PSO) are used to distinguish the water regions from the non-water based on spectral information. These algorithms are chosen since they are quite efficient in solving multi-modal optimization problems. These classified images are then segmented using spatial features of the water region to extract the river. From the results obtained, we evaluate the performance of the methods and conclude that incorporating region based image segmentation along with clustering algorithms provides accurate and reliable approach for the extraction of water covered region.

Genetic studies of the PRP17 gene of Saccharomyces cerevisiae: a domain essential for function maps to a nonconserved region of the protein

The PRP17 gene product is required for the second step of pre-mRNA splicing reactions. The C-terminal half of this protein bears four repeat units with homology to the beta transducin repeat. Missense mutations in three temperature-sensitive prp17 mutants map to a region in the N-terminal half of the protein. We have generated, in vitro, 11 missense alleles at the beta transducin repeat units and find that only one affects function in vivo. A phenotypically silent missense allele at the fourth repeat unit enhances the slow-growing phenotype conferred by an allele at the third repeat, suggesting an interaction between these domains. Although many missense mutations in highly conserved amino acids lack phenotypic effects, deletion analysis suggests an essential role for these units. Only mutations in the N-terminal nonconserved domain of PRP17 are synthetically lethal in combination with mutations in PRP16 and PRP18, two other gene products required for the second splicing reaction. A mutually allele-specific interaction between Prp17 and snr7, with mutations in U5 snRNA, was observed. We therefore suggest that the functional region of Prp17p that interacts with Prp18p, Prp16p, and U5 snRNA is the N terminal region of the protein.

Discrete parameter simulation optimization algorithms with applications to admission control with dependent service times

We propose certain discrete parameter variants of well known simulation optimization algorithms. Two of these algorithms are based on the smoothed functional (SF) technique while two others are based on the simultaneous perturbation stochastic approximation (SPSA) method. They differ from each other in the way perturbations are obtained and also the manner in which projections and parameter updates are performed. All our algorithms use two simulations and two-timescale stochastic approximation. As an application setting, we consider the important problem of admission control of packets in communication networks under dependent service times. We consider a discrete time slotted queueing model of the system and consider two different scenarios - one where the service times have a dependence on the system state and the other where they depend on the number of arrivals in a time slot. Under our settings, the simulated objective function appears ill-behaved with multiple local minima and a unique global minimum characterized by a sharp dip in the objective function in a small region of the parameter space. We compare the performance of our algorithms on these settings and observe that the two SF algorithms show the best results overall. In fact, in many cases studied, SF algorithms converge to the global minimum.

Helical FDK Algorithms With No Backprojection Weight

In this paper, we present two new filtered backprojection (FBP) type algorithms for cylindrical detector helical cone-beam geometry with no position dependent backprojection weight. The algorithms are extension of the recent exact Hilbert filtering based 2D divergent beam reconstruction with no backprojection weight to the FDK type algorithm for reconstruction in 3D helical trajectory cone-beam tomography. The two algorithms named HFDK-W1 and HFDK-W2 result in better image quality, noise uniformity, lower noise and reduced cone-beam artifacts.

A monoclonal antibody recognizing the C-terminal region of chicken egg white riboflavin carrier protein terminates early pregnancy in mice

In order to identify the functionally relevant epitopes on chicken riboflavin carrier protein, we have raised monoclonal antibodies to the vitamin carrier. One of these, 6B2C12, was found to interact specifically with a synthetic oligopeptide corresponding to the C-terminal 17 amino acid residues of the chicken egg white riboflavin carrier protein, which is missing in part in the egg yolk riboflavin carrier protein. This epitope is conserved through evolution in mammals including humans. Administration of the ascites fluid of 6B2C12 to pregnant mice intraperitoneally, resulted in the termination of pregnancy indicating that this epitope is involved in or closely associated with the transplacental transport of the vitamin from the maternal circulation to the growing fetus.

Status Survey of the Malabar Pied Hornbill in the Dandeli Region, Northern Western Ghats, India

The Malabar Pied Hornbill, Anthracoceros coronatus, is a near threatened species, endemic to the tropical deciduous forests of central and southern India and Sri Lanka. The Dandeli region in Karnataka (India) is believed to be the last stronghold of this species in the Western Ghats biodiversity hotspot. Being a rapidly developing area with a growing human population, the threats to this species and their habitat are mounting, especially due to a large number of hydroelectric projects and habitat fragmentation caused by paper and plywood industries. This study evaluated the change in population status of the Malabar Pied Hornbill over a 23 year period and defined priorities for the long term conservation and monitoring of hornbills in Dandeli. Encounter rates of hornbills were also analysed in relation to the density and species richness of trees and fruiting trees, basal area, canopy cover and distance from river. Hornbill encounters were not significantly different compared to the earlier study carried out by Reddy in 1988, but were significantly different across the five sites in the current study. Higher numbers of hornbills were encountered closer to the river, but these results were only marginally significant. The mean numbers of hornbills recorded at the two roost sites identified in Dandeli were 26 +/- 4.47 (n=16 counts) and 31.78 +/- 3.53 (n=14 counts) respectively. The study also helped build local awareness about the species, train local Forest Department staff in monitoring hornbills and develop a management plan for its conservation.

Space vector based bus clamped PWM algorithms for three level inverters: implementation, performance analysis and application considerations

This paper describes the different types of space vector based bus clamped PWM algorithms for three level inverters. A novel bus clamp PWM algorithm for low modulation indices region is also presented. The principles and switching sequences of all the types of bus clamped algorithms for high switching frequency are presented. Synchronized version of the PWM sequences for high power applications where switching frequency is low is also presented. The implementation details on DSP based digital controller and experimental results are presented. The THD of the output waveforms is studied for the entire operating region and is compared with the conventional space vector PWM technique. The bus clamped techniques can be used to reduce the switching losses or to improve the output voltage quality or both.. Different issues dominate depending on the type of application and power rating of the inverters. The results presented in this paper can be used for judicious use of the PWM techniques, which result in improved system efficiency and performance.

Theory and Algorithms for Hop-Count-Based Localization with Random Geometric Graph Models of Dense Sensor Networks

Wireless sensor networks can often be viewed in terms of a uniform deployment of a large number of nodes in a region of Euclidean space. Following deployment, the nodes self-organize into a mesh topology with a key aspect being self-localization. Having obtained a mesh topology in a dense, homogeneous deployment, a frequently used approximation is to take the hop distance between nodes to be proportional to the Euclidean distance between them. In this work, we analyze this approximation through two complementary analyses. We assume that the mesh topology is a random geometric graph on the nodes; and that some nodes are designated as anchors with known locations. First, we obtain high probability bounds on the Euclidean distances of all nodes that are h hops away from a fixed anchor node. In the second analysis, we provide a heuristic argument that leads to a direct approximation for the density function of the Euclidean distance between two nodes that are separated by a hop distance h. This approximation is shown, through simulation, to very closely match the true density function. Localization algorithms that draw upon the preceding analyses are then proposed and shown to perform better than some of the well-known algorithms present in the literature. Belief-propagation-based message-passing is then used to further enhance the performance of the proposed localization algorithms. To our knowledge, this is the first usage of message-passing for hop-count-based self-localization.

State estimation in power systems using linear model infinity norm-based trust region approach

State estimation is one of the most important functions in an energy control centre. An computationally efficient state estimator which is free from numerical instability/ill-conditioning is essential for security assessment of electric power grid. Whereas approaches to successfully overcome the numerical ill-conditioning issues have been proposed, an efficient algorithm for addressing the convergence issues in the presence of topological errors is yet to be evolved. Trust region (TR) methods have been successfully employed to overcome the divergence problem to certain extent. In this study, case studies are presented where the conventional algorithms including the existing TR methods would fail to converge. A linearised model-based TR method for successfully overcoming the convergence issues is proposed. On the computational front, unlike the existing TR methods for state estimation which employ quadratic models, the proposed linear model-based estimator is computationally efficient because the model minimiser can be computed in a single step. The model minimiser at each step is computed by minimising the linearised model in the presence of TR and measurement mismatch constraints. The infinity norm is used to define the geometry of the TR. Measurement mismatch constraints are employed to improve the accuracy. The proposed algorithm is compared with the quadratic model-based TR algorithm with case studies on the IEEE 30-bus system, 205-bus and 514-bus equivalent systems of part of Indian grid.

Real-World Extensions To Scheduling Algorithms Based On Lagrangian Relaxation

Recently, efficient scheduling algorithms based on Lagrangian relaxation have been proposed for scheduling parallel machine systems and job shops. In this article, we develop real-world extensions to these scheduling methods. In the first part of the paper, we consider the problem of scheduling single operation jobs on parallel identical machines and extend the methodology to handle multiple classes of jobs, taking into account setup times and setup costs, The proposed methodology uses Lagrangian relaxation and simulated annealing in a hybrid framework, In the second part of the paper, we consider a Lagrangian relaxation based method for scheduling job shops and extend it to obtain a scheduling methodology for a real-world flexible manufacturing system with centralized material handling.

Unsteady free convection flow in the stagnation-point region of a rotating sphere

The unsteady free convection boundary-layer flow in the forward stagnation-point region of a sphere, which is rotating with time-dependent angular velocity in an ambient fluid, has been studied. Both constant wall temperature and constant hear flux conditions have been considered. The non-linear coupled parabolic partial differential equations governing the flow have been solved numerically using an implicit finite-difference scheme. The skin friction and the heat transfer are enhanced by the buoyancy force. The effect of the buoyancy force is found to be more pronounced for smaller Prandtl numbers than for larger Prandtl numbers. For a given buoyancy force, the heat transfer increases with an increase in Prandtl number, but the skin friction decreases.

Unsteady free convection flow in the stagnation-point region of a three-dimensional body

The unsteady free convection flow in the stagnation-point region of a heated three-dimensional body placed in an ambient fluid is studied under boundary layer approximations. We have considered the case where there is an initial steady state that is perturbed by a step-change in the wall temperature. The non-linear coupled partial differential equations governing the free convection flow are solved numerically using a finite difference scheme. The presented results show the temporal development of the momentum and thermal boundary layer characteristics.

Free Energy Gap Dependence of the Electron-Transfer Rate from the Inverted to the Normal Region

numerical study of the free energy gap (FEG) dependence of the electron-transfer rate in polar solvents is presented. This study is based on the generalized multidimensional hybrid model, which not only includes the solvent polarization and the molecular vibration modes, but also the biphasic polar response of the solvent. The free energy gap dependence is found to be sensitive to several factors, including the solvent relaxation rate, the electronic coupling between the surfaces, the frequency of the high-frequency quantum vibrational mode, and the magnitude of the solvent reorganization energy. It is shown that in some cases solvent relaxation can play an important role even in the Marcus normal regime. The minimal hybrid model involves a large number of parameters, giving rise to a diverse non-Marcus FEG behavior which is often determined collectively by these parameters. The model gives the linear free energy gap dependence of the logarithmic rate over a substantial range of FEG, spanning from the normal to the inverted regime. However, even for favorable values of the relevant parameters, a linear free energy gap dependence of the rate could be obtained only over a range of 5000-6000 cm(-1) (compared to the experimentally observed range of 10000 cm(-1) reported by Benniston et al.). The present work suggests several extensions/generalizations of the hybrid model which might be necessary to fully understand the observed free energy gap dependence.