@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{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{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{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{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},
}
@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},
}
@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{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{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{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{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},
}
@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{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{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{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{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},
}
@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{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{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{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{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{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{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{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{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},
}
@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{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{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{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{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{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{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{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{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{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{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{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{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{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},
}
@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{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{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{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{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},
}
@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},
}
@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},
}
@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},
}
@inproceedings{3513,
author = {Dobkin, David P and Herbert Edelsbrunner},
pages = {88 -- 99},
publisher = {Teubner},
title = {{Ham-sandwich theorems applied to intersection problems}},
year = {1984},
}
@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},
}