@article{4086, abstract = {This note proves that the maximum number of faces (of any dimension) of the upper envelope of a set ofn possibly intersectingd-simplices ind+1 dimensions is (n d (n)). This is an extension of a result of Pach and Sharir [PS] who prove the same bound for the number ofd-dimensional faces of the upper envelope.}, author = {Edelsbrunner, Herbert}, issn = {1432-0444}, journal = {Discrete & Computational Geometry}, number = {4}, pages = {337 -- 343}, publisher = {Springer}, title = {{The upper envelope of piecewise linear functions: Tight bounds on the number of faces }}, doi = {10.1007/BF02187734}, volume = {4}, year = {1989}, } @article{4088, abstract = {Anarrangement ofn lines (or line segments) in the plane is the partition of the plane defined by these objects. Such an arrangement consists ofO(n 2) regions, calledfaces. In this paper we study the problem of calculating and storing arrangementsimplicitly, using subquadratic space and preprocessing, so that, given any query pointp, we can calculate efficiently the face containingp. First, we consider the case of lines and show that with (n) space1 and (n 3/2) preprocessing time, we can answer face queries in (n)+O(K) time, whereK is the output size. (The query time is achieved with high probability.) In the process, we solve three interesting subproblems: (1) given a set ofn points, find a straight-edge spanning tree of these points such that any line intersects only a few edges of the tree, (2) given a simple polygonal path , form a data structure from which we can find the convex hull of any subpath of quickly, and (3) given a set of points, organize them so that the convex hull of their subset lying above a query line can be found quickly. Second, using random sampling, we give a tradeoff between increasing space and decreasing query time. Third, we extend our structure to report faces in an arrangement of line segments in (n 1/3)+O(K) time, given(n 4/3) space and (n 5/3) preprocessing time. Lastly, we note that our techniques allow us to computem faces in an arrangement ofn lines in time (m 2/3 n 2/3+n), which is nearly optimal.}, author = {Edelsbrunner, Herbert and Guibas, Leonidas and Hershberger, John and Seidel, Raimund and Sharir, Micha and Snoeyink, Jack and Welzl, Emo}, issn = {1432-0444}, journal = {Discrete & Computational Geometry}, number = {1}, pages = {433 -- 466}, publisher = {Springer}, title = {{Implicitly representing arrangements of lines or segments}}, doi = {10.1007/BF02187742}, volume = {4}, year = {1989}, } @article{4089, abstract = {Motivated by a number of motion-planning questions, we investigate in this paper some general topological and combinatorial properties of the boundary of the union ofn regions bounded by Jordan curves in the plane. We show that, under some fairly weak conditions, a simply connected surface can be constructed that exactly covers this union and whose boundary has combinatorial complexity that is nearly linear, even though the covered region can have quadratic complexity. In the case where our regions are delimited by Jordan acrs in the upper halfplane starting and ending on thex-axis such that any pair of arcs intersect in at most three points, we prove that the total number of subarcs that appear on the boundary of the union is only (n(n)), where(n) is the extremely slowly growing functional inverse of Ackermann's function.}, author = {Edelsbrunner, Herbert and Guibas, Leonidas and Hershberger, John and Pach, János and Pollack, Richard and Seidel, Raimund and Sharir, Micha and Snoeyink, Jack}, issn = {1432-0444}, journal = {Discrete & Computational Geometry}, number = {1}, pages = {523 -- 539}, publisher = {Springer}, title = {{On arrangements of Jordan arcs with three intersections per pair}}, doi = {10.1007/BF02187745}, volume = {4}, year = {1989}, } @article{3655, abstract = {The structural basis and distribution of variation in the ribosomal RNA multigene family ( rDNA) was studied in the X0 and neo-XY races of the Alpine grasshopper Podisma pedestris. Restriction-enzyme sites in the gene region of the rDNA repeat were identical in both races and homogeneous in the rDNA family. In contrast, sites for Hind111 and PvuII in the intergenic spacer (IGS) region showed racial divergence and variation within the rDNA family and within populations. A short insertion in the 28s gene region was present in a minority of repeats in both races. The distributions of four polymorphic IGS Hind111 fragments were surveyed at 43 locations in and around the hybrid zone. Two of these fragments appear to be distributed as clines, one of which is strongly associated with the neo-X chromosome. The other two fragments show considerable variation in both races and show negative association. It is proposed that the clinally distributed variants arise from processes of amplification and divergence of IGS sequence variants and that such divergence may contribute to hybrid inviability. }, author = {Dallas, John and Barton, Nicholas H and Dover, Gabriel}, issn = {1537-1719}, journal = {Molecular Biology and Evolution}, number = {6}, pages = {660 -- 674}, publisher = {Oxford University Press}, title = {{Interracial rDNA variation in the grasshopper Podisma Pedestris}}, doi = {10.1093/oxfordjournals.molbev.a040528}, volume = {5}, 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 = {Edelsbrunner, Herbert and Preparata, Franco}, issn = {0890-5401}, 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{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 and Nichols, R. and Barton, Nicholas H}, issn = {1365-2540}, 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{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 Barton, Nicholas H and Hewitt, Godfrey}, issn = {1365-2540}, 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{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 = {Barton, Nicholas H and Slatkin, Montgomery}, issn = {1365-2540}, 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, abstract = {Suppose that selection acts at one or more loci to maintain genetic differences between hybridising populations. Then, the flow of alleles at a neutral marker locus which is linked to these selected loci will be impeded. We define and calculate measures of the barrier to gene flow between two distinct demes, and across a continuous habitat. In both cases, we find that in order for gene flow to be significantly reduced over much of the genome, hybrids must be substantially less fit, and the number of genes involved in building the barrier must be so large that the majority of other genes become closely linked to some locus which is under selection. This conclusion is not greatly affected by the pattern of epistasis, or the position of the marker locus along the chromosome.}, author = {Barton, Nicholas H and Bengtsson, Bengt}, issn = {1365-2540}, journal = {Heredity}, pages = {357 -- 376}, publisher = {Nature Publishing Group}, title = {{The barrier to genetic exchange between hybridising populations}}, volume = {57}, year = {1986}, } @article{3665, abstract = {The rate of gene flow across a hybrid zone may be reduced by the presence of a physical barrier, by a reduction of population density caused by reduced fitness of hybrids (the “hybrid sink” effect), and by linkage. If the reduction in hybrid fitness is not extreme, the strength of the barrier to gene flow caused by these effects is. Here, w is the width of the cline; ρ* is the carrying capacity; W̄* is the mean fitness of the population, excluding effects of density; R is the strength of density-dependent regulation; and r̄ is the harmonic mean recombination rate between the locus whose flow is being calculated, and loci under selection. +, 0 denote populations outside the hybrid zone, and at its centre, respectively. This relation is illustrated using data from hybrid ones in Bombina and Podisma, and its implications for interpretation of data from nature are discussed.}, author = {Barton, Nicholas H}, issn = {1365-2540}, 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 = {Edelsbrunner, Herbert and Stöckl, Gerd}, issn = {1096-0899}, 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{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}, }