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 -