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 -