TY - CONF
AB - This paper offers combinatorial results on extremum problems concerning the number of tetrahedra in a tetrahedrization of n points in general position in three dimensions, i.e. such that no four points are coplanar. It also presents an algorithm that in O(nlog n) time constructs a tetrahedrization of a set of n points consisting of at most 3n–11 tetrahedra.
AU - Herbert Edelsbrunner
AU - Preparata, Franco P
AU - West, Douglas B
ID - 4087
TI - Tetrahedrizing point sets in three dimensions
VL - 358
ER -
TY - JOUR
AB - 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.
AU - Herbert Edelsbrunner
AU - Guibas, Leonidas
AU - Hershberger, John
AU - Seidel, Raimund
AU - Sharir, Micha
AU - Snoeyink, Jack
AU - Welzl, Emo
ID - 4088
IS - 1
JF - Discrete & Computational Geometry
TI - Implicitly representing arrangements of lines or segments
VL - 4
ER -
TY - JOUR
AB - 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.
AU - Herbert Edelsbrunner
AU - Guibas, Leonidas
AU - Hershberger, John
AU - Pach, János
AU - Pollack, Richard
AU - Seidel, Raimund
AU - Sharir, Micha
AU - Snoeyink, Jack
ID - 4089
IS - 1
JF - Discrete & Computational Geometry
TI - On arrangements of Jordan arcs with three intersections per pair
VL - 4
ER -
TY - CONF
AU - Chazelle, Bernard
AU - Herbert Edelsbrunner
AU - Guibas, Leonidas J
AU - Sharir, Micha
ID - 4092
TI - A singly exponential stratification scheme for real semi-algebraic varieties and its applications
VL - 372
ER -
TY - JOUR
AB - This paper investigates the combinatorial and computational aspects of certain extremal geometric problems in two and three dimensions. Specifically, we examine the problem of intersecting a convex subdivision with a line in order to maximize the number of intersections. A similar problem is to maximize the number of intersected facets in a cross-section of a three-dimensional convex polytope. Related problems concern maximum chains in certain families of posets defined over the regions of a convex subdivision. In most cases we are able to prove sharp bounds on the asymptotic behavior of the corresponding extremal functions. We also describe polynomial algorithms for all the problems discussed.
AU - Chazelle, Bernard
AU - Herbert Edelsbrunner
AU - Guibas, Leonidas J
ID - 4093
IS - 1
JF - Discrete & Computational Geometry
TI - The complexity of cutting complexes
VL - 4
ER -
TY - JOUR
AB - Three methods for estimating the average level of gene flow in natural population are discussed and compared. The three methods are FST, rare alleles, and maximum likelihood. All three methods yield estimates of the combination of parameters (the number of migrants [Nm] in a demic model or the neighborhood size [4πDσ2] in a continuum model) that determines the relative importance of gene flow and genetic drift. We review the theory underlying these methods and derive new analytic results for the expectation of FST in stepping-stone and continuum models when small sets of samples are taken. We also compare the effectiveness of the different methods using a variety of simulated data. We found that the FST and rare-alleles methods yield comparable estimates under a wide variety of conditions when the population being sampled is demographically stable. They are roughly equally sensitive to selection and to variation in population structure, and they approach their equilibrium values at approximately the same rate. We found that two different maximum-likelihood methods tend to yield biased estimates when relatively small numbers of locations are sampled but more accurate estimates when larger numbers are sampled. Our conclusion is that, although FST and rare-alleles methods are expected to be equally effective in analyzing ideal data, practical problems in estimating the frequencies of rare alleles in electrophoretic studies suggest that FST is likely to be more useful under realistic conditions.
AU - Slatkin, Montgomery
AU - Nicholas Barton
ID - 4309
IS - 7
JF - Evolution; International Journal of Organic Evolution
TI - A comparison of three methods for estimating average levels of gene flow
VL - 43
ER -
TY - JOUR
AU - Nicholas Barton
AU - Turelli, Michael
ID - 4312
JF - Annual Review of Genetics
TI - Evolutionary quantitative genetics: how little do we know ?
VL - 23
ER -
TY - CHAP
AU - Nicholas Barton
ED - Otte, Daniel
ED - Endler, John A
ID - 4313
T2 - Speciation and its consequences
TI - Founder effect speciation
ER -
TY - JOUR
AB - Polygenic variation can be maintained by a balance between mutation and stabilizing selection. When the alleles responsible for variation are rare, many classes of equilibria may be stable. The rate at which drift causes shifts between equilibria is investigated by integrating the gene frequency distribution W2N II (pq)4N mu-1. This integral can be found exactly, by numerical integration, or can be approximated by assuming that the full distribution of allele frequencies is approximately Gaussian. These methods are checked against simulations. Over a wide range of population sizes, drift will keep the population near an equilibrium which minimizes the genetic variance and the deviation from the selective optimum. Shifts between equilibria in this class occur at an appreciable rate if the product of population size and selection on each locus is small (Ns alpha 2 less than 10). The Gaussian approximation is accurate even when the underlying distribution is strongly skewed. Reproductive isolation evolves as populations shift to new combinations of alleles: however, this process is slow, approaching the neutral rate (approximately mu) in small populations.
AU - Nicholas Barton
ID - 4314
IS - 1
JF - Genetical Research
TI - The divergence of a polygenic system under stabilising selection, mutation and drift
VL - 54
ER -
TY - CONF
AB - A real-time temporal logic for the specification of reactive systems is introduced. The novel feature of the logic, TPTL, is the adoption of temporal operators as quantifiers over time variables; every modality binds a variable to the time(s) it refers to. TPTL is demonstrated to be both a natural specification language and a suitable formalism for verification and synthesis. A tableau-based decision procedure and model-checking algorithm for TPTL are presented. Several generalizations of TPTL are shown to be highly undecidable.
AU - Alur, Rajeev
AU - Thomas Henzinger
ID - 4596
TI - A really temporal logic
ER -
TY - JOUR
AB - Asymmetrical displacement currents and Na currents of single myelinated nerve fibers of Xenopus laevis were studied in the temperature range from 5 to 24 degrees C. The time constant of the on-response at E = 4 mV, tau on, was strongly temperature dependent, whereas the amount of displaced charge at E = 39 mV, Qon, was only slightly temperature dependent. The mean Q10 for tau on-1 was 2.54, the mean Q10 for Qon was 1.07. The time constant of charge immobilization, tau i, at E = 4 mV varied significantly (alpha = 0.001) with temperature. The mean Q10 for tau i-1 was 2.71 +/- 0.38. The time constants of immobilization of gating charge and of fast inactivation of Na permeability were similar in the temperature range from 6 to 22 degrees C. The Qoff/Qon ratio for E = 4 mV pulses of 0.5 msec duration decreased with increasing temperature. The temperature dependence of the time constant of the off-response could not be described by a single Q10 value, since the Q10 depended on the duration of the test pulse. Increasing temperature shifted Qon (E) curves to more negative potentials by 0.51 mV K-1, but shifted PNa (E) curves and h infinity (E) curves to more positive potentials by 0.43 and 0.57 mV K-1, respectively. h infinity (E = -70 mV) increased monotonously with increasing temperature. The present data indicate that considerable entropy changes may occur when the Na channel molecule passes from closed through open to inactivated states.
AU - Peter Jonas
ID - 3465
IS - 3
JF - Journal of Membrane Biology
TI - Temperature dependence of gating current in myelinated nerve fibers
VL - 112
ER -
TY - JOUR
AB - 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.
AU - Peter Jonas
AU - Bräu, Michael E
AU - Hermsteiner, Markus
AU - Vogel, Werner
ID - 3466
IS - 18
JF - PNAS
TI - Single-channel recording in myelinated nerve fibers reveals one type of Na channel but different K channels
VL - 86
ER -
TY - CONF
AU - Herbert Edelsbrunner
ID - 3549
TI - Spatial triangulations with dihedral angle conditions
ER -
TY - JOUR
AB - 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.
AU - Mallet, James L
AU - Nicholas Barton
ID - 3652
IS - 4
JF - Genetics
TI - Inference from clines stabilized by frequency-dependent selection
VL - 122
ER -
TY - JOUR
AB - 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.
AU - Mallet, James L
AU - Nicholas Barton
ID - 3653
JF - Evolution
TI - Strong natural selection in a warning color hybrid zone
VL - 43
ER -
TY - JOUR
AB - 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.
AU - Nicholas Barton
AU - Hewitt, Godfrey M
ID - 3654
JF - Nature
TI - Adaptation, speciation and hybrid zones
VL - 341
ER -
TY - JOUR
AB - 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.
AU - Ino, Tadashi
AU - Itoh, Kazuo
AU - Kamiya, Hiroto
AU - Ryuichi Shigemoto
AU - Akiguchi, Ichiro
AU - Mizuno, Noboru
ID - 2522
IS - 1
JF - Brain Research
TI - Direct projections of non-pyramidal neurons of Ammon's horn to the supramammillary region in the cat
VL - 460
ER -
TY - JOUR
AB - 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.
AU - Mizuno, Noboru
AU - Ueyama, Teizo
AU - Itoh, Kazuo
AU - Satoda, Takahiro
AU - Tashiro, Takashi
AU - Ryuichi Shigemoto
ID - 2523
IS - 1
JF - Neuroscience Letters
TI - Direct projections from the subthalamic nucleus of Luys to the spinal cord in the Japanese monkey
VL - 89
ER -
TY - JOUR
AB - 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.
AU - Kaneko, Takeshi
AU - Ryuichi Shigemoto
AU - Mizuno, Noboru
ID - 2524
IS - 1
JF - Brain Research
TI - Metabolism of glutamate and ammonia in astrocyte an immunocytochemical study
VL - 457
ER -
TY - JOUR
AU - Leonid Sazanov
AU - Karavaev, V A
AU - Kukushkin, A K
ID - 1941
JF - J. Phys. Chem-Russia
TI - Mathematical model of photosynthesis regulation accounts for the effects of changes in external conditions and observed oscillations
VL - 52
ER -
TY - JOUR
AB - 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.
AU - Herbert Edelsbrunner
AU - Preparata, Franco P
ID - 4090
IS - 3
JF - Information and Computation
TI - Minimum polygonal separation
VL - 77
ER -
TY - JOUR
AB - 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.
AU - Herbert Edelsbrunner
AU - Skiena,Steven S
ID - 4091
IS - 5
JF - SIAM Journal on Computing
TI - Probing convex polygons with X-Rays
VL - 17
ER -
TY - CONF
AU - Herbert Edelsbrunner
ID - 4096
TI - Geometric structures in computational geometry
VL - 317
ER -
TY - CONF
AB - 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.
AU - Herbert Edelsbrunner
AU - Guibas, Leonidas
AU - Pach, János
AU - Pollack, Richard
AU - Seidel, Raimund
AU - Sharir, Micha
ID - 4097
TI - Arrangements of curves in the plane - topology, combinatorics, and algorithms
VL - 317
ER -
TY - GEN
AU - Coyne, Jerry A
AU - Nicholas Barton
ID - 4315
T2 - Nature
TI - What do we know about speciation ?
VL - 331
ER -
TY - GEN
AU - Nicholas Barton
AU - Jones, Steve
ID - 4316
T2 - Nature
TI - Molecular evolutionary genetics
VL - 332
ER -
TY - CHAP
AU - Nicholas Barton
ED - Myers, Alan A
ED - Giller, Paul S
ID - 4317
T2 - Analytical biogeography
TI - Speciation
ER -
TY - GEN
AU - Nicholas Barton
AU - Jones, Steve
AU - Mallet, James L
ID - 4318
T2 - Nature
TI - No barriers to speciation
VL - 336
ER -
TY - JOUR
AU - Dallas, John F
AU - Nicholas Barton
AU - Dover, Gabriel A.
ID - 3655
IS - 6
JF - Molecular Biology and Evolution
TI - Interracial rDNA variation in the grasshopper Podisma pedestris
VL - 5
ER -
TY - JOUR
AU - Nishimura, Masaki
AU - Ryuichi Shigemoto
AU - Matsubayashi, K
AU - Mimori, Y
AU - Kameyama, Masakuni
ID - 2521
IS - 11
JF - Clinical Neurology
TI - Meningoencephalitis during the pre-icteric phase of hepatitis A - a case report
VL - 27
ER -
TY - BOOK
AB - 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.
AU - Edelsbrunner, Herbert
ID - 3900
SN - 9783540137221
TI - Algorithms in Combinatorial Geometry
VL - 10
ER -
TY - JOUR
AB - 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.
AU - Herbert Edelsbrunner
AU - Shen, Xiaojun
ID - 4094
IS - 2
JF - Information Processing Letters
TI - A tight lower bound on the size of visibility graphs
VL - 26
ER -
TY - JOUR
AB - 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.
AU - Chazelle, Bernard
AU - Herbert Edelsbrunner
ID - 4095
IS - 11
JF - IEEE Transactions on Computers
TI - An improved algorithm for constructing kth-order Voronoi diagrams
VL - 36
ER -
TY - JOUR
AB - 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.
AU - Chazelle, Bernard
AU - Herbert Edelsbrunner
ID - 4100
IS - 1
JF - Discrete & Computational Geometry
TI - Linear space data structures for two types of range search
VL - 2
ER -
TY - JOUR
AB - 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.
AU - Herbert Edelsbrunner
AU - Overmars, Mark H
ID - 4101
IS - 6
JF - Information Processing Letters
TI - Zooming by repeated range detection
VL - 24
ER -
TY - JOUR
AB - 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.
AU - Dobkin, David P
AU - Herbert Edelsbrunner
ID - 4102
IS - 3
JF - Journal of Algorithms
TI - Space searching for intersecting objects
VL - 8
ER -
TY - JOUR
AB - 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.
AU - Westerman, Michael
AU - Nicholas Barton
AU - Hewitt, Godfrey M
ID - 4319
JF - Heredity
TI - Differences in DNA content between two chromosomal races of the grasshopper Podisma pedestris
VL - 58
ER -
TY - JOUR
AB - 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.
AU - Rouhani, Shahin
AU - Nicholas Barton
ID - 4320
IS - 1-2
JF - Physica A
TI - Instantons and stochastic quantization
VL - 143
ER -
TY - JOUR
AB - 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.
AU - Nicholas Barton
ID - 4322
IS - 1
JF - Genetical Research
TI - The probability of establishment of an advantageous mutation in a subdivided population
VL - 50
ER -
TY - CONF
AB - 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)).
AU - Herbert Edelsbrunner
AU - Pach, János
AU - Schwartz, Jacob T
AU - Sharir, Micha
ID - 3514
TI - On the lower envelope of bivariate functions and its applications
ER -
TY - JOUR
AB - 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.
AU - Rouhani, Shahin
AU - Nicholas Barton
ID - 3656
IS - 1
JF - Journal of Theoretical Biology
TI - The probability of peak shifts in a founder population
VL - 126
ER -
TY - JOUR
AB - 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.
AU - Rouhani, Shahin
AU - Nicholas Barton
ID - 3657
IS - 3
JF - Theoretical Population Biology
TI - Speciation and the "shifting balance" in a continuous population
VL - 31
ER -
TY - JOUR
AB - 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.
AU - Hewitt, Godfrey M
AU - Nichols, R. A.
AU - Nicholas Barton
ID - 3658
IS - 3
JF - Heredity
TI - Homogamy in a hybrid zone in the alpine grasshopper Podisma pedestris
VL - 59
ER -
TY - JOUR
AU - Charlesworth, Brian
AU - Coyne, Jerry A
AU - Nicholas Barton
ID - 3659
IS - 1
JF - American Naturalist
TI - The relative rates of evolution of sex chromosomes and autosomes.
VL - 130
ER -
TY - JOUR
AB - 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.
AU - Nicholas Barton
AU - Turelli, Michael
ID - 3660
IS - 2
JF - Genetical Research
TI - Adaptive landscapes, genetic distance, and the evolution of quantitative characters
VL - 49
ER -
TY - JOUR
AB - 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.
AU - Nicholas Barton
AU - Rouhani, Shahin
ID - 3661
IS - 4
JF - Journal of Theoretical Biology
TI - The frequency of shifts between alternative equilibria
VL - 125
ER -
TY - JOUR
AB - 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.
AU - Herbert Edelsbrunner
AU - Stöckl, Gerd
ID - 4098
IS - 2
JF - Journal of Combinatorial Theory Series A
TI - The number of extreme pairs of finite point-sets in Euclidean spaces
VL - 43
ER -
TY - JOUR
AB - 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.
AU - Herbert Edelsbrunner
AU - Welzl, Emo
ID - 4099
IS - 5
JF - Information Processing Letters
TI - Halfplanar range search in linear space and O(n0.695) query time
VL - 23
ER -
TY - JOUR
AB - 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).
AU - Herbert Edelsbrunner
AU - Welzl, Emo
ID - 4103
IS - 2
JF - Journal of Combinatorial Theory Series A
TI - On the maximal number of edges of many faces in an arrangement
VL - 41
ER -
TY - JOUR
AB - 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
AU - Herbert Edelsbrunner
AU - Guibas, Leonidas J
AU - Stolfi, Jorge
ID - 4104
IS - 2
JF - SIAM Journal on Computing
TI - Optimal point location in a monotone subdivision
VL - 15
ER -
TY - JOUR
AB - 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
AU - Herbert Edelsbrunner
AU - O'Rourke, Joseph
AU - Seidel, Raimund
ID - 4105
IS - 2
JF - SIAM Journal on Computing
TI - Constructing arrangements of lines and hyperplanes with applications
VL - 15
ER -
TY - JOUR
AB - 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.
AU - Herbert Edelsbrunner
AU - Waupotitsch, Roman
ID - 4106
IS - 2
JF - Journal of Symbolic Computation
TI - Computing a ham-sandwich cut in two dimensions
VL - 2
ER -
TY - JOUR
AB - 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.
AU - Herbert Edelsbrunner
AU - Haussler, David H
ID - 4107
IS - C
JF - Discrete Mathematics
TI - The complexity of cells in 3-dimensional arrangements
VL - 60
ER -
TY - JOUR
AB - 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.
AU - Herbert Edelsbrunner
AU - Seidel, Raimund
ID - 4108
IS - 1
JF - Discrete & Computational Geometry
TI - Voronoi diagrams and arrangements
VL - 1
ER -
TY - JOUR
AB - 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.
AU - Herbert Edelsbrunner
AU - Haring, Günter
AU - Hilbert, D
ID - 4109
IS - 1
JF - Computer Journal
TI - Rectangular point location in d-dimensions with applications
VL - 29
ER -
TY - JOUR
AB - 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
AU - Herbert Edelsbrunner
AU - Welzl, Emo
ID - 4110
IS - 1
JF - SIAM Journal on Computing
TI - Constructing belts in two-dimensional arrangements with applications
VL - 15
ER -
TY - JOUR
AU - Szymura, Jacek M
AU - Nicholas Barton
ID - 4321
JF - Evolution; International Journal of Organic Evolution
TI - Genetic analysis of a hybrid zone between the fire-bellied toads Bombina bombina and B. variegata, near Cracow in Southern Poland
VL - 40
ER -
TY - JOUR
AB - 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.
AU - Nicholas Barton
AU - POST,R. J
ID - 4323
IS - 4
JF - Journal of Theoretical Biology
TI - Sibling competition and the advantage of mixed families
VL - 120
ER -
TY - JOUR
AB - 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.
AU - Nicholas Barton
ID - 4324
IS - 3
JF - Genetical Research
TI - The maintenance of polygenic variation through a balance between mutation and stabilising selection
VL - 47
ER -
TY - JOUR
AB - 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.
AU - Peter Jonas
AU - Vogel, Werner
AU - Arantes, Eliane C
AU - Giglio, Jose R
ID - 3464
IS - 1
JF - Pflugers Archiv : European Journal of Physiology
TI - Toxin γ of the scorpion Tityus serrulatus modifies both activation and inactivation of sodium permeability of nerve membrane
VL - 407
ER -
TY - JOUR
AU - Herbert Edelsbrunner
AU - Jaromczyk, Jerzy W
ID - 3579
JF - Congressus Numerantium
TI - How often can you see yourself in a convex configuration of mirrors?
VL - 53
ER -
TY - JOUR
AB - 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.
AU - Herbert Edelsbrunner
ID - 3580
IS - 1-4
JF - Algorithmica
TI - Edge-skeletons in arrangements with applications
VL - 1
ER -
TY - CONF
AU - Curtis,C. F
AU - Curtis,J.
AU - Nicholas Barton
ID - 3602
TI - Methodology for testing the hypothesis of single locus control of host resistance to infection and malignancy
ER -
TY - JOUR
AB - 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.
AU - Nagylaki, Thomas
AU - Nicholas Barton
ID - 3662
IS - 3
JF - Theoretical Population Biology
TI - Intrachromosomal gene conversion, linkage, and the evolution of multigene families
VL - 29
ER -
TY - JOUR
AB - 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.
AU - Nicholas Barton
AU - Slatkin, Montgomery
ID - 3663
IS - 3
JF - Heredity
TI - A quasi-equilibrium theory of the distribution of rare alleles in a subdivided population
VL - 56
ER -
TY - JOUR
AU - Nicholas Barton
AU - Bengtsson, Bengt O
ID - 3664
JF - Heredity
TI - The barrier to genetic exchange between hybridising populations
VL - 57
ER -
TY - JOUR
AU - Nicholas Barton
ID - 3665
JF - Heredity
TI - The effects of linkage and density-dependent regulation on gene flow
VL - 57
ER -
TY - JOUR
AB - 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.
AU - Herbert Edelsbrunner
AU - Maurer, Hermann A
ID - 4111
IS - 1
JF - Information Processing Letters
TI - Finding extreme-points in 3-dimensions and solving the post-office problem in the plane
VL - 21
ER -
TY - JOUR
AB - 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.
AU - Herbert Edelsbrunner
AU - Overmars, Mark H
ID - 4112
IS - 4
JF - Journal of Algorithms
TI - Batched dynamic solutions to decomposable searching problems
VL - 6
ER -
TY - JOUR
AB - 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.
AU - Herbert Edelsbrunner
AU - Welzl, Emo
ID - 4113
IS - 1
JF - Journal of Combinatorial Theory Series A
TI - On the number of line separations of a finite set in the plane
VL - 38
ER -
TY - JOUR
AB - 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
AU - Day,William H
AU - Herbert Edelsbrunner
ID - 4114
IS - 2-3
JF - Journal of Classification
TI - Investigation of Proportional Link Linkage Clustering Methods
VL - 2
ER -
TY - JOUR
AB - 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).
AU - Herbert Edelsbrunner
ID - 4115
IS - 2
JF - Journal of Algorithms
TI - Computing the extreme distances between two convex polygons
VL - 6
ER -
TY - JOUR
AB - 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”.
AU - Herbert Edelsbrunner
ID - 4116
IS - 1
JF - Theoretical Computer Science
TI - Finding Transversals for Sets of Simple Geometric-Figures
VL - 35
ER -
TY - JOUR
AB - 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.
AU - Chazelle, Bernard
AU - Herbert Edelsbrunner
ID - 4120
IS - 1
JF - Journal of Symbolic Computation
TI - Optimal solutions for a class of point retrieval problems
VL - 1
ER -
TY - CONF
AU - Curtis,C. F
AU - Curtis,J.
AU - Nicholas Barton
ID - 4241
TI - Methodology for testing the hypothesis of single locus control of host resistance to infection and malignancy
VL - 3
ER -
TY - GEN
AU - Jones, Steve
AU - Nicholas Barton
ID - 4325
T2 - Nature
TI - Haldane's Rule OK
VL - 314
ER -
TY - JOUR
AU - Nicholas Barton
AU - Hewitt, Godfrey M
ID - 4326
JF - Annual Review of Ecology and Systematics
TI - Analysis of hybrid zones
VL - 16
ER -
TY - JOUR
AU - Herbert Edelsbrunner
AU - van Leeuwen,Jan
AU - Ottmann,Thomas
AU - Wood, Derick
ID - 4117
IS - 2
JF - Rairo-Informatique Theorique Et Applications-Theoretical Informatics and Applications
TI - Computing the connected components of simple rectilinear geometrical objects in D-Space
VL - 18
ER -
TY - JOUR
AB - 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.
AU - Herbert Edelsbrunner
AU - O'Rourke, Joseph
AU - Welzl, Emo
ID - 4118
IS - 2
JF - Computer Vision, Graphics, and Image Processing
TI - Stationing guards in rectilinear art galleries
VL - 27
ER -
TY - CONF
AU - Herbert Edelsbrunner
AU - Welzl, Emo
ID - 4119
TI - Monotone edge sequences in line arrangements and applications
VL - 176
ER -
TY - JOUR
AB - 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.
AU - Day,William H
AU - Herbert Edelsbrunner
ID - 4121
IS - 1
JF - Journal of Classification
TI - Efficient algorithms for agglomerative hierarchical clustering methods
VL - 1
ER -
TY - CONF
AB - 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.
AU - Herbert Edelsbrunner
ID - 4122
TI - Key-problems and key-methods in computational geometry
VL - 166
ER -
TY - JOUR
AB - 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.
AU - Herbert Edelsbrunner
AU - Overmars, Mark H
AU - Seidel, Raimund
ID - 4123
IS - 1
JF - Computer Vision, Graphics, and Image Processing
TI - Some methods of computational geometry applied to computer graphics
VL - 28
ER -
TY - JOUR
AB - 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.
AU - Aurenhammer,Franz
AU - Herbert Edelsbrunner
ID - 4125
IS - 2
JF - Pattern Recognition
TI - An optimal algorithm for constructing the weighted Voronoi diagram in the plane
VL - 17
ER -
TY - JOUR
AU - Nicholas Barton
AU - Charlesworth, Brian
ID - 4327
JF - Annual Review of Ecology and Systematics
TI - Genetic revolutions, founder effects, and speciation
VL - 15
ER -
TY - CONF
AU - Dobkin, David P
AU - Herbert Edelsbrunner
ID - 3513
TI - Ham-sandwich theorems applied to intersection problems
ER -
TY - CONF
AU - Herbert Edelsbrunner
AU - Welzl, Emo
ID - 4124
TI - On the number of equal-sized semispaces of a set of points in the plane
VL - 154
ER -
TY - JOUR
AB - 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.
AU - Herbert Edelsbrunner
ID - 4126
IS - 3-4
JF - International Journal of Computer Mathematics
TI - A new approach to rectangle intersections part 1
VL - 13
ER -
TY - JOUR
AB - 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.
AU - Herbert Edelsbrunner
ID - 4127
IS - 3-4
JF - International Journal of Computer Mathematics
TI - A new approach to rectangle intersections part 2
VL - 13
ER -
TY - JOUR
AB - 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.
AU - Herbert Edelsbrunner
AU - Kirkpatrick, David G
AU - Seidel, Raimund
ID - 4128
IS - 4
JF - IEEE Transactions on Information Theory
TI - On the shape of a set of points in the plane
VL - 29
ER -
TY - CHAP
AB - 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.
AU - Nicholas Barton
AU - Hewitt, Godfrey M
ED - Oxford,Geoffrey S
ED - Rollinson,David
ID - 4328
T2 - Protein polymorphism: adaptive and taxonomic significance
TI - Hybrid zones as barriers to gene flow
VL - 24
ER -
TY - GEN
AU - Nicholas Barton
ID - 4329
IS - 2
T2 - Animal Behaviour
TI - The extended phenotype: the gene as the unit of selection (review of Dawkins R 1982)
VL - 31
ER -
TY - GEN
AU - Nicholas Barton
ID - 4330
T2 - Heredity
TI - Gene flow and speciation (abstract)
VL - 50
ER -
TY - CHAP
AU - Bucher, W.
AU - Herbert Edelsbrunner
ED - Preparata, Franco P
ID - 3562
T2 - Computational Geometry: Theory and Applications
TI - On expected- and worst-case segment trees
VL - 1
ER -
TY - CHAP
AU - Herbert Edelsbrunner
AU - Overmars, Mark H
AU - Wood, Derick
ED - Preparata, Franco P
ID - 3563
T2 - Computational Geometry: Theory and Applications
TI - Graphics in Flatland: a case study
VL - 1
ER -
TY - CHAP
AU - Herbert Edelsbrunner
ED - Maurer, Hermann A
ID - 3564
T2 - Überblicke Informationsverarbeitung
TI - Neue Entwicklungen im Bereich Datenstrukturen
ER -
TY - GEN
AU - Nicholas Barton
AU - Jones, Steve
ID - 3598
T2 - Nature
TI - Mitochondrial DNA: new clues about evolution
VL - 306
ER -
TY - JOUR
AB - 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.
AU - Halliday, Bruce
AU - Nicholas Barton
AU - Hewitt, Godfrey M
ID - 3666
IS - 1
JF - Biological Journal of the Linnean Society
TI - Electrophoretic analysis of a chromosomal hybrid zone in the grasshopper Podisma pedestris
VL - 19
ER -
TY - JOUR
AB - 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.
AU - Nicholas Barton
AU - Halliday, Bruce
AU - Hewitt, Godfrey M
ID - 3667
IS - 2
JF - Heredity
TI - Rare electrophoretic variants in a hybrid zone
VL - 50
ER -
TY - JOUR
AU - Nicholas Barton
ID - 3668
IS - 3
JF - Evolution; International Journal of Organic Evolution
TI - Multilocus clines
VL - 37
ER -