@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 = {Edelsbrunner, Herbert and Welzl, Emo}, issn = {1096-0899}, 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{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 = {Edelsbrunner, Herbert}, issn = {0304-3975}, 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 Edelsbrunner, Herbert}, issn = {1095-855X}, 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{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 = {Barton, Nicholas H and Halliday, Bruce and Hewitt, Godfrey}, issn = {1365-2540}, 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}, } @misc{4330, author = {Barton, Nicholas H}, booktitle = {Heredity}, issn = {1365-2540}, pages = {213 -- 213}, publisher = {Springer Nature}, title = {{Gene flow and speciation (abstract)}}, doi = {10.1038/hdy.1983.24}, volume = {50}, year = {1983}, } @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 = {Barton, Nicholas H and Hewitt, Godfrey}, issn = {1365-2540}, journal = {Heredity}, number = {2}, pages = {237 -- 249}, publisher = {Springer Nature}, title = {{A measurement of dispersal in the grasshopper Podisma pedestris (Orthoptera: Acrididae)}}, doi = {10.1038/hdy.1982.29}, volume = {48}, year = {1982}, } @article{3671, author = {Barton, Nicholas H}, issn = {1365-2540}, 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}, } @article{4132, author = {Edelsbrunner, Herbert and Maurer, Hermann}, issn = {0020-0190}, 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 = {Edelsbrunner, Herbert and Maurer, Hermann}, issn = {0304-3975}, 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}, } @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 = {Barton, Nicholas H and Hewitt, Godfrey}, issn = {1365-2540}, journal = {Heredity}, number = {3}, pages = {367 -- 383}, publisher = {Springer Nature}, 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{3672, author = {Barton, Nicholas H}, issn = {1365-2540}, journal = {Heredity}, pages = {277 -- 278}, publisher = {Springer Nature}, title = {{The hybrid sink effect}}, doi = {10.1038/hdy.1980.23}, volume = {44}, year = {1980}, } @article{4335, abstract = {Genetic incompatibilities between two races of the grasshopper Podisma pedestris, which differ by a Robertsonian fusion involving the sex chromosome, have been investigated. Crosses were made between four populations spanning the chromosomal cline; F1 hybrids between the races, though not between separated populations of the same race, showed markedly reduced hatching success. Observations of the fate of chromosomes transplanted across the cline supported this finding. Crosses between grasshoppers from a mixed population in the cline showed a lower average hatching success, but no correlation of this inviability with the chromosomal polymorphism. The karyotypes of pre-diapause embryos from both types of cross gave no evidence for non-disjunction of the sex chromosome trivalent in heterozygous females; an upper limit of 16 per cent can be set on the non-disjunction rate. These findings suggest that the karyotypic difference is only a weakly selected marker for more fundamental changes in genotype.}, author = {Barton, Nicholas H}, issn = {1365-2540}, journal = {Heredity}, pages = {47 -- 59}, publisher = {Springer Nature}, title = {{The fitness of hybrids between two chromosomal races of the grasshopper Podisma pedestris}}, doi = {10.1038/hdy.1980.49}, volume = {45}, year = {1980}, } @article{3673, abstract = {The effect of a cline as a barrier to gene flow at closely linked, weakly selected loci is investigated using a continuous diffusion model. It is shown that a linked cline induces a step in the frequency of a neutral allele, which is proportional to the gradient in neutral allele frequency and to the inverse of the recombination rate. A barrier to dispersal or a local region of low abundance has a similar effect (Nagylaki, 1976). The cline will block the flow of neutral alleles over a region of chromosome roughly 2s/t map units long. However, a slightly advantageous allele will be little affected, and must be very tightly linked to be delayed for long.}, author = {Barton, Nicholas H}, issn = {1365-2540}, journal = {Heredity}, number = {3}, pages = {333 -- 339}, publisher = {Springer Nature}, title = {{Gene flow past a cline}}, doi = {10.1038/hdy.1979.86}, volume = {43}, year = {1979}, } @article{4336, abstract = {This paper investigates the dynamic behaviour of hybrid zones which are maintained by a balance between dispersal and selection against hybrids. In the first section it is shown that a hybrid zone involving a single locus can move in response to a selective imbalance between the two homozygotes, and also to variation in population density and dispersal rate. It can be trapped by natural barriers, and so an allele which is selected against when rare cannot advance, even if it is advantageous when common. The continuous model used in deriving these results is shown to be a good approximation to the stepping-stone model, provided that the cline contains several demes. The effect of stochastic forces on multi-locus hybrid zones is then considered. An expression giving the shift in position after an arbitrary perturbation in gamete frequency is derived. Using this formula, it is found that sampling drift is negligible unless the zone includes few organisms and involves few loci. Random variations in population structure are the dominant force, and could allow considerable movement in an even environment. However, natural barriers can still trap hybrid zones, and so it is likely that they will remain roughly where they first formed.}, author = {Barton, Nicholas H}, issn = {1365-2540}, journal = {Heredity}, number = {3}, pages = {341 -- 359}, publisher = {Springer Nature}, title = {{The dynamics of hybrid zones}}, doi = {10.1038/hdy.1979.87}, volume = {43}, year = {1979}, }