@article{3466,
abstract = {Amphibian myelinated nerve fibers were treated with collagenase and protease. Axons with retraction of the myelin sheath were patch-clamped in the nodal and paranodal region. One type of Na channel was found. It has a single-channel conductance of 11 pS (15 degrees C) and is blocked by tetrodotoxin. Averaged events show the typical activation and inactivation kinetics of macroscopic Na current. Three potential-dependent K channels were identified (I, F, and S channel). The I channel, being the most frequent type, has a single-channel conductance of 23 pS (inward current, 105 mM K on both sides of the membrane), activates between -60 and -30 mV, deactivates with intermediate kinetics, and is sensitive to dendrotoxin. The F channel has a conductance of 30 pS, activates between -40 and 60 mV, and deactivates with fast kinetics. The former inactivates within tens of seconds; the latter inactivates within seconds. The third type, the S channel, has a conductance of 7 pS and deactivates slowly. All three channels can be blocked by external tetraethylammonium chloride. We suggest that these distinct K channel types form the basis for the different components of macroscopic K current described previously.},
author = {Peter Jonas and Bräu, Michael E and Hermsteiner, Markus and Vogel, Werner},
journal = {PNAS},
number = {18},
pages = {7238 -- 7242},
publisher = {National Academy of Sciences},
title = {{Single-channel recording in myelinated nerve fibers reveals one type of Na channel but different K channels}},
volume = {86},
year = {1989},
}
@inproceedings{3549,
author = {Herbert Edelsbrunner},
pages = {83 -- 89},
publisher = {Institute of the Electronics, Information and Communication Enginneers},
title = {{Spatial triangulations with dihedral angle conditions}},
year = {1989},
}
@article{3652,
abstract = {Frequency-dependent selection against rare forms can maintain clines. For weak selection, s, in simple linear models of frequency-dependence, single locus clines are stabilized with a maximum slope of between {complex}s/{complex}8 {sigma} and {complex}s/{complex}12 {delta}, where {sigma} is the dispersal distance. These clines are similar to those maintained by heterozygote disadvantage. Using computer simulations, the weak-selection analytical results are extended to higher selection pressures with up to three unlinked genes. Graphs are used to display the effect of selection, migration, dominance, and number of loci on cline widths, speeds of cline movements, two-way gametic correlations (``linkage disequilibria''), and heterozygote deficits. The effects of changing the order of reproduction, migration, and selection, are also briefly explored. Epistasis can also maintain tension zones. We show that epistatic selection is similar in its effects to frequency-dependent selection, except that the disequilibria produced in the zone will be higher for a given level of selection. If selection consists of a mixture of frequency-dependence and epistasis, as is likely in nature, the error made in estimating selection is usually less than twofold. From the graphs, selection and migration can be estimated using knowledge of the dominance and number of genes, of gene frequences and of gametic correlations from a hybrid zone.},
author = {Mallet, James L and Nicholas Barton},
journal = {Genetics},
number = {4},
pages = {967 -- 976},
publisher = {Genetics Society of America},
title = {{Inference from clines stabilized by frequency-dependent selection}},
volume = {122},
year = {1989},
}
@article{3653,
abstract = {Frequency-dependent selection on warning color can maintain narrow hybrid zones between unpalatable prey taxa. To measure such selection, we transferred marked Heliconius erato (Lepidoptera: Nymphalidae) in both directions across a 10-km-wide hybrid zone between Peruvian races differing in color pattern. These experimental H. erato were released at four sites, along with control H. erato of the phenotype native to each site. Survival of experimental butterflies was significantly lower than that of controls at two sites and overall. Most selection, measured as differences in survival, occurred soon after release. Selection against foreign morphs was 52% (confidence limits: 25-71%) and was probably due to bird attacks on unusual warning-color morphs (more than 10% of the recaptures had beak marks). Since only three major loci determine the color-pattern differences, this suggests an average selection coefficient of 0.17 per locus, sufficient to maintain the narrow clines in H. erato.
},
author = {Mallet, James L and Nicholas Barton},
journal = {Evolution},
pages = {421 -- 431},
publisher = {Wiley-Blackwell},
title = {{Strong natural selection in a warning color hybrid zone}},
doi = {10.2307/2409217 },
volume = {43},
year = {1989},
}
@article{3654,
abstract = {Many species are divided into a mosaic of genetically distinct populations, separated by narrow zones of hybridization. Studies of hybrid zones allow us to quantify the genetic differences responsible for speciation, to measure the diffusion of genes between diverging taxa, and to understand the spread of alternative adaptations.},
author = {Nicholas Barton and Hewitt, Godfrey M},
journal = {Nature},
pages = {497 -- 503},
publisher = {Nature Publishing Group},
title = {{Adaptation, speciation and hybrid zones}},
doi = {10.1038/341497a0},
volume = {341},
year = {1989},
}
@article{2522,
abstract = {Non-pyramidal neurons in cat Ammon's horn were shown to send their axons to the supramammillary regions (SMR), i.e. the supramammillary nucleus and its vicinities including the supramammillary nucleus and the lateral, posterior and dorsal hypothalamic areas: wheat germ agglutinin-horseradish peroxidase (WGA-HRP) injection into Ammon's horn resulted in labeling of presumed axon terminals in the SMR; and after injecting HRP into the SMR, retrogradely labeled non-pyramidal neurons were seen in Ammon's horn.},
author = {Ino, Tadashi and Itoh, Kazuo and Kamiya, Hiroto and Ryuichi Shigemoto and Akiguchi, Ichiro and Mizuno, Noboru},
journal = {Brain Research},
number = {1},
pages = {173 -- 177},
publisher = {Elsevier},
title = {{Direct projections of non-pyramidal neurons of Ammon's horn to the supramammillary region in the cat}},
doi = {10.1016/0006-8993(88)91219-X},
volume = {460},
year = {1988},
}
@article{2523,
abstract = {Injection of large amounts of a mixture of horseradish peroxidase and wheat germ agglutinin-horseradish peroxidase conjugate into the upper cervical segments of the spinal cord in the Japanese monkey (Macaca fuscata) led to the retrograde labeling of a small number of neuronal cell bodies within the rostral part of the subthalamic nucleus of Luys. Direct projection from the subthalamic nucleus to the spinal cord appeared to be much less prominent in the Japanese monkey than in the cat and rat.},
author = {Mizuno, Noboru and Ueyama, Teizo and Itoh, Kazuo and Satoda, Takahiro and Tashiro, Takashi and Ryuichi Shigemoto},
journal = {Neuroscience Letters},
number = {1},
pages = {13 -- 18},
publisher = {Elsevier},
title = {{Direct projections from the subthalamic nucleus of Luys to the spinal cord in the Japanese monkey}},
doi = {10.1016/0304-3940(88)90473-9},
volume = {89},
year = {1988},
}
@article{2524,
abstract = {Alpha-ketoglutamate (α-KG) reductive amination activity in rat brain was found to be mostly absorbed with an antibody against liver glutamate dehydrogenase. With this and anti-glutamine synthetase antibodies, α-KG reductive amination activity was immunocytochemically shown to coexist with glutamine synthetase activity in astrocytes. The results suggest that astrocytes de novo synthesize glutamate from α-KG and ammonia, and metabolize it to glutamine.},
author = {Kaneko, Takeshi and Ryuichi Shigemoto and Mizuno, Noboru},
journal = {Brain Research},
number = {1},
pages = {160 -- 164},
publisher = {Elsevier},
title = {{Metabolism of glutamate and ammonia in astrocyte an immunocytochemical study}},
doi = {10.1016/0006-8993(88)90069-8},
volume = {457},
year = {1988},
}
@article{1941,
author = {Leonid Sazanov and Karavaev, V A and Kukushkin, A K},
journal = {J. Phys. Chem-Russia},
pages = {3351 -- 3354},
publisher = {Elsevier},
title = {{Mathematical model of photosynthesis regulation accounts for the effects of changes in external conditions and observed oscillations}},
volume = {52},
year = {1988},
}
@article{4090,
abstract = {In this paper we study the problem of polygonal separation in the plane, i.e., finding a convex polygon with minimum number k of sides separating two given finite point sets (k-separator), if it exists. We show that for k = Θ(n), is a lower bound to the running time of any algorithm for this problem, and exhibit two algorithms of distinctly different flavors. The first relies on an O(n log n)-time preprocessing task, which constructs the convex hull of the internal set and a nested star-shaped polygon determined by the external set; the k-separator is contained in the annulus between the boundaries of these two polygons and is constructed in additional linear time. The second algorithm adapts the prune-and-search approach, and constructs, in each iteration, one side of the separator; its running time is O(kn), but the separator may have one more side than the minimum.},
author = {Herbert Edelsbrunner and Preparata, Franco P},
journal = {Information and Computation},
number = {3},
pages = {218 -- 232},
publisher = {Elsevier},
title = {{Minimum polygonal separation}},
doi = {10.1016/0890-5401(88)90049-1},
volume = {77},
year = {1988},
}
@article{4091,
abstract = {An X-ray probe through a polygon measures the length of intersection between a line and the polygon. This paper considers the properties of various classes of X-ray probes, and shows how they interact to give finite strategies for completely describing convex n-gons. It is shown that (3n/2)+6 probes are sufficient to verify a specified n-gon, while for determining convex polygons (3n-1)/2 X-ray probes are necesssary and 5n+O(1) sufficient, with 3n+O(1) sufficient given that a lower bound on the size of the smallest edge of P is known.},
author = {Herbert Edelsbrunner and Skiena,Steven S},
journal = {SIAM Journal on Computing},
number = {5},
pages = {870 -- 882},
publisher = {SIAM},
title = {{Probing convex polygons with X-Rays}},
doi = {10.1137/0217054 },
volume = {17},
year = {1988},
}
@inproceedings{4096,
author = {Herbert Edelsbrunner},
pages = {201 -- 213},
publisher = {Springer},
title = {{Geometric structures in computational geometry}},
doi = {10.1007/3-540-19488-6_117},
volume = {317},
year = {1988},
}
@inproceedings{4097,
abstract = {Arrangements of curves in the plane are of fundamental significance in many problems of computational and combinatorial geometry (e.g. motion planning, algebraic cell decomposition, etc.). In this paper we study various topological and combinatorial properties of such arrangements under some mild assumptions on the shape of the curves, and develop basic tools for the construction, manipulation, and analysis of these arrangements. Our main results include a generalization of the zone theorem of [EOS], [CGL] to arrangements of curves (in which we show that the combinatorial complexity of the zone of a curve is nearly linear in the number of curves), and an application of (some weaker variant of) that theorem to obtain a nearly quadratic incremental algorithm for the construction of such arrangements.},
author = {Herbert Edelsbrunner and Guibas, Leonidas and Pach, János and Pollack, Richard and Seidel, Raimund and Sharir, Micha},
pages = {214 -- 229},
publisher = {Springer},
title = {{Arrangements of curves in the plane - topology, combinatorics, and algorithms}},
doi = {10.1007/3-540-19488-6_118},
volume = {317},
year = {1988},
}
@misc{4315,
author = {Coyne, Jerry A and Nicholas Barton},
booktitle = {Nature},
pages = {485 -- 486},
publisher = {Nature Publishing Group},
title = {{What do we know about speciation ?}},
doi = {10.1038/331485a0},
volume = {331},
year = {1988},
}
@misc{4316,
author = {Nicholas Barton and Jones, Steve},
booktitle = {Nature},
pages = {597 -- 597},
publisher = {Nature Publishing Group},
title = {{Molecular evolutionary genetics}},
doi = {10.1038/332597a0},
volume = {332},
year = {1988},
}
@inbook{4317,
author = {Nicholas Barton},
booktitle = {Analytical biogeography},
editor = {Myers, Alan A and Giller, Paul S},
pages = {185 -- 218},
publisher = {Chapman Hall},
title = {{Speciation}},
year = {1988},
}
@misc{4318,
author = {Nicholas Barton and Jones, Steve and Mallet, James L},
booktitle = {Nature},
pages = {13 -- 14},
publisher = {Nature Publishing Group},
title = {{No barriers to speciation}},
doi = {10.1038/336013a0},
volume = {336},
year = {1988},
}
@article{3655,
author = {Dallas, John F and Nicholas Barton and Dover, Gabriel A.},
journal = {Molecular Biology and Evolution},
number = {6},
pages = {660 -- 674},
publisher = {Oxford University Press},
title = {{Interracial rDNA variation in the grasshopper Podisma pedestris}},
volume = {5},
year = {1988},
}
@article{2521,
author = {Nishimura, Masaki and Ryuichi Shigemoto and Matsubayashi, K and Mimori, Y and Kameyama, Masakuni},
journal = {Clinical Neurology},
number = {11},
pages = {1441 -- 1444},
publisher = {Societas Neurologica Japonica},
title = {{Meningoencephalitis during the pre-icteric phase of hepatitis A - a case report}},
volume = {27},
year = {1987},
}
@book{3900,
abstract = {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.},
author = {Edelsbrunner, Herbert},
isbn = {9783540137221},
publisher = {Springer},
title = {{Algorithms in Combinatorial Geometry}},
volume = {10},
year = {1987},
}
@article{4094,
abstract = {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.},
author = {Herbert Edelsbrunner and Shen, Xiaojun},
journal = {Information Processing Letters},
number = {2},
pages = {61 -- 64},
publisher = {Elsevier},
title = {{A tight lower bound on the size of visibility graphs}},
doi = {10.1016/0020-0190(87)90038-X},
volume = {26},
year = {1987},
}
@article{4095,
abstract = {he kth-order Voronoi diagram of a finite set of sites in the Euclidean plane E2 subdivides E2 into maximal regions such that all points within a given region have the same k nearest sites. Two versions of an algorithm are developed for constructing the kth-order Voronoi diagram of a set of n sites in O(n2 log n + k(n - k) log2 n) time, O(k(n - k)) storage, and in O(n2 + k(n - k) log2 n) time, O(n2) storage, respectively.},
author = {Chazelle, Bernard and Herbert Edelsbrunner},
journal = {IEEE Transactions on Computers},
number = {11},
pages = {1349 -- 1354},
publisher = {IEEE},
title = {{An improved algorithm for constructing kth-order Voronoi diagrams}},
doi = {10.1109/TC.1987.5009474},
volume = {36},
year = {1987},
}
@article{4100,
abstract = {This paper investigates the existence of linear space data structures for range searching. We examine thehomothetic range search problem, where a setS ofn points in the plane is to be preprocessed so that for any triangleT with sides parallel to three fixed directions the points ofS that lie inT can be computed efficiently. We also look atdomination searching in three dimensions. In this problem,S is a set ofn points inE 3 and the question is to retrieve all points ofS that are dominated by some query point. We describe linear space data structures for both problems. The query time is optimal in the first case and nearly optimal in the second.
},
author = {Chazelle, Bernard and Herbert Edelsbrunner},
journal = {Discrete & Computational Geometry},
number = {1},
pages = {113 -- 126},
publisher = {Springer},
title = {{Linear space data structures for two types of range search}},
doi = {10.1007/BF02187875},
volume = {2},
year = {1987},
}
@article{4101,
abstract = {In a number of recent papers, techniques from computational geometry (the field of algorithm design that deals with objects in multi-dimensional space) have been applied to some problems in the area of computer graphics. In this way, efficient solutions were obtained for the windowing problem that asks for those line segments in a planar set that lie in given window (range) and the moving problem that asks for the first line segment that comes into the window when moving the window in some direction. In this paper we show that also the zooming problem, which asks for the first line segment that comes into the window when we enlarge it, can be solved efficiently. This is done by repeatedly performing range queries with ranges of varying sizes. The obtained structure is dynamic and yields a query time of O(log2n) and an insertion and deletion time of O(log2n), where n is the number of line segments in the set. The amount of storage required is O(n log n). It is also shown that the technique of repeated range search can be used to solve several other problems efficiently.
},
author = {Herbert Edelsbrunner and Overmars, Mark H},
journal = {Information Processing Letters},
number = {6},
pages = {413 -- 417},
publisher = {Elsevier},
title = {{Zooming by repeated range detection}},
doi = {10.1016/0020-0190(87)90120-7},
volume = {24},
year = {1987},
}
@article{4102,
abstract = {Determining or counting geometric objects that intersect another geometric query object is at the core of algorithmic problems in a number of applied areas of computer science. This article presents a family of space-efficient data structures that realize sublinear query time for points, line segments, lines and polygons in the plane, and points, line segments, planes, and polyhedra in three dimensions.},
author = {Dobkin, David P and Herbert Edelsbrunner},
journal = {Journal of Algorithms},
number = {3},
pages = {348 -- 361},
publisher = {Academic Press},
title = {{Space searching for intersecting objects}},
doi = {10.1016/0196-6774(87)90015-0},
volume = {8},
year = {1987},
}
@article{4319,
abstract = {The grasshopper Podisma pedestris contains two chromosomal races, which differ by a Robertsonian fusion between the sex chromosome and an autosome, and which meet in a narrow hybrid zone in the Alpes Maritimes. DNA content variation across this hybrid zone was investigated by optical densitometry of Feulgen stained spermatids. Spermatids from males with the unfused sex chromosome stain more strongly than those from males with the fused chromosome. The difference between the karyotypes is greater in the centre of the hybrid zone, suggesting that it is not a pleiotropic effect of the fusion itself, but is due instead to differences at closely linked loci.},
author = {Westerman, Michael and Nicholas Barton and Hewitt, Godfrey M},
journal = {Heredity},
pages = {221 -- 228},
publisher = {Nature Publishing Group},
title = {{Differences in DNA content between two chromosomal races of the grasshopper Podisma pedestris}},
doi = {10.1038/hdy.1987.36},
volume = {58},
year = {1987},
}
@article{4320,
abstract = {Bosonic field theories may be formulated in terms of stochastic differential equations. The characteristic long term behaviour of these systems is a decay into the global minimum of their Hamiltonian. If local minima exist, the rate of this decay is determined by instanton effects. We calculate the decay rate and perform computer simulations on a 1 + 1 dimensional model to test the instanton approximation. We find the instanton approximations to be in very good agreement with the simulation results.
Copyright © 1987 Published by Elsevier B.V.},
author = {Rouhani, Shahin and Nicholas Barton},
journal = {Physica A},
number = {1-2},
pages = {220 -- 226},
publisher = {Elsevier},
title = {{Instantons and stochastic quantization}},
doi = {10.1016/0378-4371(87)90064-1},
volume = {143},
year = {1987},
}
@article{4322,
abstract = {A method is developed for calculating the probability of establishment of an allele which is favoured in some places, but not others, in a large subdivided population. This method is quite general, and could be used to calculate the chance that any system which is linear near an absorbing boundary will move away from that boundary. The results are applied to a population distributed along one dimension. Only mutants which arise within a distance σ/ √2s of the region in which they are favoured stand an appreciable chance of establishment. The net chance of establishment of mutations distributed randomly across the habitat will be decreased by gene flow if selection against them is sufficiently strong. However, if the mutations are only weakly deleterious outside some limited region, gene flow may increase the net chance of establishment.},
author = {Nicholas Barton},
journal = {Genetical Research},
number = {1},
pages = {35 -- 40},
publisher = {Cambridge University Press},
title = {{The probability of establishment of an advantageous mutation in a subdivided population}},
doi = {10.1017/S0016672300023314},
volume = {50},
year = {1987},
}
@inproceedings{3514,
abstract = {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)).},
author = {Herbert Edelsbrunner and Pach, János and Schwartz, Jacob T and Sharir, Micha},
pages = {27 -- 37},
publisher = {IEEE},
title = {{On the lower envelope of bivariate functions and its applications}},
doi = {10.1109/SFCS.1987.44},
year = {1987},
}
@article{3656,
abstract = {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.},
author = {Rouhani, Shahin and Nicholas Barton},
journal = {Journal of Theoretical Biology},
number = {1},
pages = {51 -- 62},
publisher = {Elsevier},
title = {{The probability of peak shifts in a founder population}},
doi = {10.1016/S0022-5193(87)80100-5},
volume = {126},
year = {1987},
}
@article{3657,
abstract = {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.},
author = {Rouhani, Shahin and Nicholas Barton},
journal = {Theoretical Population Biology},
number = {3},
pages = {465 -- 492},
publisher = {Academic Press},
title = {{Speciation and the "shifting balance" in a continuous population}},
doi = {10.1016/0040-5809(87)90016-5},
volume = {31},
year = {1987},
}
@article{3658,
abstract = {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.},
author = {Hewitt, Godfrey M and Nichols, R. A. and Nicholas Barton},
journal = {Heredity},
number = {3},
pages = {457 -- 466},
publisher = {Nature Publishing Group},
title = {{Homogamy in a hybrid zone in the alpine grasshopper Podisma pedestris}},
doi = {10.1038/hdy.1987.156},
volume = {59},
year = {1987},
}
@article{3659,
author = {Charlesworth, Brian and Coyne, Jerry A and Nicholas Barton},
journal = {American Naturalist},
number = {1},
pages = {113 -- 146},
publisher = {University of Chicago Press},
title = {{The relative rates of evolution of sex chromosomes and autosomes.}},
volume = {130},
year = {1987},
}
@article{3660,
abstract = {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.},
author = {Nicholas Barton and Turelli, Michael},
journal = {Genetical Research},
number = {2},
pages = {157 -- 174},
publisher = {Cambridge University Press},
title = {{Adaptive landscapes, genetic distance, and the evolution of quantitative characters}},
doi = {10.1017/S0016672300026951},
volume = {49},
year = {1987},
}
@article{3661,
abstract = {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.},
author = {Nicholas Barton and Rouhani, Shahin},
journal = {Journal of Theoretical Biology},
number = {4},
pages = {397 -- 418},
publisher = {Elsevier},
title = {{The frequency of shifts between alternative equilibria}},
doi = {10.1016/S0022-5193(87)80210-2},
volume = {125},
year = {1987},
}
@article{4098,
abstract = {To points p and q of a finite set S in d-dimensional Euclidean space Ed are extreme if {p, q} = S ∩ h, for some open halfspace h. Let e2(d)(n) be the maximum number of extreme pairs realized by any n points in Ed. We give geometric proofs of , if n⩾4, and e2(3)(n) = 3n−6, if n⩾6. These results settle the question since all other cases are trivial.},
author = {Herbert Edelsbrunner and Stöckl, Gerd},
journal = {Journal of Combinatorial Theory Series A},
number = {2},
pages = {344 -- 349},
publisher = {Elsevier},
title = {{The number of extreme pairs of finite point-sets in Euclidean spaces}},
doi = {10.1016/0097-3165(86)90075-0},
volume = {43},
year = {1986},
}
@article{4099,
abstract = {Let S denote a set of n points in the Euclidean plane. A halfplanar range query specifies a halfplane h and requires the determination of the number of points in S which are contained in h. A new data structure is described which stores S in O(n) space and allows us to answer a halfplanar range query in O(nlog2(1+√5)−1) time in the worst case, thus improving the best result known before. The structure can be built in O(n log n) time.},
author = {Herbert Edelsbrunner and Welzl, Emo},
journal = {Information Processing Letters},
number = {5},
pages = {289 -- 293},
publisher = {Elsevier},
title = {{Halfplanar range search in linear space and O(n0.695) query time}},
doi = {10.1016/0020-0190(86)90088-8},
volume = {23},
year = {1986},
}
@article{4103,
abstract = {Let A be an arrangement of n lines in the plane. Suppose F1,…, Fk are faces in the dissection induced by A and that Fi is a t(Fi)-gon. We give asymptotic bounds on the maximal sum ∑i=1kt(Fi) which can be realized by k different faces in an arrangement of n lines. The results improve known bounds for k of higher order than n(1/2).},
author = {Herbert Edelsbrunner and Welzl, Emo},
journal = {Journal of Combinatorial Theory Series A},
number = {2},
pages = {159 -- 166},
publisher = {Elsevier},
title = {{On the maximal number of edges of many faces in an arrangement}},
doi = {10.1016/0097-3165(86)90078-6},
volume = {41},
year = {1986},
}
@article{4104,
abstract = {Point location, often known in graphics as “hit detection,” is one of the fundamental problems of computational geometry. In a point location query we want to identify which of a given collection of geometric objects contains a particular point. Let $\mathcal{S}$ denote a subdivision of the Euclidean plane into monotone regions by a straight-line graph of $m$ edges. In this paper we exhibit a substantial refinement of the technique of Lee and Preparata [SIAM J. Comput., 6 (1977), pp. 594–606] for locating a point in $\mathcal{S}$ based on separating chains. The new data structure, called a layered dag, can be built in $O(m)$ time, uses $O(m)$ storage, and makes possible point location in $O(\log m)$ time. Unlike previous structures that attain these optimal bounds, the layered dag can be implemented in a simple and practical way, and is extensible to subdivisions with edges more general than straight-line segments.
© 1986 Society for Industrial and Applied Mathematics},
author = {Herbert Edelsbrunner and Guibas, Leonidas J and Stolfi, Jorge},
journal = {SIAM Journal on Computing},
number = {2},
pages = {317 -- 340},
publisher = {SIAM},
title = {{Optimal point location in a monotone subdivision}},
doi = {10.1137/0215023},
volume = {15},
year = {1986},
}
@article{4105,
abstract = {A finite set of lines partitions the Euclidean plane into a cell complex. Similarly, a finite set of $(d - 1)$-dimensional hyperplanes partitions $d$-dimensional Euclidean space. An algorithm is presented that constructs a representation for the cell complex defined by $n$ hyperplanes in optimal $O(n^d )$ time in $d$ dimensions. It relies on a combinatorial result that is of interest in its own right. The algorithm is shown to lead to new methods for computing $\lambda $-matrices, constructing all higher-order Voronoi diagrams, halfspatial range estimation, degeneracy testing, and finding minimum measure simplices. In all five applications, the new algorithms are asymptotically faster than previous results, and in several cases are the only known methods that generalize to arbitrary dimensions. The algorithm also implies an upper bound of $2^{cn^d } $, $c$ a positive constant, for the number of combinatorially distinct arrangements of $n$ hyperplanes in $E^d $.
© 1986 Society for Industrial and Applied Mathematics},
author = {Herbert Edelsbrunner and O'Rourke, Joseph and Seidel, Raimund},
journal = {SIAM Journal on Computing},
number = {2},
pages = {341 -- 363},
publisher = {SIAM},
title = {{Constructing arrangements of lines and hyperplanes with applications}},
doi = {10.1137/0215024},
volume = {15},
year = {1986},
}
@article{4106,
abstract = {Let B be a set of nb black points and W a set of nw, white points in the Euclidean plane. A line h is said to bisect B (or W) if, at most, half of the points of B (or W) lie on any one side of h. A line that bisects both B and W is called a ham-sandwich cut of B and W. We give an algorithm that computes a ham-sandwich cut of B and W in 0((nh+nw) log (min {nb, nw}+ 1)) time. The algorithm is considerably simpler than the previous most efficient one which takes 0((nb + nw) log (nb + nw)) time.},
author = {Herbert Edelsbrunner and Waupotitsch, Roman},
journal = {Journal of Symbolic Computation},
number = {2},
pages = {171 -- 178},
publisher = {Elsevier},
title = {{Computing a ham-sandwich cut in two dimensions}},
doi = {10.1016/S0747-7171(86)80020-7},
volume = {2},
year = {1986},
}
@article{4107,
abstract = {A set of m planes dissects E3 into cells, facets, edges and vertices. Letting deg(c) be the number of facets that bound a cellc, we give exact and asymptotic bounds on the maximum of ∈cinCdeg(c), if C is a family of cells of the arrangement with fixed cardinality.},
author = {Herbert Edelsbrunner and Haussler, David H},
journal = {Discrete Mathematics},
number = {C},
pages = {139 -- 146},
publisher = {Elsevier},
title = {{The complexity of cells in 3-dimensional arrangements}},
doi = {10.1016/0012-365X(86)90008-7},
volume = {60},
year = {1986},
}
@article{4108,
abstract = {We propose a uniform and general framework for defining and dealing with Voronoi diagrams. In this framework a Voronoi diagram is a partition of a domainD induced by a finite number of real valued functions onD. Valuable insight can be gained when one considers how these real valued functions partitionD ×R. With this view it turns out that the standard Euclidean Voronoi diagram of point sets inR d along with its order-k generalizations are intimately related to certain arrangements of hyperplanes. This fact can be used to obtain new Voronoi diagram algorithms. We also discuss how the formalism of arrangements can be used to solve certain intersection and union problems.},
author = {Herbert Edelsbrunner and Seidel, Raimund},
journal = {Discrete & Computational Geometry},
number = {1},
pages = {25 -- 44},
publisher = {Springer},
title = {{Voronoi diagrams and arrangements}},
doi = {10.1007/BF02187681},
volume = {1},
year = {1986},
}
@article{4109,
abstract = {Rectangle location search in d dimensions is finding the d-dimensional axis-parallel box of a non-overlapping collection C that contains a query point. A new data structure is proposed that requires optimal space and 0(logd|C|) time for a search. The significance of this data structure in practical applications is substantiated by empirical examinations of its behaviour.},
author = {Herbert Edelsbrunner and Haring, Günter and Hilbert, D},
journal = {Computer Journal},
number = {1},
pages = {76 -- 82},
publisher = {Oxford University Press},
title = {{Rectangular point location in d-dimensions with applications}},
doi = {10.1093/comjnl/29.1.76},
volume = {29},
year = {1986},
}
@article{4110,
abstract = {For $H$ a set of lines in the Euclidean plane, $A(H)$ denotes the induced dissection, called the arrangement of $H$. We define the notion of a belt in $A(H)$, which is bounded by a subset of the edges in $A(H)$, and describe two algorithms for constructing belts. All this is motivated by applications to a host of seemingly unrelated problems including a type of range search and finding the minimum area triangle with the vertices taken from some finite set of points.
© 1986 © Society for Industrial and Applied Mathematics},
author = {Herbert Edelsbrunner and Welzl, Emo},
journal = {SIAM Journal on Computing},
number = {1},
pages = {271 -- 284},
publisher = {SIAM},
title = {{Constructing belts in two-dimensional arrangements with applications}},
doi = {10.1137/0215019},
volume = {15},
year = {1986},
}
@article{4321,
author = {Szymura, Jacek M and Nicholas Barton},
journal = {Evolution; International Journal of Organic Evolution},
pages = {1141 -- 1159},
publisher = {Wiley-Blackwell},
title = {{Genetic analysis of a hybrid zone between the fire-bellied toads Bombina bombina and B. variegata, near Cracow in Southern Poland}},
doi = {3786},
volume = {40},
year = {1986},
}
@article{4323,
abstract = {It is noted that the sibling competition model for the evolution of sex and recombination, as it has been developed so far, involves truncation selection. After briefly reviewing aspects of the development and behaviour of such models an analytical treatment is presented which involves additive selection. Additive selection, as compared with truncation selection, decreases the advantage of sex to such an extent that it is unlikely that sibling competition could overcome its intrinsic two-fold cost, although it could still be important in promoting family variability produced by other mechanisms, such as polyandry.},
author = {Nicholas Barton and POST,R. J},
journal = {Journal of Theoretical Biology},
number = {4},
pages = {381 -- 387},
publisher = {Elsevier},
title = {{Sibling competition and the advantage of mixed families}},
doi = {10.1016/S0022-5193(86)80033-9},
volume = {120},
year = {1986},
}
@article{4324,
abstract = {The maintenance of polygenic variation through a balance between mutation and stabilizing selection can be approximated in two ways. In the ‘Gaussian’ approximation, a normal distribution of allelic effects is assumed at each locus. In the ‘House of Cards’ approximation, the effect of new mutations is assumed to be large compared with the spread of the existing distribution. These approximations were developed to describe models where alleles may have a continuous range of effects. However, previous analyses of models with only two alleles have predicted an equilibrium variance equal to that given by the ‘House of Cards’ approximation. These analyses of biallelic models have assumed that, at equilibrium, the population mean is at the optimum. Here, it is shown that many stable equilibria may coexist, each giving a slight deviation from the optimum. Though the variance is given by the ‘House of Cards’ approximation when the mean is at the optimum, it increases towards a value of the same order as that given by the ‘Gaussian’ approximation when the mean deviates from the optimum. Thus, the equilibrium variance cannot be predicted by any simple model, but depends on the previous history of the population.},
author = {Nicholas Barton},
journal = {Genetical Research},
number = {3},
pages = {209 -- 216},
publisher = {Cambridge University Press},
title = {{The maintenance of polygenic variation through a balance between mutation and stabilising selection}},
doi = {10.1017/S0016672300023156},
volume = {47},
year = {1986},
}
@article{3464,
abstract = {The effects of the major neurotoxic fraction isolated from scorpion venom of Tityus serrulatus, TiTx gamma, on peripheral nerve membrane of Xenopus laevis were studied under current- and voltage-clamp conditions. 700 nmol/l TiTx gamma depolarized the membrane and induced spontaneous activity (150 s-1, maximum value), which ceased within a few minutes. It reduced the amplitude of the action potentials from 109 mV to 52 mV and increased their duration from 1.25 ms to 4.5 ms. 440 nmol/l TiTx gamma induced inward Na current flow at resting potential. The descending branch of the Na current-voltage curve was flattened and shifted approximately 10 mV to more negative potentials. Maximum Na permeability was reduced to about 20%. Both development of and recovery from inactivation of Na permeability were slowed. The steepness of the steady-state inactivation curve was decreased, but the mid-potential changed only insignificantly. No prepulse was necessary to elicit either a shift of activation or an inward current at resting potential. Expressing the toxin effect either in terms of the decrease of Na peak current or of the slowing of inactivation, half-maximum effects were found with 0.3 +/- 0.1 and 3.7 +/- 0.7 mumol/l TiTx gamma, respectively.},
author = {Peter Jonas and Vogel, Werner and Arantes, Eliane C and Giglio, Jose R},
journal = {Pflugers Archiv : European Journal of Physiology},
number = {1},
pages = {92 -- 99},
publisher = {Springer},
title = {{Toxin γ of the scorpion Tityus serrulatus modifies both activation and inactivation of sodium permeability of nerve membrane}},
doi = {10.1007/BF00580727},
volume = {407},
year = {1986},
}
@article{3579,
author = {Herbert Edelsbrunner and Jaromczyk, Jerzy W},
journal = {Congressus Numerantium},
pages = {193 -- 200},
publisher = {Utilitas Mathemtica Publ. Inc.},
title = {{How often can you see yourself in a convex configuration of mirrors?}},
volume = {53},
year = {1986},
}
@article{3580,
abstract = {An edge-skeleton in an arrangementA(H) of a finite set of planes inE 3 is a connected collection of edges inA(H). We give a method that constructs a skeleton inO(√n logn) time per edge. This method implies new and more efficient algorithms for a number of structures in computational geometry including order-k power diagrams inE 2 and space cutting trees inE 3.
We also give a novel method for handling special cases which has the potential to substantially decrease the amount of effort needed to implement geometric algorithms.},
author = {Herbert Edelsbrunner},
journal = {Algorithmica},
number = {1-4},
pages = {93 -- 109},
publisher = {Springer},
title = {{Edge-skeletons in arrangements with applications}},
doi = {10.1007/BF01840438},
volume = {1},
year = {1986},
}
@inproceedings{3602,
author = {Curtis,C. F and Curtis,J. and Nicholas Barton},
publisher = {Liss},
title = {{Methodology for testing the hypothesis of single locus control of host resistance to infection and malignancy}},
year = {1986},
}
@article{3662,
abstract = {The evolution of the probabilities of genetic identity within and between tandemly repeated loci of a multigene family is investigated analytically and numerically. Unbiased intrachromosomal gene conversion, equal crossing over, random genetic drift, and mutation to new alleles are incorporated. Generations are discrete and nonoverlapping; the diploid, monoecious population mates at random. Under the restriction that there is at most one crossover in the multigene family per individual per generation, the dependence on location of the probabilities of identity is treated exactly. In the “homogeneous” approximation to this “exact” model, end effects are disregarded; in the “exchangeable” approximation, to which all previous work was confined, all position dependence is neglected. Numerical results indicate that (i) the exchangeable and homogeneous models are both qualitatively correct, (ii) the exchangeable model is sometimes too inaccurate for quantitative conclusions, and (iii) the homogeneous model is always more accurate than the exchangeable one and is always sufficiently accurate for quantitative conclusions.},
author = {Nagylaki, Thomas and Nicholas Barton},
journal = {Theoretical Population Biology},
number = {3},
pages = {407 -- 437},
publisher = {Academic Press},
title = {{Intrachromosomal gene conversion, linkage, and the evolution of multigene families}},
doi = {10.1016/0040-5809(86)90017-1},
volume = {29},
year = {1986},
}
@article{3663,
abstract = {The conditional average frequency of rare alleles has been shown in simulations to provide a simple and robust estimator of the number of individuals exchanged between local populations in an island model (Nm). This statistic is defined as the average frequency of an allele in those samples in which the allele is present. Here, we show that the conditional average frequency can be calculated from the distribution of allele frequencies. It is a measure of the spread of this distribution, and so is analogous to the standardised variance, FST. Analytic predictions for the island model of migration agree well with the corresponding simulation results. These predictions are based on the assumption that the rare alleles found in samples have reached a "quasi-equilibrium" distribution. As well as relating the conditional average frequency to the underlying allele frequency distribution, our results provide a more accurate method of estimating Nm from the conditional average frequency of private alleles in samples of different sizes.},
author = {Nicholas Barton and Slatkin, Montgomery},
journal = {Heredity},
number = {3},
pages = {409 -- 416},
publisher = {Nature Publishing Group},
title = {{A quasi-equilibrium theory of the distribution of rare alleles in a subdivided population}},
doi = {10.1038/hdy.1986.63},
volume = {56},
year = {1986},
}
@article{3664,
author = {Nicholas Barton and Bengtsson, Bengt O},
journal = {Heredity},
pages = {357 -- 376},
publisher = {Nature Publishing Group},
title = {{The barrier to genetic exchange between hybridising populations}},
volume = {57},
year = {1986},
}
@article{3665,
author = {Nicholas Barton},
journal = {Heredity},
pages = {415 -- 426},
publisher = {Nature Publishing Group},
title = {{The effects of linkage and density-dependent regulation on gene flow}},
volume = {57},
year = {1986},
}
@article{4111,
abstract = {This paper describes an optimal solution for the following geometric search problem defined for a set P of n points in three dimensions: Given a plane h with all points of P on one side and a line ℓ in h, determine a point of P that is hit first when h is rotated around ℓ. The solution takes O(n) space and O(log n) time for a query. By use of geometric transforms, the post-office problem for a finite set of points in two dimensions and certain two-dimensional point location problems are reduced to the former problem and thus also optimally solved.},
author = {Herbert Edelsbrunner and Maurer, Hermann A},
journal = {Information Processing Letters},
number = {1},
pages = {39 -- 47},
publisher = {Elsevier},
title = {{Finding extreme-points in 3-dimensions and solving the post-office problem in the plane}},
doi = {10.1016/0020-0190(85)90107-3},
volume = {21},
year = {1985},
}
@article{4112,
abstract = {The batched static version of a searching problem asks for performing a given set of queries on a given set of objects. All queries are known in advance. The batched dynamic version of a searching problem is the following: given a sequence of insertions, deletions, and queries, perform them on an initially empty set. We will develop methods for solving batched static and batched dynamic versions of searching problems which are in particular applicable to decomposable searching problems. The techniques show that batched static (dynamic) versions of searching problems can often be solved more efficiently than by using known static (dynamic) data structures. In particular, a technique called “streaming” is described that reduces the space requirements considerably. The methods have also a number of applications on set problems. E.g., the k intersecting pairs in a set of n axis-parallel hyper-rectangles in d dimensions can be reported in O (nlogd−1n + k) time using only O(n) space.},
author = {Herbert Edelsbrunner and Overmars, Mark H},
journal = {Journal of Algorithms},
number = {4},
pages = {515 -- 542},
publisher = {Academic Press},
title = {{Batched dynamic solutions to decomposable searching problems}},
doi = {10.1016/0196-6774(85)90030-6},
volume = {6},
year = {1985},
}
@article{4113,
abstract = {Let S denote a set of n points in the Euclidean plane. A subset S′ of S is termed a k-set of S if it contains k points and there exists a straight line which has no point of S on it and separates S′ from S−S′. We let fk(n) denote the maximum number of k-sets which can be realized by a set of n points. This paper studies the asymptotic behaviour of fk(n) as this function has applications to a number of problems in computational geometry. A lower and an upper bound on fk(n) is established. Both are nontrivial and improve bounds known before. In particular, is shown by exhibiting special point-sets which realize that many k-sets. In addition, is proved by the study of a combinatorial problem which is of interest in its own right.},
author = {Herbert Edelsbrunner and Welzl, Emo},
journal = {Journal of Combinatorial Theory Series A},
number = {1},
pages = {15 -- 29},
publisher = {Elsevier},
title = {{On the number of line separations of a finite set in the plane}},
doi = {10.1016/0097-3165(85)90017-2},
volume = {38},
year = {1985},
}
@article{4114,
abstract = {Proportional link linkage (PLL) clustering methods are a parametric family of monotone invariant agglomerative hierarchical clustering methods. This family includes the single, minimedian, and complete linkage clustering methods as special cases; its members are used in psychological and ecological applications. Since the literature on clustering space distortion is oriented to quantitative input data, we adapt its basic concepts to input data with only ordinal significance and analyze the space distortion properties of PLL methods. To enable PLL methods to be used when the numbern of objects being clustered is large, we describe an efficient PLL algorithm that operates inO(n 2 logn) time andO(n 2) space},
author = {Day,William H and Herbert Edelsbrunner},
journal = {Journal of Classification},
number = {2-3},
pages = {239 -- 254},
publisher = {Springer},
title = {{Investigation of Proportional Link Linkage Clustering Methods}},
doi = {10.1007/BF01908077},
volume = {2},
year = {1985},
}
@article{4115,
abstract = {A polygon in the plane is convex if it contains all line segments connecting any two of its points. Let P and Q denote two convex polygons. The computational complexity of finding the minimum and maximum distance possible between two points p in P and q in Q is studied. An algorithm is described that determines the minimum distance (together with points p and q that realize it) in O(logm + logn) time, where m and n denote the number of vertices of P and Q, respectively. This is optimal in the worst case. For computing the maximum distance, a lower bound Ω(m + n) is proved. This bound is also shown to be best possible by establishing an upper bound of O(m + n).},
author = {Herbert Edelsbrunner},
journal = {Journal of Algorithms},
number = {2},
pages = {213 -- 224},
publisher = {Academic Press},
title = {{Computing the extreme distances between two convex polygons}},
doi = {10.1016/0196-6774(85)90039-2},
volume = {6},
year = {1985},
}
@article{4116,
abstract = {A straight line that intersects all members of a set S of objects in the real plane is called a transversal of S. Geometric transforms are described that reduce transversal problems for various types of objects to convex hull problems for points. These reductions lead to efficient algorithms for finding transversals which are also described. Applications of the algorithms are found in computer graphics: “Reproduce the line displayed by a collection of pixels”, and in statistics: “Find the line that minimizes the maximum distance from a collection of (weighted) points in the plane”.},
author = {Herbert Edelsbrunner},
journal = {Theoretical Computer Science},
number = {1},
pages = {55 -- 69},
publisher = {Elsevier},
title = {{Finding Transversals for Sets of Simple Geometric-Figures}},
doi = {10.1016/0304-3975(85)90005-2},
volume = {35},
year = {1985},
}
@article{4120,
abstract = {Let P be a set of n points in the Euclidean plane and let C be a convex figure. We study the problem of preprocessing P so that for any query point q, the points of P in C+q can be retrieved efficiently. If constant time sumces for deciding the inclusion of a point in C, we then demonstrate the existence of an optimal solution: the algorithm requires O(n) space and O(k + log n) time for a query with output size k. If C is a disk, the problem becomes the wellknown fixed-radius neighbour problem, to which we thus provide the first known optimal solution.},
author = {Chazelle, Bernard and Herbert Edelsbrunner},
journal = {Journal of Symbolic Computation},
number = {1},
pages = {47 -- 56},
publisher = {Elsevier},
title = {{Optimal solutions for a class of point retrieval problems}},
doi = {10.1016/S0747-7171(85)80028-6},
volume = {1},
year = {1985},
}
@inproceedings{4241,
author = {Curtis,C. F and Curtis,J. and Nicholas Barton},
publisher = {Liss},
title = {{Methodology for testing the hypothesis of single locus control of host resistance to infection and malignancy}},
volume = {3},
year = {1985},
}
@misc{4325,
author = {Jones, Steve and Nicholas Barton},
booktitle = {Nature},
pages = {668 -- 668},
publisher = {Nature Publishing Group},
title = {{Haldane's Rule OK}},
doi = {10.1038/314668a0},
volume = {314},
year = {1985},
}
@article{4326,
author = {Nicholas Barton and Hewitt, Godfrey M},
journal = {Annual Review of Ecology and Systematics},
pages = {113 -- 148},
publisher = {Annual Reviews},
title = {{Analysis of hybrid zones}},
doi = {10.1146/annurev.es.16.110185.000553},
volume = {16},
year = {1985},
}
@article{4117,
author = {Herbert Edelsbrunner and van Leeuwen,Jan and Ottmann,Thomas and Wood, Derick},
journal = {Rairo-Informatique Theorique Et Applications-Theoretical Informatics and Applications},
number = {2},
pages = {171 -- 183},
publisher = {Cambridge University Press},
title = {{Computing the connected components of simple rectilinear geometrical objects in D-Space}},
volume = {18},
year = {1984},
}
@article{4118,
abstract = {A rectilinear polygon can be viewed as an art gallery room whose walls meet at right angles. An algorithm is presented that stations guards in such a room so that every interior point is visible to some guard. The algorithm partitions the polygon into L-shaped pieces, a subclass of star-shaped pieces, and locates one guard within each kernel. The algorithm runs in O(n log n) time in the worst case for a polygon of n vertices.},
author = {Herbert Edelsbrunner and O'Rourke, Joseph and Welzl, Emo},
journal = {Computer Vision, Graphics, and Image Processing},
number = {2},
pages = {167 -- 176},
publisher = {Academic Press},
title = {{Stationing guards in rectilinear art galleries}},
doi = {10.1016/S0734-189X(84)80041-9},
volume = {27},
year = {1984},
}
@inproceedings{4119,
author = {Herbert Edelsbrunner and Welzl, Emo},
pages = {265 -- 272},
publisher = {Springer},
title = {{Monotone edge sequences in line arrangements and applications}},
doi = {10.1007/BFb0030307},
volume = {176},
year = {1984},
}
@article{4121,
abstract = {Whenevern objects are characterized by a matrix of pairwise dissimilarities, they may be clustered by any of a number of sequential, agglomerative, hierarchical, nonoverlapping (SAHN) clustering methods. These SAHN clustering methods are defined by a paradigmatic algorithm that usually requires 0(n 3) time, in the worst case, to cluster the objects. An improved algorithm (Anderberg 1973), while still requiring 0(n 3) worst-case time, can reasonably be expected to exhibit 0(n 2) expected behavior. By contrast, we describe a SAHN clustering algorithm that requires 0(n 2 logn) time in the worst case. When SAHN clustering methods exhibit reasonable space distortion properties, further improvements are possible. We adapt a SAHN clustering algorithm, based on the efficient construction of nearest neighbor chains, to obtain a reasonably general SAHN clustering algorithm that requires in the worst case 0(n 2) time and space.
Whenevern objects are characterized byk-tuples of real numbers, they may be clustered by any of a family of centroid SAHN clustering methods. These methods are based on a geometric model in which clusters are represented by points ink-dimensional real space and points being agglomerated are replaced by a single (centroid) point. For this model, we have solved a class of special packing problems involving point-symmetric convex objects and have exploited it to design an efficient centroid clustering algorithm. Specifically, we describe a centroid SAHN clustering algorithm that requires 0(n 2) time, in the worst case, for fixedk and for a family of dissimilarity measures including the Manhattan, Euclidean, Chebychev and all other Minkowski metrics.},
author = {Day,William H and Herbert Edelsbrunner},
journal = {Journal of Classification},
number = {1},
pages = {7 -- 24},
publisher = {Springer},
title = {{Efficient algorithms for agglomerative hierarchical clustering methods}},
doi = {10.1007/BF01890115},
volume = {1},
year = {1984},
}
@inproceedings{4122,
abstract = {Computational geometry, considered a subfield of computer science, is concerned with the computational aspects of geometric problems. The increasing activity in this rather young field made it split into several reasonably independent subareas. This paper presents several key-problems of the classical part of computational geometry which exhibit strong interrelations. A unified view of the problems is stressed, and the general ideas behind the methods that solve them are worked out.},
author = {Herbert Edelsbrunner},
pages = {1 -- 13},
publisher = {Springer},
title = {{Key-problems and key-methods in computational geometry}},
doi = {10.1007/3-540-12920-0_1},
volume = {166},
year = {1984},
}
@article{4123,
abstract = {Windowing a two-dimensional picture means to determine those line segments of the picture that are visible through an axis-parallel window. A study of some algorithmic problems involved in windowing a picture is offered. Some methods from computational geometry are exploited to store the picture in a computer such that (1) those line segments inside or partially inside of a window can be determined efficiently, and (2) the set of those line segments can be maintained efficiently while the window is moved parallel to a coordinate axis and/or it is enlarged or reduced.},
author = {Herbert Edelsbrunner and Overmars, Mark H and Seidel, Raimund},
journal = {Computer Vision, Graphics, and Image Processing},
number = {1},
pages = {92 -- 108},
publisher = {Academic Press},
title = {{Some methods of computational geometry applied to computer graphics}},
doi = {10.1016/0734-189X(84)90142-7},
volume = {28},
year = {1984},
}
@article{4125,
abstract = {Let S denote a set of n points in the plane such that each point p has assigned a positive weight w(p) which expresses its capability to influence its neighbourhood. In this sense, the weighted distance of an arbitrary point x from p is given by de(x,p)/w(p) where de denotes the Euclidean distance function. The weighted Voronoi diagram for S is a subdivision of the plane such that each point p in S is associated with a region consisting of all points x in the plane for which p is a weighted nearest point of S.
An algorithm which constructs the weighted Voronoi diagram for S in O(n2) time is outlined in this paper. The method is optimal as the diagram can consist of Θ(n2) faces, edges and vertices.},
author = {Aurenhammer,Franz and Herbert Edelsbrunner},
journal = {Pattern Recognition},
number = {2},
pages = {251 -- 257},
publisher = {Springer},
title = {{An optimal algorithm for constructing the weighted Voronoi diagram in the plane}},
doi = {10.1016/0031-3203(84)90064-5},
volume = {17},
year = {1984},
}
@article{4327,
author = {Nicholas Barton and Charlesworth, Brian},
journal = {Annual Review of Ecology and Systematics},
pages = {133 -- 164},
publisher = {Annual Reviews},
title = {{Genetic revolutions, founder effects, and speciation}},
doi = {10.1146/annurev.es.15.110184.001025},
volume = {15},
year = {1984},
}
@inproceedings{3513,
author = {Dobkin, David P and Herbert Edelsbrunner},
pages = {88 -- 99},
publisher = {Teubner},
title = {{Ham-sandwich theorems applied to intersection problems}},
year = {1984},
}
@inproceedings{4124,
author = {Herbert Edelsbrunner and Welzl, Emo},
pages = {182 -- 187},
publisher = {Springer},
title = {{On the number of equal-sized semispaces of a set of points in the plane}},
doi = {10.1007/BFb0036908},
volume = {154},
year = {1983},
}
@article{4126,
abstract = {Rectangle intersections involving rectilinearly-oriented (hyper-) rectangles in d-dimensional real space are examined from two points of view. First, a data structure is developed which is efficient in time and space and allows us to report all d-dimensional rectangles stored which intersect a d-dimensional query rectangle. Second, in Part II, a slightly modified version of this new data structure is applied to report all intersecting pairs of rectangles of a given set. This approach yields a solution which is optimal in time and space for planar rectangles and reasonable in higher dimensions.},
author = {Herbert Edelsbrunner},
journal = {International Journal of Computer Mathematics},
number = {3-4},
pages = {209 -- 219},
publisher = {Taylor & Francis},
title = {{A new approach to rectangle intersections part 1}},
doi = {10.1080/00207168308803364},
volume = {13},
year = {1983},
}
@article{4127,
abstract = {The study begun in Part I is completed by providing an algorithm which reports all intersecting pairs of a set of rectangles in d dimensions. This approach yields a solution which is optimal in time and space for planar rectangles and reasonable in higher dimensions.},
author = {Herbert Edelsbrunner},
journal = {International Journal of Computer Mathematics},
number = {3-4},
pages = {221 -- 229},
publisher = {Taylor & Francis},
title = {{A new approach to rectangle intersections part 2}},
doi = {10.1080/00207168308803365},
volume = {13},
year = {1983},
}
@article{4128,
abstract = {A generalization of the convex hull of a finite set of points in the plane is introduced and analyzed. This generalization leads to a family of straight-line graphs, "alpha-shapes," which seem to capture the intuitive notions of "fine shape" and "crude shape" of point sets. It is shown that a-shapes are subgraphs of the closest point or furthest point Delaunay triangulation. Relying on this result an optimalO(n log n)algorithm that constructsalpha-shapes is developed.},
author = {Herbert Edelsbrunner and Kirkpatrick, David G and Seidel, Raimund},
journal = {IEEE Transactions on Information Theory},
number = {4},
pages = {551 -- 559},
publisher = {IEEE},
title = {{On the shape of a set of points in the plane}},
doi = {10.1109/TIT.1983.1056714 },
volume = {29},
year = {1983},
}
@inbook{4328,
abstract = {The hybrid zone which forms when two partially incompatible populations meet acts as a barrier to gene flow. We discuss electrophoretic and theoretical evidence on the strength of such barriers. Hybrid zones generally involve considerable electrophoretic divergence. The enzyme clines are consistent in position and width; in some cases, they show consistently asymmetric patterns of introgression. This consistency suggests that the clines are maintained primarily by the indirect effects of selection at linked loci, rather than by the effect of each individual locus on fitness. A cline at a single locus will present some barrier, regardless of the selective mechanism which maintains it. However, unless the locus induces virtually complete assortment or hybrid unfitness, the barrier will be weak. Spreading the same selection over more clines gives a stronger barrier. If the clines are staggered, this barrier is still unlikely to be significant; if they coincide, and if selection is stronger than recombination, then the barrier will be very strong; its strength and asymmetry will be consistent over different loci. Thus, the taxonomic status of divergent populations cannot be inferred just from the total amount of pre- or post-mating isolation; the number of genetic differences, and the interactions between them are equally important in determining rates of gene flow.},
author = {Nicholas Barton and Hewitt, Godfrey M},
booktitle = {Protein polymorphism: adaptive and taxonomic significance},
editor = {Oxford,Geoffrey S and Rollinson,David},
pages = {341 -- 359},
publisher = {Academic Press},
title = {{Hybrid zones as barriers to gene flow}},
doi = {3690},
volume = {24},
year = {1983},
}
@misc{4329,
author = {Nicholas Barton},
booktitle = {Animal Behaviour},
number = {2},
pages = {626 -- 627},
publisher = {Elsevier},
title = {{The extended phenotype: the gene as the unit of selection (review of Dawkins R 1982)}},
doi = {10.1016/S0003-3472(83)80100-6},
volume = {31},
year = {1983},
}
@misc{4330,
author = {Nicholas Barton},
booktitle = {Heredity},
pages = {213 -- 213},
publisher = {Nature Publishing Group},
title = {{Gene flow and speciation (abstract)}},
doi = {10.1038/hdy.1983.24},
volume = {50},
year = {1983},
}
@inbook{3562,
author = {Bucher, W. and Herbert Edelsbrunner},
booktitle = {Computational Geometry: Theory and Applications},
editor = {Preparata, Franco P},
pages = {109 -- 125},
publisher = {Elsevier},
title = {{On expected- and worst-case segment trees}},
volume = {1},
year = {1983},
}
@inbook{3563,
author = {Herbert Edelsbrunner and Overmars, Mark H and Wood, Derick},
booktitle = {Computational Geometry: Theory and Applications},
editor = {Preparata, Franco P},
pages = {35 -- 59},
publisher = {Elsevier},
title = {{Graphics in Flatland: a case study}},
volume = {1},
year = {1983},
}
@inbook{3564,
author = {Herbert Edelsbrunner},
booktitle = {Überblicke Informationsverarbeitung },
editor = {Maurer, Hermann A},
pages = {55 -- 109},
publisher = {BI Wissenschaftsverlag},
title = {{Neue Entwicklungen im Bereich Datenstrukturen}},
year = {1983},
}
@misc{3598,
author = {Nicholas Barton and Jones, Steve},
booktitle = {Nature},
pages = {317 -- 318},
publisher = {Nature Publishing Group},
title = {{Mitochondrial DNA: new clues about evolution}},
doi = {10.1038/306317a0},
volume = {306},
year = {1983},
}
@article{3666,
abstract = {We have made an extensive allozyme survey of 21 enzyme and protein loci in populations of the alpine grasshopper Podisma pedestris. This species occurs in two races, differing by a chromosomal fusion which separates the ancestral XO/XX race from a derived neo-XY race. These races also differ in DNA content, and hybrids between them have reduced viability. Electrophoresis reveals that the amount of genetic differentiation between these races is no greater than the variation among populations within each race. Both larger-scale surveys and a detailed survey of an area where the races hybridize, show that the chromosomal change is not correlated with gene frequency changes at any of the 21 loci studied. These findings are consistent with recently developed theory concerning the strength of the barrier to gene flow posed by a hybrid zone with characteristics such as those measured experimentally in Podisma. It is argued that hybrid zones in other species which involve allozymic differences do so because of stronger selection against hybrids rather than through mating isolation.},
author = {Halliday, Bruce and Nicholas Barton and Hewitt, Godfrey M},
journal = {Biological Journal of the Linnean Society},
number = {1},
pages = {51 -- 62},
publisher = {Wiley-Blackwell},
title = {{Electrophoretic analysis of a chromosomal hybrid zone in the grasshopper Podisma pedestris}},
doi = {10.1111/j.1095-8312.1983.tb00776.x},
volume = {19},
year = {1983},
}
@article{3667,
abstract = {Populations of the grasshopper Podisma pedestris were collected from two ends of a zone of hybridization between two chromosome races, at Seyne and Tende in southern France. 21 enzyme and protein loci were detected by gel electrophoresis. Six of these loci showed widespread polymorphism, and a further eleven had very little or no variation. Two loci (Idh, 6Pgd) had rare alleles in different frequencies in the two areas surveyed. The remaining two loci (Mdh-1, Mdh-2) showed a marked increase in the frequency of rare variants, from 1 per cent outside the hybrid zone, up to 5 per cent at its centre. This region of increased electrophoretic variation coincided with the chromosomal cline between the two races, and with a region of decreased viability. It was spread over about the same width as the chromosomal cline. Possible explanations for this extra variation include intragenic recombination and elevated mutation rates.},
author = {Nicholas Barton and Halliday, Bruce and Hewitt, Godfrey M},
journal = {Heredity},
number = {2},
pages = {139 -- 146},
publisher = {Nature Publishing Group},
title = {{Rare electrophoretic variants in a hybrid zone}},
doi = {10.1038/hdy.1983.15},
volume = {50},
year = {1983},
}
@article{3668,
author = {Nicholas Barton},
journal = {Evolution; International Journal of Organic Evolution},
number = {3},
pages = {454 -- 471},
publisher = {Wiley-Blackwell},
title = {{Multilocus clines}},
volume = {37},
year = {1983},
}
@article{4129,
abstract = {An algorithm for the geometric problem of determining a line (called a stabbing line) which intersects each ofn given line segments in the plane is presented. As a matter of fact, the algorithm computes a description of all stabbing lines. A purely geometric fact is proved which infers that this description requiresO(n) space to be specified. Our algorithm computes it inO(n logn) time which is optimal in the worst case.
Using the description of the stabbing lines, we are able to decide inO(logn) time whether or not a specified line is a stabbing line. Finally, the problem of maintaining the description of all stabbing lines while inserting and deleting line segments is addressed.},
author = {Herbert Edelsbrunner and Maurer, Hermann A and Preparata, Franco P and Rosenberg, Arnold L and Welzl, Emo and Wood, Derick},
journal = {Bit},
number = {3},
pages = {274 -- 281},
publisher = {Springer},
title = {{Stabbing line segments}},
doi = {10.1007/BF01934440},
volume = {22},
year = {1982},
}
@article{4130,
author = {Herbert Edelsbrunner and Maurer, Hermann A and Kirkpatrick, David G},
journal = {Information Processing Letters},
number = {2},
pages = {74 -- 79},
publisher = {Elsevier},
title = {{Polygonal intersection searching}},
doi = {10.1016/0020-0190(82)90090-4},
volume = {14},
year = {1982},
}
@article{4131,
author = {Herbert Edelsbrunner and Overmars, Mark H},
journal = {Information Processing Letters},
number = {3},
pages = {124 -- 127},
publisher = {Elsevier},
title = {{On the equivalence of some rectangle problems}},
doi = {10.1016/0020-0190(82)90068-0},
volume = {14},
year = {1982},
}
@article{4331,
author = {Nicholas Barton},
journal = {Evolution; International Journal of Organic Evolution},
number = {4},
pages = {863 -- 866},
publisher = {Wiley-Blackwell},
title = {{The structure of the hybrid zone in Uroderma bilobatum (Chiroptera: Phyllostomatidae)}},
volume = {36},
year = {1982},
}
@article{3669,
abstract = {The dispersal rate of the grasshopper Podisma pedestris has been measured, with the aim of interpreting the width of a chromosomal cline. 171 adults were marked individually, and released within the cline. 169 movements were seen over three subsequent scorings; the distribution of distances, after correction for the loss of long distance dispersants, was close to a normal curve, but there was an initial shift of ten metres, perhaps towards a better habitat. The linear variance increased at about 214 m2 day- 1, which corresponds to a standard deviation of 207 m gen- 1/2 over a 20 day life span. Statistical uncertainty in this estimate can be expressed using a distribution-free maximum likelihood method, which gives support limits of 186- 270 m gen- 1/2. However, the main errors come from extrapolating from this experiment to the cline as a whole.},
author = {Nicholas Barton and Hewitt, Godfrey M},
journal = {Heredity},
number = {2},
pages = {237 -- 249},
publisher = {Nature Publishing Group},
title = {{A measurement of dispersal in the grasshopper Podisma pedestris (Orthoptera: Acrididae)}},
doi = {10.1038/hdy.1982.29},
volume = {48},
year = {1982},
}
@article{4132,
author = {Herbert Edelsbrunner and Maurer, Hermann A},
journal = {Information Processing Letters},
number = {4-5},
pages = {177 -- 181},
publisher = {Elsevier},
title = {{On the intersection of Orthogonal objects}},
doi = {10.1016/0020-0190(81)90053-3},
volume = {13},
year = {1981},
}
@article{4133,
abstract = {In 1979 Kirpatrick obtained a practically feasible algorithm for planar regionlocation working in linear space and logarithmic time, provided the regions are bounded by straight line segments. No algorithm requiring only linear space and log-polynomial time was known, so far, for general planar regionlocation, i.e. for the case where regions are bounded by curves more complicated than straight line segments. As main result of this paper such an algorithm is presented.},
author = {Herbert Edelsbrunner and Maurer, Hermann A},
journal = {Theoretical Computer Science},
number = {3},
pages = {329 -- 336},
publisher = {Elsevier},
title = {{A space-optimal solution of general region location}},
doi = {10.1016/0304-3975(81)90103-1},
volume = {16},
year = {1981},
}
@inbook{4332,
author = {Nicholas Barton and Hewitt, Godfrey M},
booktitle = {Evolution and Speciation},
editor = {Atchley,William R and Woodruff, David S},
pages = {109 -- 145},
publisher = {Cambridge University Press},
title = {{Hybrid zones and speciation}},
year = {1981},
}
@article{4333,
abstract = {Samples were taken from five sites in a transect across the hybrid zone between two chromosomal races of the grasshopper Podisma pedestris. Crosses were set up between insects from the same population, and between populations spanning the zone, and the early viability of the offspring was measured. Hybrids between pure populations had reduced viability, and the viability of insects from the middle of the zone was still lower, showing that most (87 per cent) of the inviability was due to the breakup of coadapated gene complexes. Although the total selection acting was strong (log. fitness reduced by S25), it was spread over a region wider than the dispersal range (350 m vs. 20 m). Hence, the selection on each locus contributing towards the inviability is weak (3 per cent). Many (150) independent chromosome segments act cumulatively to produce inviability at this stage in the life history. The implications of these findings for models of divergence are discussed.},
author = {Nicholas Barton and Hewitt, Godfrey M},
journal = {Heredity},
pages = {367 -- 383},
publisher = {Nature Publishing Group},
title = {{The genetic basis of hybrid inviability between two chromosomal races of the grasshopper Podisma pedestris}},
doi = {10.1038/hdy.1981.98},
volume = {47},
year = {1981},
}
@article{3670,
abstract = {The grasshopper Podisma pedestris includes two chromosomal races, which differ by a Robertsonian fusion involving the sex chromosome. The two races meet in a cline which runs for 100 km across the Alpes Maritimes in south-eastern France. An intensive study of the easternmost end of this cline shows that it is about 800 m wide; the cline is not smooth, containing substantial spikes in chromosome frequency which might be due to sampling drift. Though the cline seems narrow, it is wide compared with the dispersal rate of the insect; a selective force of only 0.5% would be enough to maintain the cline. It is difficult to determine the nature of this force, but some evidence comes from the position of the cline, and from the presence of coincident clines at other loci. An estimate of the distribution of Podisma has been made, and the cline seems to follow, for the most part, a region of low population density, suggesting that it is maintained by hybrid unfitness. However, in the one region where the cline is relatively free to move, the XY race bulges forwards more than would be expected if hybrids are unfit. The observation of severe inviability in crosses between the races, though it is not associated with the chromosomal difference, also indicates that this cline is the result of some sort of genetic incompatibility.},
author = {Nicholas Barton and Hewitt, Godfrey M},
journal = {Evolution; International Journal of Organic Evolution},
number = {5},
pages = {1008 -- 1018},
publisher = {Wiley-Blackwell},
title = {{A chromosomal cline in the grasshopper Podisma pedestris}},
volume = {35},
year = {1981},
}
@article{3671,
author = {Nicholas Barton},
journal = {Heredity},
pages = {279 -- 282},
publisher = {Nature Publishing Group},
title = {{The width of the hybrid zone in Caledia captiva}},
doi = {10.1038/hdy.1981.86},
volume = {47},
year = {1981},
}