@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 = {Edelsbrunner, Herbert}, issn = {1029-0265}, 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 = {Edelsbrunner, Herbert}, issn = {1029-0265}, 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 optimal O(n \log n) algorithm that constructs \alpha -shapes is developed.}, author = {Edelsbrunner, Herbert and Kirkpatrick, David and Seidel, Raimund}, issn = {1558-0814}, 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 = {Barton, Nicholas H and Hewitt, Godfrey}, booktitle = {Protein polymorphism: Adaptive and taxonomic significance}, editor = {Oxford, Geoffrey and Rollinson, David}, isbn = {978-0-1253-1780-1}, issn = {0309-2593}, keywords = {chemotaxonomy}, location = {University of York, United Kingdom}, pages = {341 -- 359}, publisher = {Academic Press}, title = {{Hybrid zones as barriers to gene flow}}, volume = {24}, year = {1983}, } @misc{4329, author = {Barton, Nicholas H}, booktitle = {Animal Behaviour}, issn = {1095-8282}, 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 = {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{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 = {Edelsbrunner, Herbert and Maurer, Hermann and Preparata, Franco and Rosenberg, Arnold and Welzl, Emo and Wood, Derick}, issn = {1572-9125}, journal = {BIT Numerical Mathematics}, number = {3}, pages = {274 -- 281}, publisher = {Springer Nature}, title = {{Stabbing line segments}}, doi = {10.1007/BF01934440}, volume = {22}, year = {1982}, } @article{4130, author = {Edelsbrunner, Herbert and Maurer, Hermann and Kirkpatrick, David}, issn = {1872-6119}, 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 = {Edelsbrunner, Herbert and Overmars, Mark}, issn = {1872-6119}, 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 = {Barton, Nicholas H}, issn = {1558-5646}, journal = {Evolution}, number = {4}, pages = {863 -- 866}, publisher = {Wiley}, title = {{The structure of the hybrid zone in Uroderma bilobatum (Chiroptera: Phyllostomatidae)}}, doi = {10.1111/j.1558-5646.1982.tb05452.x}, volume = {36}, year = {1982}, } @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 = {Barton, Nicholas H and Hewitt, Godfrey}, issn = {1558-5646}, journal = {Evolution; International Journal of Organic Evolution}, number = {5}, pages = {1008 -- 1018}, publisher = {Wiley-Blackwell}, title = {{A chromosomal cline in the grasshopper Podisma pedestris}}, doi = { 10.1111/j.1558-5646.1981.tb04966.x}, volume = {35}, year = {1981}, } @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}, } @inbook{4332, author = {Barton, Nicholas H and Hewitt, Godfrey}, booktitle = {Evolution and Speciation}, editor = {Atchley, William and Woodruff, David}, isbn = {9-780-5212-3823-6}, 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 = {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}, } @inbook{4334, author = {Hewitt, Godfrey and Barton, Nicholas H}, booktitle = {Insect Cytogenetics}, editor = {Blackman, Roger and Ashburner, Michael}, isbn = {9-780-6320-0552-9}, pages = {149 -- 170}, publisher = {Wiley-Blackwell}, title = {{The structure and maintenance of hybrid zones as exemplified by Podisma pedestris}}, volume = {10}, 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}, }