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 -