TY - JOUR
AB - A tour of a finite set P of points is a necklace-tour if there are disks with the points in P as centers such that two disks intersect if and only if their centers are adjacent in . It has been observed by Sanders that a necklace-tour is an optimal traveling salesman tour.
In this paper, we present an algorithm that either reports that no necklace-tour exists or outputs a necklace-tour of a given set of n points in O(n2 log n) time. If a tour is given, then we can test in O(n2) time whether or not this tour is a necklace-tour. Both algorithms can be generalized to ƒ-factors of point sets in the plane. The complexity results rely on a combinatorial analysis of certain intersection graphs of disks defined for finite sets of points in the plane.
AU - Herbert Edelsbrunner
AU - Rote,Günter
AU - Welzl, Emo
ID - 4084
IS - 2
JF - Theoretical Computer Science
TI - Testing the necklace condition for shortest tours and optimal factors in the plane
VL - 66
ER -
TY - CONF
AB - Let C be a cell complex in d-dimensional Euclidean space whose faces are obtained by orthogonal projection of the faces of a convex polytope in d + 1 dimensions. For example, the Delaunay triangulation of a finite point set is such a cell complex. This paper shows that the in_front/behind relation defined for the faces of C with respect to any fixed viewpoint x is acyclic. This result has applications to hidden line/surface removal and other problems in computational geometry.
AU - Herbert Edelsbrunner
ID - 4085
TI - An acyclicity theorem for cell complexes in d dimension
ER -
TY - JOUR
AB - 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.
AU - Herbert Edelsbrunner
ID - 4086
IS - 4
JF - Discrete & Computational Geometry
TI - The upper envelope of piecewise linear functions: Tight bounds on the number of faces
VL - 4
ER -
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 - 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 - 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 - 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
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 - 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 - 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 - 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 - 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 -