TY - JOUR
AU - Nishimura, Masaki
AU - Ryuichi Shigemoto
AU - Matsubayashi, K
AU - Mimori, Y
AU - Kameyama, Masakuni
ID - 2521
IS - 11
JF - Clinical Neurology
TI - Meningoencephalitis during the pre-icteric phase of hepatitis A - a case report
VL - 27
ER -
TY - CONF
AB - We consider the problem of obtaining sharp (nearly quadratic) bounds for the combinatorial complexity of the lower envelope (i.e. pointwise minimum) of a collection of n bivariate (or generally multi-variate) continuous and "simple" functions, and of designing efficient algorithms for the calculation of this envelope. This problem generalizes the well-studied univariate case (whose analysis is based on the theory of Davenport-Schinzel sequences), but appears to be much more difficult and still largely unsolved. It is a central problem that arises in many areas in computational and combinatorial geometry, and has numerous applications including generalized planar Voronoi diagrams, hidden surface elimination for intersecting surfaces, purely translational motion planning, finding common transversals of polyhedra, and more. In this abstract we provide several partial solutions and generalizations of this problem, and apply them to the problems mentioned above. The most significant of our results is that the lower envelope of n triangles in three dimensions has combinatorial complexity at most O(n2α(n)) (where α(n) is the extremely slowly growing inverse of Ackermann's function), that this bound is tight in the worst case, and that this envelope can be calculated in time O(n2α(n)).
AU - Herbert Edelsbrunner
AU - Pach, János
AU - Schwartz, Jacob T
AU - Sharir, Micha
ID - 3514
TI - On the lower envelope of bivariate functions and its applications
ER -
TY - JOUR
AB - We have analysed the role of sampling drift in inducing shifts between alternative adaptive peaks, in small and rapidly growing populations. Using a simple model of disruptive selection on a polygenic character, we calculate the net probabilityofapeakshift. If the growth rate is high, theprobabilityofashiftina growing population is insensitive to selection on the character. Assuming that the character is effectively neutral during the brief initial increase, we find that theprobabilityofapeakshift is given by theprobabilityof finding a standard normal variate greater than √2ΔV where ΔV is the reduction in additive genetic variance during the growth period. This result holds for arbitrary pattern of increase in size, provided that the rate of increase is high enough for selection to be negligible, and the character depends on a large number of loci. Comparing theprobabilityofpeakshiftsin founding populations with the rate ofshiftsin static and allopatric populations it appears that although strongly selected shifts are only likely to occur ina growing population, a static population is a more congenial setting for adaptive shifts.
AU - Rouhani, Shahin
AU - Nicholas Barton
ID - 3656
IS - 1
JF - Journal of Theoretical Biology
TI - The probability of peak shifts in a founder population
VL - 126
ER -
TY - JOUR
AB - Shifts between adaptive peaks, caused by sampling drift, are involved in both speciation and adaptation via Wright's “shiftingbalance.” We use techniques from statistical mechanics to calculate the rate of such transitions for apopulation in a single panmictic deme and for apopulation which is continuously distributed over one- and two-dimensional regions. This calculation applies in the limit where transitions are rare. Our results indicate that stochastic divergence is feasible despite free gene flow, provided that neighbourhood size is low enough. In two dimensions, the rate of transition depends primarily on neighbourhood size N and only weakly on selection pressure (≈sk exp(− cN)), where k is a number determined by the local population structure, in contrast with the exponential dependence on selection pressure in one dimension (≈exp(− cN √s)) or in a single deme (≈exp(− cNs)). Our calculations agree with simulations of a single deme and a one-dimensional population.
AU - Rouhani, Shahin
AU - Nicholas Barton
ID - 3657
IS - 3
JF - Theoretical Population Biology
TI - Speciation and the "shifting balance" in a continuous population
VL - 31
ER -
TY - JOUR
AB - Females of the grasshopper Podisima pedestris were collected from the middle of a hybrid zone between two chromosomal races in the Alpes Maritimes. They had already mated in the field, and could therefore lay fertilised eggs in the laboratory. The embryos were karyotyped, and found to contain an excess of chromosomal homozygotes. No evidence of assortative mating was found from copulating pairs taken in the field. The excess appears to have been caused by a combination of multiple insemination and assortative fertilisation. The genetics of the assortment, and the implications for the evolution of reproductive isolation are discussed.
AU - Hewitt, Godfrey M
AU - Nichols, R. A.
AU - Nicholas Barton
ID - 3658
IS - 3
JF - Heredity
TI - Homogamy in a hybrid zone in the alpine grasshopper Podisma pedestris
VL - 59
ER -
TY - JOUR
AU - Charlesworth, Brian
AU - Coyne, Jerry A
AU - Nicholas Barton
ID - 3659
IS - 1
JF - American Naturalist
TI - The relative rates of evolution of sex chromosomes and autosomes.
VL - 130
ER -
TY - JOUR
AB - The maintenance of polygenic variability by a balance between mutation and stabilizing selection has been analysed using two approximations: the ‘Gaussian’ and the ‘house of cards’. These lead to qualitatively different relationships between the equilibrium genetic variance and the parameters describing selection and mutation. Here we generalize these approximations to describe the dynamics of genetic means and variances under arbitrary patterns of selection and mutation. We incorporate genetic drift into the same mathematical framework.
The effects of frequency-independent selection and genetic drift can be determined from the gradient of log mean fitness and a covariance matrix that depends on genotype frequencies. These equations describe an ‘adaptive landscape’, with a natural metric of genetic distance set by the covariance matrix. From this representation we can change coordinates to derive equations describing the dynamics of an additive polygenic character in terms of the moments (means, variances, …) of allelic effects at individual loci. Only under certain simplifying conditions, such as those derived from the Gaussian and house-of-cards approximations, do these general recursions lead to tractable equations for the first few phenotypic moments. The alternative approximations differ in the constraints they impose on the distributions of allelic effects at individual loci. The Gaussian-based prediction that evolution of the phenotypic mean does not change the genetic variance is shown to be a consequence of the assumption that the allelic distributions are never skewed. We present both analytical and numerical results delimiting the parameter values consistent with our approximations.
AU - Nicholas Barton
AU - Turelli, Michael
ID - 3660
IS - 2
JF - Genetical Research
TI - Adaptive landscapes, genetic distance, and the evolution of quantitative characters
VL - 49
ER -
TY - JOUR
AB - We derive a formula giving thefrequency with which random drift shifts a population betweenalternativeequilibria. This formula is valid when such shifts are rare (Ns >> 1), and applies over a wide range of mutation rates. When the number of mutations entering the population is low (4Nμ << 1), the rate of stochastic shifts reduces to the product ofthe mutation rate and the probability of fixation of a single mutation. However, when many mutations enter the population in each generation (4Nμ >> 1), the rate is higher than would be expected if mutations were established independently, and converges to that given by a gaussian approximation. We apply recent results on bistable systems to extend this formula to the general multidimensional case. This gives an explicit expression for thefrequencyof stochastic shifts, which depends only on theequilibrium probability distribution near the saddle point separating thealternative stable states. The plausibility of theories of speciation through random drift are discussed in the light of these results.
AU - Nicholas Barton
AU - Rouhani, Shahin
ID - 3661
IS - 4
JF - Journal of Theoretical Biology
TI - The frequency of shifts between alternative equilibria
VL - 125
ER -
TY - BOOK
AB - Computational geometry as an area of research in its own right emerged in the early seventies of this century. Right from the beginning, it was obvious that strong connections of various kinds exist to questions studied in the considerably older field of combinatorial geometry. For example, the combinatorial structure of a geometric problem usually decides which algorithmic method solves the problem most efficiently. Furthermore, the analysis of an algorithm often requires a great deal of combinatorial knowledge. As it turns out, however, the connection between the two research areas commonly referred to as computa tional geometry and combinatorial geometry is not as lop-sided as it appears. Indeed, the interest in computational issues in geometry gives a new and con structive direction to the combinatorial study of geometry. It is the intention of this book to demonstrate that computational and com binatorial investigations in geometry are doomed to profit from each other. To reach this goal, I designed this book to consist of three parts, acorn binatorial part, a computational part, and one that presents applications of the results of the first two parts. The choice of the topics covered in this book was guided by my attempt to describe the most fundamental algorithms in computational geometry that have an interesting combinatorial structure. In this early stage geometric transforms played an important role as they reveal connections between seemingly unrelated problems and thus help to structure the field.
AU - Edelsbrunner, Herbert
ID - 3900
SN - 9783540137221
TI - Algorithms in Combinatorial Geometry
VL - 10
ER -
TY - JOUR
AB - The visibility graph of a finite set of line segments in the plane connects two endpoints u and v if and only if the straight line connection between u and v does not cross any line segment of the set. This article proves that 5n - 4 is a lower bound on the number of edges in the visibility graph of n nonintersecting line segments in the plane. This bound is tight.
AU - Herbert Edelsbrunner
AU - Shen, Xiaojun
ID - 4094
IS - 2
JF - Information Processing Letters
TI - A tight lower bound on the size of visibility graphs
VL - 26
ER -