Expansion-based algorithms for finding single pair shortest path on surface

Finding single pair shortest paths on surface is a fundamental problem in various domains, like Geographic Information Systems (GIS) 3D applications, robotic path planning system, and surface nearest neighbor query in spatial database, etc. Currently, to solve the problem, existing algorithms must traverse the entire polyhedral surface. With the rapid advance in areas like Global Positioning System (CPS), Computer Aided Design (CAD) systems and laser range scanner, surface models axe becoming more and more complex. It is not uncommon that a surface model contains millions of polygons. The single pair shortest path problem is getting harder and harder to solve. Based on the observation that the single pair shortest path is in the locality, we propose in this paper efficient methods by excluding part of the surface model without considering them in the search process. Three novel expansion-based algorithms are proposed, namely, Naive algorithm, Rectangle-based Algorithm and Ellipse-based Algorithm. Each algorithm uses a two-step approach to find the shortest path. (1) compute an initial local path. (2) use the value of this initial path to select a search region, in which the global shortest path exists. The search process terminates once the global optimum criteria are satisfied. By reducing the searching region, the performance is improved dramatically in most cases.

Quantifying potential nitrogen removal by denitrification in stream sediments at a regional scale

Potential denitrification rates were measured using the acetylene block method, in sediments collected from streams in the sub-tropical, south-east Queensland region of Australia. Our aim was to estimate how much nitrogen could be removed from lotic systems by denitrification at the regional scale. Denitrification measured at 65 sites in August and September from a catchment of 22700 km(2) was extrapolated to all streams and rivers in the region based on the sediment area available for denitrification. Denitrification rates ranged between 4 and 950 mumol N m(-2) h(-1), with most sites having rates below 150 mumol N m(-2) h(-1). Based on these results, the current study estimates that a total of 305 t of nitrogen could be denitrified per year from all streams and rivers in the region, representing 6% of the total annual nitrogen load from surrounding land use. During baseflow conditions, when nitrogen loads to streams are low, the proportion of nitrogen removed through denitrification would be substantially higher, in some cases removing 100% of the nitrogen load. It is proposed that denitrification is an important process maintaining low concentrations of dissolved inorganic nitrogen under baseflow conditions and is therefore likely to enhance nitrogen limitation of primary production in this region.

A simulation model of cereal-legume intercropping systems for semi-arid regions II. Model application

Smallholder farmers in Africa practice traditional cropping techniques such as intercropping. Intercropping is thought to offer higher productivity and resource milisation than sole cropping. In this study, risk associated with maize-bean intercropping was evaluated by quantifying long-term yield in both intercropping and sole cropping in a semi-arid region of South Africa (Bloemfontein, Free State) with reference to rainfall variability. The crop simulation model was run with different cultural practices (planting date and plant density) for 52 summer crop growing seasons (1950/1951-2001/2002). Eighty-one scenarios, consisted of three levels of initial soil water, planting date, maize population, and bean population, were simulated. From the simulation outputs, the total land equivalent ratio (LER) was greater than one. The intercrop (equivalent to sole maize) had greater energy value (EV) than sole beans, and the intercrop (equivalent to sole beans) had greater monetary value (MV) than sole maize. From these results, it can be concluded that maize-bean intercropping is advantageous for this semi-arid region. Soil water at planting was the most important factor of all scenario factors, followed by planting date. Irrigation application at planting, November/December planting and high plant density of maize for EV and beans for MV can be one of the most effective cultural practices in the study region. With regard to rainfall variability, seasonal (October-April) rainfall positively affected EV and MV, but not LER. There was more intercrop production in La Nina years than in El Nino years. Thus, better cultural practices may be selected to maximize maize-bean intercrop yields for specific seasons in the semi-arid region based on the global seasonal outlook. (c) 2004 Elsevier B.V. All rights reserved.

Enhanced detection-guided NLMS estimation of sparse FIR-modeled signal channels

In various signal-channel-estimation problems, the channel being estimated may be well approximated by a discrete finite impulse response (FIR) model with sparsely separated active or nonzero taps. A common approach to estimating such channels involves a discrete normalized least-mean-square (NLMS) adaptive FIR filter, every tap of which is adapted at each sample interval. Such an approach suffers from slow convergence rates and poor tracking when the required FIR filter is "long." Recently, NLMS-based algorithms have been proposed that employ least-squares-based structural detection techniques to exploit possible sparse channel structure and subsequently provide improved estimation performance. However, these algorithms perform poorly when there is a large dynamic range amongst the active taps. In this paper, we propose two modifications to the previous algorithms, which essentially remove this limitation. The modifications also significantly improve the applicability of the detection technique to structurally time varying channels. Importantly, for sparse channels, the computational cost of the newly proposed detection-guided NLMS estimator is only marginally greater than that of the standard NLMS estimator. Simulations demonstrate the favourable performance of the newly proposed algorithm. © 2006 IEEE.

Estimation of concentration-dependent diffusion coefficient in drying process from the space-averaged concentration versus time with experimental data

The estimation of a concentration-dependent diffusion coefficient in a drying process is known as an inverse coefficient problem. The solution is sought wherein the space-average concentration is known as function of time (mass loss monitoring). The problem is stated as the minimization of a functional and gradient-based algorithms are used to solve it. Many numerical and experimental examples that demonstrate the effectiveness of the proposed approach are presented. Thin slab drying was carried out in an isothermal drying chamber built in our laboratory. The diffusion coefficients of fructose obtained with the present method are compared with existing literature results.

Extraction of texture features from arbitrary-shaped regions for image retrieval

Lots of work has been done in texture feature extraction for rectangular images, but not as much attention has been paid to the arbitrary-shaped regions available in region-based image retrieval (RBIR) systems. In This work, we present a texture feature extraction algorithm, based on projection onto convex sets (POCS) theory. POCS iteratively concentrates more and more energy into the selected coefficients from which texture features of an arbitrary-shaped region can be extracted. Experimental results demonstrate the effectiveness of the proposed algorithm for image retrieval purposes.

3D protein structure matching by patch signatures

For determining functionality dependencies between two proteins, both represented as 3D structures, it is an essential condition that they have one or more matching structural regions called patches. As 3D structures for proteins are large, complex and constantly evolving, it is computationally expensive and very time-consuming to identify possible locations and sizes of patches for a given protein against a large protein database. In this paper, we address a vector space based representation for protein structures, where a patch is formed by the vectors within the region. Based on our previews work, a compact representation of the patch named patch signature is applied here. A similarity measure of two patches is then derived based on their signatures. To achieve fast patch matching in large protein databases, a match-and-expand strategy is proposed. Given a query patch, a set of small k-sized matching patches, called candidate patches, is generated in match stage. The candidate patches are further filtered by enlarging k in expand stage. Our extensive experimental results demonstrate encouraging performances with respect to this biologically critical but previously computationally prohibitive problem.

Specific PCR based detection of Phytophthora medicaginis using the intergenic spacer region of the ribosomal DNA

A technique based on the polymerase chain reaction (PCR) for the specific detection of Phytophthora medicaginis was developed using nucleotide sequence information of the ribosomal DNA (rDNA) regions. The complete IGS 2 region between the 5 S gene of one rDNA repeat and the small subunit of the adjacent repeat was sequenced for P. medicaginis and related species. The entire nucleotide sequence length of the IGS 2 of P. medicaginis was 3566 bp. A pair of oligonucleotide primers (PPED04 and PPED05), which allowed amplification of a specific fragment (364 bp) within the IGS 2 of P. medicaginis using the PCR, was designed. Specific amplification of this fragment from P. medicaginis was highly sensitive, detecting template DNA as low as 4 ng and in a host-pathogen DNA ratio of 1000000:1. Specific PCR amplification using PPED04 and PPED05 was successful in detecting P. medicaginis in lucerne stems infected under glasshouse conditions and field infected lucerne roots. The procedures developed in this work have application to improved identification and detection of a wide range of Phytophthora spp. in plants and soil.

Concurreny based transition refinement for the verification of distributed algorithms

We suggest a new notion of behaviour preserving transition refinement based on partial order semantics. This notion is called transition refinement. We introduced transition refinement for elementary (low-level) Petri Nets earlier. For modelling and verifying complex distributed algorithms, high-level (Algebraic) Petri nets are usually used. In this paper, we define transition refinement for Algebraic Petri Nets. This notion is more powerful than transition refinement for elementary Petri nets because it corresponds to the simultaneous refinement of several transitions in an elementary Petri net. Transition refinement is particularly suitable for refinement steps that increase the degree of distribution of an algorithm, e.g. when synchronous communication is replaced by asynchronous message passing. We study how to prove that a replacement of a transition is a transition refinement.

A phylogeny for the genus Isoodon and a range extension for I-obesulus peninsulae based on mtDNA control region and morphology

Short-nosed bandicoots, Isoodon, have undergone marked range contractions since European colonisation of Australia and are currently divided into many subspecies, the validity of which is debated. Discriminant function analysis of morphology and a phylogeny of Isoodon based on mtDNA control region sequences indicate a clear split between two of the three recognised species, I. macrourus and I. obesulus/auratus. However, while all previously recognised taxa within the I. obesulus/auratus group are morphologically distinct, I. auratus and I. obesulus are not phylogenetically distinct for mtDNA. The genetic divergence between I. obesulus and I. auratus (2.6%) is similar to that found among geographic isolates of the former (I. o. obesulus and I. o. peninsulae: 2.7%). Further, the divergence between geographically close populations of two different species (I. o. obesulus from Western Australia and I. a. barrowensis: 1.2%) is smaller than that among subspecies within I. auratus (I. a. barrowensis and I. auratus from northern Western Australia: 1.7%). A newly discovered population of Isoodon in the Lamb Range, far north Queensland, sympatric with a population of I. m. torosus, is shown to represent a range extension of I. o. peninsulae (350 km). It seems plausible that what is currently considered as two species, I. obesulus and I. auratus, was once one continuous species now represented by isolated populations that have diverged morphologically as a consequence of adaptation to the diverse environments that occur throughout their range. The taxonomy of these populations is discussed in relation to their morphological distinctiveness and genetic similarity.

Knowledge-based system on optimum design of liquid retaining structures with genetic algorithms

This paper delineates the development of a prototype hybrid knowledge-based system for the optimum design of liquid retaining structures by coupling the blackboard architecture, an expert system shell VISUAL RULE STUDIO and genetic algorithm (GA). Through custom-built interactive graphical user interfaces under a user-friendly environment, the user is directed throughout the design process, which includes preliminary design, load specification, model generation, finite element analysis, code compliance checking, and member sizing optimization. For structural optimization, GA is applied to the minimum cost design of structural systems with discrete reinforced concrete sections. The design of a typical example of the liquid retaining structure is illustrated. The results demonstrate extraordinarily converging speed as near-optimal solutions are acquired after merely exploration of a small portion of the search space. This system can act as a consultant to assist novice designers in the design of liquid retaining structures.

Automatic texture segmentation for texture-based image retrieval

Texture-segmentation is the crucial initial step for texture-based image retrieval. Texture is the main difficulty faced to a segmentation method. Many image segmentation algorithms either can’t handle texture properly or can’t obtain texture features directly during segmentation which can be used for retrieval purpose. This paper describes an automatic texture segmentation algorithm based on a set of features derived from wavelet domain, which are effective in texture description for retrieval purpose. Simulation results show that the proposed algorithm can efficiently capture the textured regions in arbitrary images, with the features of each region extracted as well. The features of each textured region can be directly used to index image database with applications as texture-based image retrieval.

A hybrid probabilistic criterion for market-based transmission expansion planning

Market-based transmission expansion planning gives information to investors on where is the most cost efficient place to invest and brings benefits to those who invest in this grid. However, both market issue and power system adequacy problems are system planers’ concern. In this paper, a hybrid probabilistic criterion of Expected Economical Loss (EEL) is proposed as an index to evaluate the systems’ overall expected economical losses during system operation in a competitive market. It stands on both investors’ and planner’s point of view and will further improves the traditional reliability cost. By applying EEL, it is possible for system planners to obtain a clear idea regarding the transmission network’s bottleneck and the amount of losses arises from this weak point. Sequentially, it enables planners to assess the worth of providing reliable services. Also, the EEL will contain valuable information for moneymen to undertake their investment. This index could truly reflect the random behaviors of power systems and uncertainties from electricity market. The performance of the EEL index is enhanced by applying Normalized Coefficient of Probability (NCP), so it can be utilized in large real power systems. A numerical example is carried out on IEEE Reliability Test System (RTS), which will show how the EEL can predict the current system bottleneck under future operational conditions and how to use EEL as one of planning objectives to determine future optimal plans. A well-known simulation method, Monte Carlo simulation, is employed to achieve the probabilistic characteristic of electricity market and Genetic Algorithms (GAs) is used as a multi-objective optimization tool.

Comparison of BR and QR Eigenvalue Algorithms for Power System Small Signal Stability Analysis

The BR algorithm is a novel and efficient method to find all eigenvalues of upper Hessenberg matrices and has never been applied to eigenanalysis for power system small signal stability. This paper analyzes differences between the BR and the QR algorithms with performance comparison in terms of CPU time based on stopping criteria and storage requirement. The BR algorithm utilizes accelerating strategies to improve its performance when computing eigenvalues of narrowly banded, nearly tridiagonal upper Hessenberg matrices. These strategies significantly reduce the computation time at a reasonable level of precision. Compared with the QR algorithm, the BR algorithm requires fewer iteration steps and less storage space without depriving of appropriate precision in solving eigenvalue problems of large-scale power systems. Numerical examples demonstrate the efficiency of the BR algorithm in pursuing eigenanalysis tasks of 39-, 68-, 115-, 300-, and 600-bus systems. Experiment results suggest that the BR algorithm is a more efficient algorithm for large-scale power system small signal stability eigenanalysis.