An efficient algorithm for partitioning parameterized polygons into rectangles

In this paper, we propose an algorithm for partitioning parameterized orthogonal polygons into rectangles. The algorithm is based on the plane-sweep technique and can be used for partitioning polygons which contain holes. The input to the algorithm consists of the contour of a parameterized polygon to be partitioned and the constraints for those parameters which reside in the contour. The algorithm uses horizontal cuts only and generates a minimum number of rectangles whose union is the original orthogonal polygon. The proposed algorithm can be used as the basis to build corner stitching data structure for parameterized VLSI layouts and has been implemented in Java programming language. Copyright © 2010 ACM, Inc.

Disaggregation of polygons of surficial geology and soil maps using spatial modelling and legacy data

Examples from the Murray-Darling basin in Australia are used to illustrate different methods of disaggregation of reconnaissance-scale maps. One approach for disaggregation revolves around the de-convolution of the soil-landscape paradigm elaborated during a soil survey. The descriptions of soil ma units and block diagrams in a soil survey report detail soil-landscape relationships or soil toposequences that can be used to disaggregate map units into component landscape elements. Toposequences can be visualised on a computer by combining soil maps with digital elevation data. Expert knowledge or statistics can be used to implement the disaggregation. Use of a restructuring element and k-means clustering are illustrated. Another approach to disaggregation uses training areas to develop rules to extrapolate detailed mapping into other, larger areas where detailed mapping is unavailable. A two-level decision tree example is presented. At one level, the decision tree method is used to capture mapping rules from the training area; at another level, it is used to define the domain over which those rules can be extrapolated. (C) 2001 Elsevier Science B.V. All rights reserved.

A state-contingent production approach to principal-agent problems with an application to point-source pollution control

Two basic representations of principal-agent relationships, the 'state-space' and 'parameterized distribution' formulations, have emerged. Although the state-space formulation appears more natural, analytical studies using this formulation have had limited success. This paper develops a state-space formulation of the moral-hazard problem using a general representation of production under uncertainty. A closed-form solution for the agency-cost problem is derived. Comparative-static results are deduced. Next we solve the principal's problem of selecting the optimal output given the agency-cost function. The analysis is applied to the problem of point-source pollution control. (C) 1998 Published by Elsevier Science S.A. All rights reserved.

HIV heterogeneity and proximity of homestead to roads in rural South Africa: an exploration using a geographical information system

OBJECTIVE To describe heterogeneity of HIV prevalence among pregnant women in Hlabisa health district, South Africa and to correlate this with proximity of homestead to roads. METHODS HIV prevalence measured through anonymous surveillance among pregnant women and stratified by local village clinic. Polygons were created around each clinic, assuming women attend the clinic nearest their home. A geographical information system (GIS) calculated the mean distance from homesteads in each clinic catchment to nearest primary (1 degrees) and to nearest primary or secondary (2 degrees) road. RESULTS We found marked HIV heterogeneity by clinic catchment (range 19-31% (P < 0.001). A polygon plot demonstrated lower HIV prevalence in catchments remote from 1 degrees roads. Mean distance from homesteads to nearest 1 degrees or 2 degrees road varied by clinic catchment from 1623 to 7569 m. The mean distance from homesteads to a 1 degrees or 2 degrees road for each clinic catchment was strongly correlated with HIV prevalence (r = 0.66; P = 0.002). CONCLUSIONS The substantial HIV heterogeneity in this district is closely correlated with proximity to a 1 degrees or 2 degrees road. GIS is a powerful tool to demonstrate and to start to analyse this observation. Further research is needed to better understand this relationship both at ecological and individual levels, and to develop interventions to reduce the spread of HIV infection.

Modified logit life table system: Principles, empirical validation, and application

Despite its widespread use, the Coale-Demeny model life table system does not capture the extensive variation in age-specific mortality patterns observed in contemporary populations, particularly those of the countries of Eastern Europe and populations affected by HIV/AIDS. Although relational mortality models, such as the Brass logit system, can identify these variations, these models show systematic bias in their predictive ability as mortality levels depart from the standard. We propose a modification of the two-parameter Brass relational model. The modified model incorporates two additional age-specific correction factors (gamma(x), and theta(x)) based on mortality levels among children and adults, relative to the standard. Tests of predictive validity show deviations in age-specific mortality rates predicted by the proposed system to be 30-50 per cent lower than those predicted by the Coale-Demeny system and 15-40 per cent lower than those predicted using the original Brass system. The modified logit system is a two-parameter system, parameterized using values of l(5) and l(60).

Do harvest refuges buffer kangaroos against evolutionary responses to selective harvesting?

There is a wealth of literature documenting a directional change of body size in heavily harvested populations. Most of this work concentrates on aquatic systems, but terrestrial populations are equally at risk. This paper explores the capacity of harvest refuges to counteract potential effects of size-selective harvesting on the allele frequency,of populations. We constructed a stochastic, individual-based model parameterized with data on red kangaroos. Because we do not know which part of individual growth would change in the course of natural selection, we explored the effects of two alternative models of individual growth in which alleles affect either the growth rate or the maximum size. The model results show that size-selective harvesting can result in significantly smaller kangaroos for a given age when the entire population is subject to harvesting. In contrast, in scenarios that include dispersal from harvest refuges, the initial allele frequency remains virtually unchanged.

An investigation into effects of long-distance seed dispersal on organelle population genetic structure and colonization rate: a model analysis

A simulation-based modelling approach is used to examine the effects of stratified seed dispersal (representing the distribution of the majority of dispersal around the maternal parent and also rare long-distance dispersal) on the genetic structure of maternally inherited genomes and the colonization rate of expanding plant populations. The model is parameterized to approximate postglacial oak colonization in the UK, but is relevant to plant populations that exhibit stratified seed dispersal. The modelling approach considers the colonization of individual plants over a large area (three 500 km x 10 km rolled transects are used to approximate a 500 km x 300 km area). Our approach shows how the interaction of plant population dynamics with stratified dispersal can result in a spatially patchy haplotype structure. We show that while both colonization speeds and the resulting genetic structure are influenced by the characteristics of the dispersal kernel, they are robust to changes in the periodicity of long-distance events, provided the average number of long-distance dispersal events remains constant. We also consider the effects of additional physical and environmental mechanisms on plant colonization. Results show significant changes in genetic structure when the initial colonization of different haplotypes is staggered over time and when a barrier to colonization is introduced. Environmental influences on survivorship and fecundity affect both the genetic structure and the speed of colonization. The importance of these mechanisms in relation to the postglacial spread and genetic structure of oak in the UK is discussed.

Slowing down a pine invasion despite uncertainty in demography and dispersal

1. Management decisions regarding invasive plants often have to be made quickly and in the face of fragmentary knowledge of their population dynamics. However, recommendations are commonly made on the basis of only a restricted set of parameters. Without addressing uncertainty and variability in model parameters we risk ineffective management, resulting in wasted resources and an escalating problem if early chances to control spread are missed. 2. Using available data for Pinus nigra in ungrazed and grazed grassland and shrubland in New Zealand, we parameterized a stage-structured spread model to calculate invasion wave speed, population growth rate and their sensitivities and elasticities to population parameters. Uncertainty distributions of parameters were used with the model to generate confidence intervals (CI) about the model predictions. 3. Ungrazed grassland environments were most vulnerable to invasion and the highest elasticities and sensitivities of invasion speed were to long-distance dispersal parameters. However, there was overlap between the elasticity and sensitivity CI on juvenile survival, seedling establishment and long-distance dispersal parameters, indicating overlap in their effects on invasion speed. 4. While elasticity of invasion speed to long-distance dispersal was highest in shrubland environments, there was overlap with the CI of elasticity to juvenile survival. In shrubland invasion speed was most sensitive to the probability of establishment, especially when establishment was low. In the grazed environment elasticity and sensitivity of invasion speed to the severity of grazing were consistently highest. Management recommendations based on elasticities and sensitivities depend on the vulnerability of the habitat. 5. Synthesis and applications. Despite considerable uncertainty in demography and dispersal, robust management recommendations emerged from the model. Proportional or absolute reductions in long-distance dispersal, juvenile survival and seedling establishment parameters have the potential to reduce wave speed substantially. Plantations of wind-dispersed invasive conifers should not be sited on exposed sites vulnerable to long-distance dispersal events, and trees in these sites should be removed. Invasion speed can also be reduced by removing seedlings, establishing competitive shrubs and grazing. Incorporating uncertainty into the modelling process increases our confidence in the wide applicability of the management strategies recommended here.

Identification of MIMO Hammerstein systems using cardinal spline functions

A new approach to identify multivariable Hammerstein systems is proposed in this paper. By using cardinal cubic spline functions to model the static nonlinearities, the proposed method is effective in modelling processes with hard and/or coupled nonlinearities. With an appropriate transformation, the nonlinear models are parameterized such that the nonlinear identification problem is converted into a linear one. The persistently exciting condition for the transformed input is derived to ensure the estimates are consistent with the true system. A simulation study is performed to demonstrate the effectiveness of the proposed method compared with the existing approaches based on polynomials. (C) 2006 Elsevier Ltd. All rights reserved.

A general-purpose tunable landscape generator

The research literature on metalieuristic and evolutionary computation has proposed a large number of algorithms for the solution of challenging real-world optimization problems. It is often not possible to study theoretically the performance of these algorithms unless significant assumptions are made on either the algorithm itself or the problems to which it is applied, or both. As a consequence, metalieuristics are typically evaluated empirically using a set of test problems. Unfortunately, relatively little attention has been given to the development of methodologies and tools for the large-scale empirical evaluation and/or comparison of metaheuristics. In this paper, we propose a landscape (test-problem) generator that can be used to generate optimization problem instances for continuous, bound-constrained optimization problems. The landscape generator is parameterized by a small number of parameters, and the values of these parameters have a direct and intuitive interpretation in terms of the geometric features of the landscapes that they produce. An experimental space is defined over algorithms and problems, via a tuple of parameters for any specified algorithm and problem class (here determined by the landscape generator). An experiment is then clearly specified as a point in this space, in a way that is analogous to other areas of experimental algorithmics, and more generally in experimental design. Experimental results are presented, demonstrating the use of the landscape generator. In particular, we analyze some simple, continuous estimation of distribution algorithms, and gain new insights into the behavior of these algorithms using the landscape generator.

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.

3D statistical shape models to embed spatial relationship information

This paper presents the creation of 3D statistical shape models of the knee bones and their use to embed information into a segmentation system for MRIs of the knee. We propose utilising the strong spatial relationship between the cartilages and the bones in the knee by embedding this information into the created models. This information can then be used to automate the initialisation of segmentation algorithms for the cartilages. The approach used to automatically generate the 3D statistical shape models of the bones is based on the point distribution model optimisation framework of Davies. Our implementation of this scheme uses a parameterized surface extraction algorithm, which is used as the basis for the optimisation scheme that automatically creates the 3D statistical shape models. The current approach is illustrated by generating 3D statistical shape models of the patella, tibia and femoral bones from a segmented database of the knee. The use of these models to embed spatial relationship information to aid in the automation of segmentation algorithms for the cartilages is then illustrated.