---
_id: '3464'
abstract:
- lang: eng
text: 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.
article_processing_charge: No
article_type: original
author:
- first_name: Peter M
full_name: Jonas, Peter M
id: 353C1B58-F248-11E8-B48F-1D18A9856A87
last_name: Jonas
orcid: 0000-0001-5001-4804
- first_name: Werner
full_name: Vogel, Werner
last_name: Vogel
- first_name: Eliane
full_name: Arantes, Eliane
last_name: Arantes
- first_name: Jose
full_name: Giglio, Jose
last_name: Giglio
citation:
ama: 'Jonas PM, Vogel W, Arantes E, Giglio J. Toxin γ of the scorpion Tityus serrulatus
modifies both activation and inactivation of sodium permeability of nerve membrane.
Pflugers Archiv : European Journal of Physiology. 1986;407(1):92-99. doi:10.1007/BF00580727'
apa: 'Jonas, P. M., Vogel, W., Arantes, E., & Giglio, J. (1986). Toxin γ of
the scorpion Tityus serrulatus modifies both activation and inactivation of sodium
permeability of nerve membrane. Pflugers Archiv : European Journal of Physiology.
Springer. https://doi.org/10.1007/BF00580727'
chicago: 'Jonas, Peter M, Werner Vogel, Eliane Arantes, and Jose Giglio. “Toxin
γ of the Scorpion Tityus Serrulatus Modifies Both Activation and Inactivation
of Sodium Permeability of Nerve Membrane.” Pflugers Archiv : European Journal
of Physiology. Springer, 1986. https://doi.org/10.1007/BF00580727.'
ieee: 'P. M. Jonas, W. Vogel, E. Arantes, and J. Giglio, “Toxin γ of the scorpion
Tityus serrulatus modifies both activation and inactivation of sodium permeability
of nerve membrane,” Pflugers Archiv : European Journal of Physiology, vol.
407, no. 1. Springer, pp. 92–99, 1986.'
ista: 'Jonas PM, Vogel W, Arantes E, Giglio J. 1986. Toxin γ of the scorpion Tityus
serrulatus modifies both activation and inactivation of sodium permeability of
nerve membrane. Pflugers Archiv : European Journal of Physiology. 407(1), 92–99.'
mla: 'Jonas, Peter M., et al. “Toxin γ of the Scorpion Tityus Serrulatus Modifies
Both Activation and Inactivation of Sodium Permeability of Nerve Membrane.” Pflugers
Archiv : European Journal of Physiology, vol. 407, no. 1, Springer, 1986,
pp. 92–99, doi:10.1007/BF00580727.'
short: 'P.M. Jonas, W. Vogel, E. Arantes, J. Giglio, Pflugers Archiv : European
Journal of Physiology 407 (1986) 92–99.'
date_created: 2018-12-11T12:03:28Z
date_published: 1986-07-01T00:00:00Z
date_updated: 2022-02-03T09:46:42Z
day: '01'
doi: 10.1007/BF00580727
extern: '1'
external_id:
pmid:
- '2426654 '
intvolume: ' 407'
issue: '1'
language:
- iso: eng
month: '07'
oa_version: None
page: 92 - 99
pmid: 1
publication: 'Pflugers Archiv : European Journal of Physiology'
publication_identifier:
eissn:
- 1432-2013
issn:
- 0031-6768
publication_status: published
publisher: Springer
publist_id: '2923'
quality_controlled: '1'
status: public
title: Toxin γ of the scorpion Tityus serrulatus modifies both activation and inactivation
of sodium permeability of nerve membrane
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 407
year: '1986'
...
---
_id: '3579'
article_processing_charge: No
article_type: original
author:
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
- first_name: Jerzy
full_name: Jaromczyk, Jerzy
last_name: Jaromczyk
citation:
ama: Edelsbrunner H, Jaromczyk J. How often can you see yourself in a convex configuration
of mirrors? Congressus Numerantium. 1986;53:193-200.
apa: Edelsbrunner, H., & Jaromczyk, J. (1986). How often can you see yourself
in a convex configuration of mirrors? Congressus Numerantium. Utilitas
Mathemtica Publ. Inc.
chicago: Edelsbrunner, Herbert, and Jerzy Jaromczyk. “How Often Can You See Yourself
in a Convex Configuration of Mirrors?” Congressus Numerantium. Utilitas
Mathemtica Publ. Inc., 1986.
ieee: H. Edelsbrunner and J. Jaromczyk, “How often can you see yourself in a convex
configuration of mirrors?,” Congressus Numerantium, vol. 53. Utilitas Mathemtica
Publ. Inc., pp. 193–200, 1986.
ista: Edelsbrunner H, Jaromczyk J. 1986. How often can you see yourself in a convex
configuration of mirrors? Congressus Numerantium. 53, 193–200.
mla: Edelsbrunner, Herbert, and Jerzy Jaromczyk. “How Often Can You See Yourself
in a Convex Configuration of Mirrors?” Congressus Numerantium, vol. 53,
Utilitas Mathemtica Publ. Inc., 1986, pp. 193–200.
short: H. Edelsbrunner, J. Jaromczyk, Congressus Numerantium 53 (1986) 193–200.
date_created: 2018-12-11T12:04:04Z
date_published: 1986-01-01T00:00:00Z
date_updated: 2022-02-02T15:58:04Z
day: '01'
extern: '1'
intvolume: ' 53'
language:
- iso: eng
month: '01'
oa_version: None
page: 193 - 200
publication: Congressus Numerantium
publication_identifier:
issn:
- 0384-9864
publication_status: published
publisher: Utilitas Mathemtica Publ. Inc.
publist_id: '2806'
quality_controlled: '1'
status: public
title: How often can you see yourself in a convex configuration of mirrors?
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 53
year: '1986'
...
---
_id: '3580'
abstract:
- lang: eng
text: "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.\r\nWe 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."
article_processing_charge: No
article_type: original
author:
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
citation:
ama: Edelsbrunner H. Edge-skeletons in arrangements with applications. Algorithmica.
1986;1(1-4):93-109. doi:10.1007/BF01840438
apa: Edelsbrunner, H. (1986). Edge-skeletons in arrangements with applications.
Algorithmica. Springer. https://doi.org/10.1007/BF01840438
chicago: Edelsbrunner, Herbert. “Edge-Skeletons in Arrangements with Applications.”
Algorithmica. Springer, 1986. https://doi.org/10.1007/BF01840438.
ieee: H. Edelsbrunner, “Edge-skeletons in arrangements with applications,” Algorithmica,
vol. 1, no. 1–4. Springer, pp. 93–109, 1986.
ista: Edelsbrunner H. 1986. Edge-skeletons in arrangements with applications. Algorithmica.
1(1–4), 93–109.
mla: Edelsbrunner, Herbert. “Edge-Skeletons in Arrangements with Applications.”
Algorithmica, vol. 1, no. 1–4, Springer, 1986, pp. 93–109, doi:10.1007/BF01840438.
short: H. Edelsbrunner, Algorithmica 1 (1986) 93–109.
date_created: 2018-12-11T12:04:04Z
date_published: 1986-11-01T00:00:00Z
date_updated: 2022-02-02T09:36:32Z
day: '01'
doi: 10.1007/BF01840438
extern: '1'
intvolume: ' 1'
issue: 1-4
language:
- iso: eng
month: '11'
oa_version: None
page: 93 - 109
publication: Algorithmica
publication_identifier:
eissn:
- 1432-0541
issn:
- 0178-4617
publication_status: published
publisher: Springer
publist_id: '2805'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Edge-skeletons in arrangements with applications
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 1
year: '1986'
...
---
_id: '3662'
abstract:
- lang: eng
text: 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.
acknowledgement: Supported by National Science Foundation Grant DEB81-03530
article_processing_charge: No
article_type: original
author:
- first_name: Thomas
full_name: Nagylaki, Thomas
last_name: Nagylaki
- first_name: Nicholas H
full_name: Barton, Nicholas H
id: 4880FE40-F248-11E8-B48F-1D18A9856A87
last_name: Barton
orcid: 0000-0002-8548-5240
citation:
ama: Nagylaki T, Barton NH. Intrachromosomal gene conversion, linkage, and the evolution
of multigene families. Theoretical Population Biology. 1986;29(3):407-437.
doi:10.1016/0040-5809(86)90017-1
apa: Nagylaki, T., & Barton, N. H. (1986). Intrachromosomal gene conversion,
linkage, and the evolution of multigene families. Theoretical Population Biology.
Academic Press. https://doi.org/10.1016/0040-5809(86)90017-1
chicago: Nagylaki, Thomas, and Nicholas H Barton. “Intrachromosomal Gene Conversion,
Linkage, and the Evolution of Multigene Families.” Theoretical Population Biology.
Academic Press, 1986. https://doi.org/10.1016/0040-5809(86)90017-1.
ieee: T. Nagylaki and N. H. Barton, “Intrachromosomal gene conversion, linkage,
and the evolution of multigene families,” Theoretical Population Biology,
vol. 29, no. 3. Academic Press, pp. 407–437, 1986.
ista: Nagylaki T, Barton NH. 1986. Intrachromosomal gene conversion, linkage, and
the evolution of multigene families. Theoretical Population Biology. 29(3), 407–437.
mla: Nagylaki, Thomas, and Nicholas H. Barton. “Intrachromosomal Gene Conversion,
Linkage, and the Evolution of Multigene Families.” Theoretical Population Biology,
vol. 29, no. 3, Academic Press, 1986, pp. 407–37, doi:10.1016/0040-5809(86)90017-1.
short: T. Nagylaki, N.H. Barton, Theoretical Population Biology 29 (1986) 407–437.
date_created: 2018-12-11T12:04:30Z
date_published: 1986-06-01T00:00:00Z
date_updated: 2022-02-01T15:50:10Z
day: '01'
doi: 10.1016/0040-5809(86)90017-1
extern: '1'
intvolume: ' 29'
issue: '3'
language:
- iso: eng
month: '06'
oa_version: None
page: 407 - 437
publication: Theoretical Population Biology
publication_identifier:
eissn:
- 1096-0325
issn:
- 0040-5809
publication_status: published
publisher: Academic Press
publist_id: '2721'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Intrachromosomal gene conversion, linkage, and the evolution of multigene families
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 29
year: '1986'
...
---
_id: '3663'
abstract:
- lang: eng
text: 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.
acknowledgement: This research has been supported in part by grants from the Royal
Society of London, S.E.R.C., and the National Science Foundation. We thank J. Felsenstein
for helpful discussions of this problem.
article_processing_charge: No
article_type: original
author:
- first_name: Nicholas H
full_name: Barton, Nicholas H
id: 4880FE40-F248-11E8-B48F-1D18A9856A87
last_name: Barton
orcid: 0000-0002-8548-5240
- first_name: Montgomery
full_name: Slatkin, Montgomery
last_name: Slatkin
citation:
ama: Barton NH, Slatkin M. A quasi-equilibrium theory of the distribution of rare
alleles in a subdivided population. Heredity. 1986;56(3):409-416. doi:10.1038/hdy.1986.63
apa: Barton, N. H., & Slatkin, M. (1986). A quasi-equilibrium theory of the
distribution of rare alleles in a subdivided population. Heredity. Nature
Publishing Group. https://doi.org/10.1038/hdy.1986.63
chicago: Barton, Nicholas H, and Montgomery Slatkin. “A Quasi-Equilibrium Theory
of the Distribution of Rare Alleles in a Subdivided Population.” Heredity.
Nature Publishing Group, 1986. https://doi.org/10.1038/hdy.1986.63.
ieee: N. H. Barton and M. Slatkin, “A quasi-equilibrium theory of the distribution
of rare alleles in a subdivided population,” Heredity, vol. 56, no. 3.
Nature Publishing Group, pp. 409–416, 1986.
ista: Barton NH, Slatkin M. 1986. A quasi-equilibrium theory of the distribution
of rare alleles in a subdivided population. Heredity. 56(3), 409–416.
mla: Barton, Nicholas H., and Montgomery Slatkin. “A Quasi-Equilibrium Theory of
the Distribution of Rare Alleles in a Subdivided Population.” Heredity,
vol. 56, no. 3, Nature Publishing Group, 1986, pp. 409–16, doi:10.1038/hdy.1986.63.
short: N.H. Barton, M. Slatkin, Heredity 56 (1986) 409–416.
date_created: 2018-12-11T12:04:30Z
date_published: 1986-06-01T00:00:00Z
date_updated: 2022-02-01T15:04:01Z
day: '01'
doi: 10.1038/hdy.1986.63
extern: '1'
external_id:
pmid:
- '3733460 '
intvolume: ' 56'
issue: '3'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://www.nature.com/articles/hdy198663
month: '06'
oa: 1
oa_version: None
page: 409 - 416
pmid: 1
publication: Heredity
publication_identifier:
eissn:
- 1365-2540
issn:
- 0018-067X
publication_status: published
publisher: Nature Publishing Group
publist_id: '2720'
quality_controlled: '1'
scopus_import: '1'
status: public
title: A quasi-equilibrium theory of the distribution of rare alleles in a subdivided
population
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 56
year: '1986'
...
---
_id: '3664'
abstract:
- lang: eng
text: Suppose that selection acts at one or more loci to maintain genetic differences
between hybridising populations. Then, the flow of alleles at a neutral marker
locus which is linked to these selected loci will be impeded. We define and calculate
measures of the barrier to gene flow between two distinct demes, and across a
continuous habitat. In both cases, we find that in order for gene flow to be significantly
reduced over much of the genome, hybrids must be substantially less fit, and the
number of genes involved in building the barrier must be so large that the majority
of other genes become closely linked to some locus which is under selection. This
conclusion is not greatly affected by the pattern of epistasis, or the position
of the marker locus along the chromosome.
article_processing_charge: No
article_type: original
author:
- first_name: Nicholas H
full_name: Barton, Nicholas H
id: 4880FE40-F248-11E8-B48F-1D18A9856A87
last_name: Barton
orcid: 0000-0002-8548-5240
- first_name: Bengt
full_name: Bengtsson, Bengt
last_name: Bengtsson
citation:
ama: Barton NH, Bengtsson B. The barrier to genetic exchange between hybridising
populations. Heredity. 1986;57:357-376.
apa: Barton, N. H., & Bengtsson, B. (1986). The barrier to genetic exchange
between hybridising populations. Heredity. Nature Publishing Group.
chicago: Barton, Nicholas H, and Bengt Bengtsson. “The Barrier to Genetic Exchange
between Hybridising Populations.” Heredity. Nature Publishing Group, 1986.
ieee: N. H. Barton and B. Bengtsson, “The barrier to genetic exchange between hybridising
populations,” Heredity, vol. 57. Nature Publishing Group, pp. 357–376,
1986.
ista: Barton NH, Bengtsson B. 1986. The barrier to genetic exchange between hybridising
populations. Heredity. 57, 357–376.
mla: Barton, Nicholas H., and Bengt Bengtsson. “The Barrier to Genetic Exchange
between Hybridising Populations.” Heredity, vol. 57, Nature Publishing
Group, 1986, pp. 357–76.
short: N.H. Barton, B. Bengtsson, Heredity 57 (1986) 357–376.
date_created: 2018-12-11T12:04:30Z
date_published: 1986-01-01T00:00:00Z
date_updated: 2022-02-01T14:49:02Z
day: '01'
extern: '1'
intvolume: ' 57'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://www.nature.com/articles/hdy1986135
month: '01'
oa: 1
oa_version: Published Version
page: 357 - 376
publication: Heredity
publication_identifier:
eissn:
- 1365-2540
issn:
- 0018-067X
publication_status: published
publisher: Nature Publishing Group
publist_id: '2719'
quality_controlled: '1'
scopus_import: '1'
status: public
title: The barrier to genetic exchange between hybridising populations
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 57
year: '1986'
...
---
_id: '3665'
abstract:
- lang: eng
text: The rate of gene flow across a hybrid zone may be reduced by the presence
of a physical barrier, by a reduction of population density caused by reduced
fitness of hybrids (the “hybrid sink” effect), and by linkage. If the reduction
in hybrid fitness is not extreme, the strength of the barrier to gene flow caused
by these effects is. Here, w is the width of the cline; ρ* is the carrying capacity;
W̄* is the mean fitness of the population, excluding effects of density; R is
the strength of density-dependent regulation; and r̄ is the harmonic mean recombination
rate between the locus whose flow is being calculated, and loci under selection.
+, 0 denote populations outside the hybrid zone, and at its centre, respectively.
This relation is illustrated using data from hybrid ones in Bombina and Podisma,
and its implications for interpretation of data from nature are discussed.
acknowledgement: I would like to thank Shahin Rouhani and Richard Nichols for their
helpful comments on the manuscript, and the latter for providing the data used in
fig. 3. This work was supported by a grant from the Science and Engineering Research
Council (GR/C/91529).
article_processing_charge: No
article_type: original
author:
- first_name: Nicholas H
full_name: Barton, Nicholas H
id: 4880FE40-F248-11E8-B48F-1D18A9856A87
last_name: Barton
orcid: 0000-0002-8548-5240
citation:
ama: Barton NH. The effects of linkage and density-dependent regulation on gene
flow. Heredity. 1986;57:415-426.
apa: Barton, N. H. (1986). The effects of linkage and density-dependent regulation
on gene flow. Heredity. Nature Publishing Group.
chicago: Barton, Nicholas H. “The Effects of Linkage and Density-Dependent Regulation
on Gene Flow.” Heredity. Nature Publishing Group, 1986.
ieee: N. H. Barton, “The effects of linkage and density-dependent regulation on
gene flow,” Heredity, vol. 57. Nature Publishing Group, pp. 415–426, 1986.
ista: Barton NH. 1986. The effects of linkage and density-dependent regulation on
gene flow. Heredity. 57, 415–426.
mla: Barton, Nicholas H. “The Effects of Linkage and Density-Dependent Regulation
on Gene Flow.” Heredity, vol. 57, Nature Publishing Group, 1986, pp. 415–26.
short: N.H. Barton, Heredity 57 (1986) 415–426.
date_created: 2018-12-11T12:04:30Z
date_published: 1986-01-01T00:00:00Z
date_updated: 2022-02-01T14:31:29Z
day: '01'
extern: '1'
intvolume: ' 57'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://www.nature.com/articles/hdy1986142
month: '01'
oa: 1
oa_version: Published Version
page: 415 - 426
publication: Heredity
publication_identifier:
eissn:
- 1365-2540
issn:
- 0018-067X
publication_status: published
publisher: Nature Publishing Group
publist_id: '2718'
quality_controlled: '1'
scopus_import: '1'
status: public
title: The effects of linkage and density-dependent regulation on gene flow
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 57
year: '1986'
...
---
_id: '4098'
abstract:
- lang: eng
text: 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.
article_processing_charge: No
article_type: original
author:
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
- first_name: Gerd
full_name: Stöckl, Gerd
last_name: Stöckl
citation:
ama: Edelsbrunner H, Stöckl G. The number of extreme pairs of finite point-sets
in Euclidean spaces. Journal of Combinatorial Theory Series A. 1986;43(2):344-349.
doi:10.1016/0097-3165(86)90075-0
apa: Edelsbrunner, H., & Stöckl, G. (1986). The number of extreme pairs of finite
point-sets in Euclidean spaces. Journal of Combinatorial Theory Series A.
Elsevier. https://doi.org/10.1016/0097-3165(86)90075-0
chicago: Edelsbrunner, Herbert, and Gerd Stöckl. “The Number of Extreme Pairs of
Finite Point-Sets in Euclidean Spaces.” Journal of Combinatorial Theory Series
A. Elsevier, 1986. https://doi.org/10.1016/0097-3165(86)90075-0.
ieee: H. Edelsbrunner and G. Stöckl, “The number of extreme pairs of finite point-sets
in Euclidean spaces,” Journal of Combinatorial Theory Series A, vol. 43,
no. 2. Elsevier, pp. 344–349, 1986.
ista: Edelsbrunner H, Stöckl G. 1986. The number of extreme pairs of finite point-sets
in Euclidean spaces. Journal of Combinatorial Theory Series A. 43(2), 344–349.
mla: Edelsbrunner, Herbert, and Gerd Stöckl. “The Number of Extreme Pairs of Finite
Point-Sets in Euclidean Spaces.” Journal of Combinatorial Theory Series A,
vol. 43, no. 2, Elsevier, 1986, pp. 344–49, doi:10.1016/0097-3165(86)90075-0.
short: H. Edelsbrunner, G. Stöckl, Journal of Combinatorial Theory Series A 43 (1986)
344–349.
date_created: 2018-12-11T12:06:56Z
date_published: 1986-11-01T00:00:00Z
date_updated: 2022-02-01T14:02:41Z
day: '01'
doi: 10.1016/0097-3165(86)90075-0
extern: '1'
intvolume: ' 43'
issue: '2'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://www.sciencedirect.com/science/article/pii/0097316586900750?via%3Dihub
month: '11'
oa: 1
oa_version: None
page: 344 - 349
publication: Journal of Combinatorial Theory Series A
publication_identifier:
eissn:
- 1096-0899
issn:
- 0097-3165
publication_status: published
publisher: Elsevier
publist_id: '2020'
quality_controlled: '1'
scopus_import: '1'
status: public
title: The number of extreme pairs of finite point-sets in Euclidean spaces
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 43
year: '1986'
...
---
_id: '4099'
abstract:
- lang: eng
text: 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.
acknowledgement: 'We thank W. Bucher for help in the analysis of the time complexity
of the query algorithm. '
article_processing_charge: No
article_type: original
author:
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
- first_name: Emo
full_name: Welzl, Emo
last_name: Welzl
citation:
ama: Edelsbrunner H, Welzl E. Halfplanar range search in linear space and O(n0.695)
query time. Information Processing Letters. 1986;23(5):289-293. doi:10.1016/0020-0190(86)90088-8
apa: Edelsbrunner, H., & Welzl, E. (1986). Halfplanar range search in linear
space and O(n0.695) query time. Information Processing Letters. Elsevier.
https://doi.org/10.1016/0020-0190(86)90088-8
chicago: Edelsbrunner, Herbert, and Emo Welzl. “Halfplanar Range Search in Linear
Space and O(N0.695) Query Time.” Information Processing Letters. Elsevier,
1986. https://doi.org/10.1016/0020-0190(86)90088-8.
ieee: H. Edelsbrunner and E. Welzl, “Halfplanar range search in linear space and
O(n0.695) query time,” Information Processing Letters, vol. 23, no. 5.
Elsevier, pp. 289–293, 1986.
ista: Edelsbrunner H, Welzl E. 1986. Halfplanar range search in linear space and
O(n0.695) query time. Information Processing Letters. 23(5), 289–293.
mla: Edelsbrunner, Herbert, and Emo Welzl. “Halfplanar Range Search in Linear Space
and O(N0.695) Query Time.” Information Processing Letters, vol. 23, no.
5, Elsevier, 1986, pp. 289–93, doi:10.1016/0020-0190(86)90088-8.
short: H. Edelsbrunner, E. Welzl, Information Processing Letters 23 (1986) 289–293.
date_created: 2018-12-11T12:06:56Z
date_published: 1986-11-24T00:00:00Z
date_updated: 2022-02-01T14:17:10Z
day: '24'
doi: 10.1016/0020-0190(86)90088-8
extern: '1'
intvolume: ' 23'
issue: '5'
language:
- iso: eng
month: '11'
oa_version: None
page: 289 - 293
publication: Information Processing Letters
publication_identifier:
eissn:
- 1872-6119
issn:
- 0020-0190
publication_status: published
publisher: Elsevier
publist_id: '2021'
quality_controlled: '1'
status: public
title: Halfplanar range search in linear space and O(n0.695) query time
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 23
year: '1986'
...
---
_id: '4103'
abstract:
- lang: eng
text: 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).
acknowledgement: The second author thanks Gan Gusfield for useful discussion.
article_processing_charge: No
author:
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
- first_name: Emo
full_name: Welzl, Emo
last_name: Welzl
citation:
ama: Edelsbrunner H, Welzl E. On the maximal number of edges of many faces in an
arrangement. Journal of Combinatorial Theory Series A. 1986;41(2):159-166.
doi:10.1016/0097-3165(86)90078-6
apa: Edelsbrunner, H., & Welzl, E. (1986). On the maximal number of edges of
many faces in an arrangement. Journal of Combinatorial Theory Series A.
Elsevier. https://doi.org/10.1016/0097-3165(86)90078-6
chicago: Edelsbrunner, Herbert, and Emo Welzl. “On the Maximal Number of Edges of
Many Faces in an Arrangement.” Journal of Combinatorial Theory Series A.
Elsevier, 1986. https://doi.org/10.1016/0097-3165(86)90078-6.
ieee: H. Edelsbrunner and E. Welzl, “On the maximal number of edges of many faces
in an arrangement,” Journal of Combinatorial Theory Series A, vol. 41,
no. 2. Elsevier, pp. 159–166, 1986.
ista: Edelsbrunner H, Welzl E. 1986. On the maximal number of edges of many faces
in an arrangement. Journal of Combinatorial Theory Series A. 41(2), 159–166.
mla: Edelsbrunner, Herbert, and Emo Welzl. “On the Maximal Number of Edges of Many
Faces in an Arrangement.” Journal of Combinatorial Theory Series A, vol.
41, no. 2, Elsevier, 1986, pp. 159–66, doi:10.1016/0097-3165(86)90078-6.
short: H. Edelsbrunner, E. Welzl, Journal of Combinatorial Theory Series A 41 (1986)
159–166.
date_created: 2018-12-11T12:06:57Z
date_published: 1986-11-01T00:00:00Z
date_updated: 2022-02-01T09:46:55Z
day: '01'
doi: 10.1016/0097-3165(86)90078-6
extern: '1'
intvolume: ' 41'
issue: '2'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://www.sciencedirect.com/science/article/pii/0097316586900786?via%3Dihub
month: '11'
oa: 1
oa_version: Published Version
page: 159 - 166
publication: Journal of Combinatorial Theory Series A
publication_identifier:
eissn:
- 1096-0899
issn:
- 0097-3165
publication_status: published
publisher: Elsevier
publist_id: '2015'
quality_controlled: '1'
scopus_import: '1'
status: public
title: On the maximal number of edges of many faces in an arrangement
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 41
year: '1986'
...
---
_id: '4104'
abstract:
- lang: eng
text: "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.\r\n© 1986 Society for Industrial and Applied
Mathematics"
acknowledgement: We would like to thank Andrei Broder, Dan Greene, Mary Claire van
Leunen, Greg Nelson, Lyle Ramshaw, and F. Frances Yao, whose comments and suggestions
have greatly improved the readability of this paper.
article_processing_charge: No
article_type: original
author:
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
- first_name: Leonidas
full_name: Guibas, Leonidas
last_name: Guibas
- first_name: Jorge
full_name: Stolfi, Jorge
last_name: Stolfi
citation:
ama: Edelsbrunner H, Guibas L, Stolfi J. Optimal point location in a monotone subdivision.
SIAM Journal on Computing. 1986;15(2):317-340. doi:10.1137/0215023
apa: Edelsbrunner, H., Guibas, L., & Stolfi, J. (1986). Optimal point location
in a monotone subdivision. SIAM Journal on Computing. SIAM. https://doi.org/10.1137/0215023
chicago: Edelsbrunner, Herbert, Leonidas Guibas, and Jorge Stolfi. “Optimal Point
Location in a Monotone Subdivision.” SIAM Journal on Computing. SIAM, 1986.
https://doi.org/10.1137/0215023.
ieee: H. Edelsbrunner, L. Guibas, and J. Stolfi, “Optimal point location in a monotone
subdivision,” SIAM Journal on Computing, vol. 15, no. 2. SIAM, pp. 317–340,
1986.
ista: Edelsbrunner H, Guibas L, Stolfi J. 1986. Optimal point location in a monotone
subdivision. SIAM Journal on Computing. 15(2), 317–340.
mla: Edelsbrunner, Herbert, et al. “Optimal Point Location in a Monotone Subdivision.”
SIAM Journal on Computing, vol. 15, no. 2, SIAM, 1986, pp. 317–40, doi:10.1137/0215023.
short: H. Edelsbrunner, L. Guibas, J. Stolfi, SIAM Journal on Computing 15 (1986)
317–340.
date_created: 2018-12-11T12:06:58Z
date_published: 1986-01-01T00:00:00Z
date_updated: 2022-02-01T10:05:55Z
day: '01'
doi: 10.1137/0215023
extern: '1'
intvolume: ' 15'
issue: '2'
language:
- iso: eng
month: '01'
oa_version: None
page: 317 - 340
publication: SIAM Journal on Computing
publication_identifier:
eissn:
- 1095-7111
issn:
- 0097-5397
publication_status: published
publisher: SIAM
publist_id: '2016'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Optimal point location in a monotone subdivision
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 15
year: '1986'
...
---
_id: '4105'
abstract:
- lang: eng
text: "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 $.\r\n© 1986 Society for Industrial and Applied Mathematics"
acknowledgement: "We thank Emmerich Welzl for discussions on Theorem 2.7. We also
thank Friedrich Huber for implementing the \r\nconstruction of arrangements in arbitrary
dimensions, and Gerd Stoeckl for implementing the algorithms presented in §§\r\n4.1
and 4.3. The third author wishes to thank Jack Edmonds for the many enlightening
discussions.\r\n"
article_processing_charge: No
article_type: original
author:
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
- first_name: Joseph
full_name: O'Rourke, Joseph
last_name: O'Rourke
- first_name: Raimund
full_name: Seidel, Raimund
last_name: Seidel
citation:
ama: Edelsbrunner H, O’Rourke J, Seidel R. Constructing arrangements of lines and
hyperplanes with applications. SIAM Journal on Computing. 1986;15(2):341-363.
doi:10.1137/0215024
apa: Edelsbrunner, H., O’Rourke, J., & Seidel, R. (1986). Constructing arrangements
of lines and hyperplanes with applications. SIAM Journal on Computing.
SIAM. https://doi.org/10.1137/0215024
chicago: Edelsbrunner, Herbert, Joseph O’Rourke, and Raimund Seidel. “Constructing
Arrangements of Lines and Hyperplanes with Applications.” SIAM Journal on Computing.
SIAM, 1986. https://doi.org/10.1137/0215024.
ieee: H. Edelsbrunner, J. O’Rourke, and R. Seidel, “Constructing arrangements of
lines and hyperplanes with applications,” SIAM Journal on Computing, vol.
15, no. 2. SIAM, pp. 341–363, 1986.
ista: Edelsbrunner H, O’Rourke J, Seidel R. 1986. Constructing arrangements of lines
and hyperplanes with applications. SIAM Journal on Computing. 15(2), 341–363.
mla: Edelsbrunner, Herbert, et al. “Constructing Arrangements of Lines and Hyperplanes
with Applications.” SIAM Journal on Computing, vol. 15, no. 2, SIAM, 1986,
pp. 341–63, doi:10.1137/0215024.
short: H. Edelsbrunner, J. O’Rourke, R. Seidel, SIAM Journal on Computing 15 (1986)
341–363.
date_created: 2018-12-11T12:06:58Z
date_published: 1986-01-01T00:00:00Z
date_updated: 2022-02-01T11:03:07Z
day: '01'
doi: 10.1137/0215024
extern: '1'
intvolume: ' 15'
issue: '2'
language:
- iso: eng
month: '01'
oa_version: None
page: 341 - 363
publication: SIAM Journal on Computing
publication_identifier:
eissn:
- 1095-7111
issn:
- 0097-5397
publication_status: published
publisher: SIAM
publist_id: '2017'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Constructing arrangements of lines and hyperplanes with applications
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 15
year: '1986'
...
---
_id: '4106'
abstract:
- lang: eng
text: 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.
article_processing_charge: No
article_type: original
author:
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
- first_name: Roman
full_name: Waupotitsch, Roman
last_name: Waupotitsch
citation:
ama: Edelsbrunner H, Waupotitsch R. Computing a ham-sandwich cut in two dimensions.
Journal of Symbolic Computation. 1986;2(2):171-178. doi:10.1016/S0747-7171(86)80020-7
apa: Edelsbrunner, H., & Waupotitsch, R. (1986). Computing a ham-sandwich cut
in two dimensions. Journal of Symbolic Computation. Elsevier. https://doi.org/10.1016/S0747-7171(86)80020-7
chicago: Edelsbrunner, Herbert, and Roman Waupotitsch. “Computing a Ham-Sandwich
Cut in Two Dimensions.” Journal of Symbolic Computation. Elsevier, 1986.
https://doi.org/10.1016/S0747-7171(86)80020-7.
ieee: H. Edelsbrunner and R. Waupotitsch, “Computing a ham-sandwich cut in two dimensions,”
Journal of Symbolic Computation, vol. 2, no. 2. Elsevier, pp. 171–178,
1986.
ista: Edelsbrunner H, Waupotitsch R. 1986. Computing a ham-sandwich cut in two dimensions.
Journal of Symbolic Computation. 2(2), 171–178.
mla: Edelsbrunner, Herbert, and Roman Waupotitsch. “Computing a Ham-Sandwich Cut
in Two Dimensions.” Journal of Symbolic Computation, vol. 2, no. 2, Elsevier,
1986, pp. 171–78, doi:10.1016/S0747-7171(86)80020-7.
short: H. Edelsbrunner, R. Waupotitsch, Journal of Symbolic Computation 2 (1986)
171–178.
date_created: 2018-12-11T12:06:58Z
date_published: 1986-01-01T00:00:00Z
date_updated: 2022-02-01T11:22:59Z
day: '01'
doi: 10.1016/S0747-7171(86)80020-7
extern: '1'
intvolume: ' 2'
issue: '2'
language:
- iso: eng
month: '01'
oa_version: None
page: 171 - 178
publication: Journal of Symbolic Computation
publication_identifier:
eissn:
- 1095-855X
issn:
- 0747-7171
publication_status: published
publisher: Elsevier
publist_id: '2018'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Computing a ham-sandwich cut in two dimensions
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 2
year: '1986'
...
---
_id: '4107'
abstract:
- lang: eng
text: 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.
acknowledgement: 'Research reported in the paper was conducted while the second author
was visiting the Technical University of Graz. Support provided by the Technical
University for this visit is gratefully acknowledged. '
article_processing_charge: No
article_type: original
author:
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
- first_name: David
full_name: Haussler, David
last_name: Haussler
citation:
ama: Edelsbrunner H, Haussler D. The complexity of cells in 3-dimensional arrangements.
Discrete Mathematics. 1986;60(C):139-146. doi:10.1016/0012-365X(86)90008-7
apa: Edelsbrunner, H., & Haussler, D. (1986). The complexity of cells in 3-dimensional
arrangements. Discrete Mathematics. Elsevier. https://doi.org/10.1016/0012-365X(86)90008-7
chicago: Edelsbrunner, Herbert, and David Haussler. “The Complexity of Cells in
3-Dimensional Arrangements.” Discrete Mathematics. Elsevier, 1986. https://doi.org/10.1016/0012-365X(86)90008-7.
ieee: H. Edelsbrunner and D. Haussler, “The complexity of cells in 3-dimensional
arrangements,” Discrete Mathematics, vol. 60, no. C. Elsevier, pp. 139–146,
1986.
ista: Edelsbrunner H, Haussler D. 1986. The complexity of cells in 3-dimensional
arrangements. Discrete Mathematics. 60(C), 139–146.
mla: Edelsbrunner, Herbert, and David Haussler. “The Complexity of Cells in 3-Dimensional
Arrangements.” Discrete Mathematics, vol. 60, no. C, Elsevier, 1986, pp.
139–46, doi:10.1016/0012-365X(86)90008-7.
short: H. Edelsbrunner, D. Haussler, Discrete Mathematics 60 (1986) 139–146.
date_created: 2018-12-11T12:06:59Z
date_published: 1986-06-01T00:00:00Z
date_updated: 2022-02-01T12:44:50Z
day: '01'
doi: 10.1016/0012-365X(86)90008-7
extern: '1'
intvolume: ' 60'
issue: C
language:
- iso: eng
month: '06'
oa_version: None
page: 139 - 146
publication: Discrete Mathematics
publication_identifier:
eissn:
- 1872-681X
issn:
- 0012-365X
publication_status: published
publisher: Elsevier
publist_id: '2019'
quality_controlled: '1'
status: public
title: The complexity of cells in 3-dimensional arrangements
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 60
year: '1986'
...
---
_id: '4108'
abstract:
- lang: eng
text: 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.
acknowledgement: 'We would like to thank John Gilbert for his careful reading of the
manuscript and his many suggestions for improvement. We also want to thank Bennett
Battaile, Gianfranco Bilardi, Joseph O''Rourke, and Chee Yap for their comments. '
article_processing_charge: No
article_type: original
author:
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
- first_name: Raimund
full_name: Seidel, Raimund
last_name: Seidel
citation:
ama: Edelsbrunner H, Seidel R. Voronoi diagrams and arrangements. Discrete &
Computational Geometry. 1986;1(1):25-44. doi:10.1007/BF02187681
apa: Edelsbrunner, H., & Seidel, R. (1986). Voronoi diagrams and arrangements.
Discrete & Computational Geometry. Springer. https://doi.org/10.1007/BF02187681
chicago: Edelsbrunner, Herbert, and Raimund Seidel. “Voronoi Diagrams and Arrangements.”
Discrete & Computational Geometry. Springer, 1986. https://doi.org/10.1007/BF02187681.
ieee: H. Edelsbrunner and R. Seidel, “Voronoi diagrams and arrangements,” Discrete
& Computational Geometry, vol. 1, no. 1. Springer, pp. 25–44, 1986.
ista: Edelsbrunner H, Seidel R. 1986. Voronoi diagrams and arrangements. Discrete
& Computational Geometry. 1(1), 25–44.
mla: Edelsbrunner, Herbert, and Raimund Seidel. “Voronoi Diagrams and Arrangements.”
Discrete & Computational Geometry, vol. 1, no. 1, Springer, 1986, pp.
25–44, doi:10.1007/BF02187681.
short: H. Edelsbrunner, R. Seidel, Discrete & Computational Geometry 1 (1986)
25–44.
date_created: 2018-12-11T12:06:59Z
date_published: 1986-01-01T00:00:00Z
date_updated: 2022-02-01T08:53:39Z
day: '01'
doi: 10.1007/BF02187681
extern: '1'
intvolume: ' 1'
issue: '1'
language:
- iso: eng
month: '01'
oa_version: None
page: 25 - 44
publication: Discrete & Computational Geometry
publication_identifier:
eissn:
- 1432-0444
issn:
- 0179-5376
publication_status: published
publisher: Springer
publist_id: '2012'
quality_controlled: '1'
status: public
title: Voronoi diagrams and arrangements
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 1
year: '1986'
...
---
_id: '4109'
abstract:
- lang: eng
text: 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.
article_processing_charge: No
article_type: original
author:
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
- first_name: Günter
full_name: Haring, Günter
last_name: Haring
- first_name: D
full_name: Hilbert, D
last_name: Hilbert
citation:
ama: Edelsbrunner H, Haring G, Hilbert D. Rectangular point location in d-dimensions
with applications. Computer Journal. 1986;29(1):76-82. doi:10.1093/comjnl/29.1.76
apa: Edelsbrunner, H., Haring, G., & Hilbert, D. (1986). Rectangular point location
in d-dimensions with applications. Computer Journal. Oxford University
Press. https://doi.org/10.1093/comjnl/29.1.76
chicago: Edelsbrunner, Herbert, Günter Haring, and D Hilbert. “Rectangular Point
Location in D-Dimensions with Applications.” Computer Journal. Oxford University
Press, 1986. https://doi.org/10.1093/comjnl/29.1.76.
ieee: H. Edelsbrunner, G. Haring, and D. Hilbert, “Rectangular point location in
d-dimensions with applications,” Computer Journal, vol. 29, no. 1. Oxford
University Press, pp. 76–82, 1986.
ista: Edelsbrunner H, Haring G, Hilbert D. 1986. Rectangular point location in d-dimensions
with applications. Computer Journal. 29(1), 76–82.
mla: Edelsbrunner, Herbert, et al. “Rectangular Point Location in D-Dimensions with
Applications.” Computer Journal, vol. 29, no. 1, Oxford University Press,
1986, pp. 76–82, doi:10.1093/comjnl/29.1.76.
short: H. Edelsbrunner, G. Haring, D. Hilbert, Computer Journal 29 (1986) 76–82.
date_created: 2018-12-11T12:06:59Z
date_published: 1986-01-01T00:00:00Z
date_updated: 2022-02-01T09:17:51Z
day: '01'
doi: 10.1093/comjnl/29.1.76
extern: '1'
intvolume: ' 29'
issue: '1'
language:
- iso: eng
month: '01'
oa_version: None
page: 76 - 82
publication: Computer Journal
publication_identifier:
eissn:
- 1460-2067
issn:
- 0010-4620
publication_status: published
publisher: Oxford University Press
publist_id: '2013'
quality_controlled: '1'
status: public
title: Rectangular point location in d-dimensions with applications
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 29
year: '1986'
...
---
_id: '4110'
abstract:
- lang: eng
text: 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.
article_processing_charge: No
article_type: original
author:
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
- first_name: Emo
full_name: Welzl, Emo
last_name: Welzl
citation:
ama: Edelsbrunner H, Welzl E. Constructing belts in two-dimensional arrangements
with applications. SIAM Journal on Computing. 1986;15(1):271-284. doi:10.1137/0215019
apa: Edelsbrunner, H., & Welzl, E. (1986). Constructing belts in two-dimensional
arrangements with applications. SIAM Journal on Computing. SIAM. https://doi.org/10.1137/0215019
chicago: Edelsbrunner, Herbert, and Emo Welzl. “Constructing Belts in Two-Dimensional
Arrangements with Applications.” SIAM Journal on Computing. SIAM, 1986.
https://doi.org/10.1137/0215019.
ieee: H. Edelsbrunner and E. Welzl, “Constructing belts in two-dimensional arrangements
with applications,” SIAM Journal on Computing, vol. 15, no. 1. SIAM, pp.
271–284, 1986.
ista: Edelsbrunner H, Welzl E. 1986. Constructing belts in two-dimensional arrangements
with applications. SIAM Journal on Computing. 15(1), 271–284.
mla: Edelsbrunner, Herbert, and Emo Welzl. “Constructing Belts in Two-Dimensional
Arrangements with Applications.” SIAM Journal on Computing, vol. 15, no.
1, SIAM, 1986, pp. 271–84, doi:10.1137/0215019.
short: H. Edelsbrunner, E. Welzl, SIAM Journal on Computing 15 (1986) 271–284.
date_created: 2018-12-11T12:07:00Z
date_published: 1986-01-01T00:00:00Z
date_updated: 2022-02-01T09:34:20Z
day: '01'
doi: 10.1137/0215019
extern: '1'
intvolume: ' 15'
issue: '1'
language:
- iso: eng
month: '01'
oa_version: None
page: 271 - 284
publication: SIAM Journal on Computing
publication_identifier:
eissn:
- 1095-7111
issn:
- 0097-5397
publication_status: published
publisher: SIAM
publist_id: '2014'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Constructing belts in two-dimensional arrangements with applications
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 15
year: '1986'
...
---
_id: '4321'
abstract:
- lang: eng
text: 'The fire-bellied toads Bombina bombina and B. variegata differ extensively
in biochemistry, morphology, and behavior. We use a survey of five diagnostic
enzyme loci across the hybrid zone near Cracow in Southern Poland to estimate
the dispersal rate, selection pressures, and numbers of loci which maintain this
zone. The enzyme clines coincide closely with each other and with morphological
and mitochondrial DNA clines. Although the zone lies on a broad transition between
environments suitable for bombina and variegata, the close concordance of diverse
characters, together with increased aberrations and mortality in hybrids, suggest
that the zone is maintained largely by selection against hybrids. There are strong
“linkage disequilibria” between each pair of (unlinked) enzyme loci (R̄ = 0.129
[2-unit support limits: 0.119–0.139]). These are probably caused by gene flow
into the zone, and they give an estimate of dispersal (σ = 890 [790–940] m gen−½).
The clines are sharply stepped, with most of the change occurring within 6.15
(5.45–6.45) km, but with long tails of introgression on either side. This implies
that the effective selection pressure on each enzyme marker (due largely to disequilibrium
with other loci) is s* = 0.17 (0.159–0.181) at the center but that the selection
acting directly on the enzyme loci is weak or zero (se < 0.0038). The stepped
pattern implies a barrier to gene flow of 220 (48–415) km. This would substantially
delay neutral introgression but would have little effect on advantageous alleles;
the two taxa need not evolve independently. Strong selection is needed to maintain
such a barrier: hybrid populations must have their mean fitness reduced by a factor
of 0.65 (0.60–0.77). This selection must be spread over a large number of loci
to account for the concordant patterns and the observed cline widths (N = 300
[80–2,000]).'
acknowledgement: 'We are grateful to J. Mitton and W. P. Hall for their suggestions
and help with earlier versions of the statistical analysis. The manuscript was much
improved by the helpful comments of Dorothy Currie, Gunther Gollmann, Godfrey Hewitt,
Julian MacLean, and Jim Mallet. Thanks are also due to Tina Tsang for her careful
typing. This work was supported by the Exchange Agreement between the Polish Academy
of Sciences and the Royal Society, and by grants from the Polish Academy of Sciences
(project MR-II/6), the Royal Society, the Nuffield Foundation, and the Science
and Engineering Research Council. '
article_processing_charge: No
article_type: original
author:
- first_name: Jacek
full_name: Szymura, Jacek
last_name: Szymura
- first_name: Nicholas H
full_name: Barton, Nicholas H
id: 4880FE40-F248-11E8-B48F-1D18A9856A87
last_name: Barton
orcid: 0000-0002-8548-5240
citation:
ama: Szymura J, Barton NH. Genetic analysis of a hybrid zone between the fire-bellied
toads Bombina bombina and B. variegata, near Cracow in Southern Poland. Evolution;
International Journal of Organic Evolution. 1986;40:1141-1159. doi:10.1111/j.1558-5646.1986.tb05740.x
apa: Szymura, J., & Barton, N. H. (1986). Genetic analysis of a hybrid zone
between the fire-bellied toads Bombina bombina and B. variegata, near Cracow in
Southern Poland. Evolution; International Journal of Organic Evolution.
Society for the Study of Evolution. https://doi.org/10.1111/j.1558-5646.1986.tb05740.x
chicago: Szymura, Jacek, and Nicholas H Barton. “Genetic Analysis of a Hybrid Zone
between the Fire-Bellied Toads Bombina Bombina and B. Variegata, near Cracow in
Southern Poland.” Evolution; International Journal of Organic Evolution.
Society for the Study of Evolution, 1986. https://doi.org/10.1111/j.1558-5646.1986.tb05740.x.
ieee: J. Szymura and N. H. Barton, “Genetic analysis of a hybrid zone between the
fire-bellied toads Bombina bombina and B. variegata, near Cracow in Southern Poland,”
Evolution; International Journal of Organic Evolution, vol. 40. Society
for the Study of Evolution, pp. 1141–1159, 1986.
ista: Szymura J, Barton NH. 1986. Genetic analysis of a hybrid zone between the
fire-bellied toads Bombina bombina and B. variegata, near Cracow in Southern Poland.
Evolution; International Journal of Organic Evolution. 40, 1141–1159.
mla: Szymura, Jacek, and Nicholas H. Barton. “Genetic Analysis of a Hybrid Zone
between the Fire-Bellied Toads Bombina Bombina and B. Variegata, near Cracow in
Southern Poland.” Evolution; International Journal of Organic Evolution,
vol. 40, Society for the Study of Evolution, 1986, pp. 1141–59, doi:10.1111/j.1558-5646.1986.tb05740.x.
short: J. Szymura, N.H. Barton, Evolution; International Journal of Organic Evolution
40 (1986) 1141–1159.
date_created: 2018-12-11T12:08:14Z
date_published: 1986-01-01T00:00:00Z
date_updated: 2022-01-31T15:31:37Z
day: '01'
doi: 10.1111/j.1558-5646.1986.tb05740.x
extern: '1'
intvolume: ' 40'
language:
- iso: eng
month: '01'
oa_version: None
page: 1141 - 1159
publication: Evolution; International Journal of Organic Evolution
publication_identifier:
eissn:
- 1558-5646
issn:
- 0014-3820
publication_status: published
publisher: Society for the Study of Evolution
publist_id: '1724'
quality_controlled: '1'
status: public
title: Genetic analysis of a hybrid zone between the fire-bellied toads Bombina bombina
and B. variegata, near Cracow in Southern Poland
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 40
year: '1986'
...
---
_id: '4323'
abstract:
- lang: eng
text: 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.
acknowledgement: "We would like to thank M. Bulmer for his helpful comments. R. J.
Post was supported during this work by an MRC Postdoctoral Fellowship, and N. Barton
by an SRC Postdoctoral Fellowship. \r\n"
article_processing_charge: No
article_type: original
author:
- first_name: Nicholas H
full_name: Barton, Nicholas H
id: 4880FE40-F248-11E8-B48F-1D18A9856A87
last_name: Barton
orcid: 0000-0002-8548-5240
- first_name: R.J.
full_name: Post, R.J.
last_name: Post
citation:
ama: Barton NH, Post RJ. Sibling competition and the advantage of mixed families.
Journal of Theoretical Biology. 1986;120(4):381-387. doi:10.1016/S0022-5193(86)80033-9
apa: Barton, N. H., & Post, R. J. (1986). Sibling competition and the advantage
of mixed families. Journal of Theoretical Biology. Elsevier. https://doi.org/10.1016/S0022-5193(86)80033-9
chicago: Barton, Nicholas H, and R.J. Post. “Sibling Competition and the Advantage
of Mixed Families.” Journal of Theoretical Biology. Elsevier, 1986. https://doi.org/10.1016/S0022-5193(86)80033-9.
ieee: N. H. Barton and R. J. Post, “Sibling competition and the advantage of mixed
families,” Journal of Theoretical Biology, vol. 120, no. 4. Elsevier, pp.
381–387, 1986.
ista: Barton NH, Post RJ. 1986. Sibling competition and the advantage of mixed families.
Journal of Theoretical Biology. 120(4), 381–387.
mla: Barton, Nicholas H., and R. J. Post. “Sibling Competition and the Advantage
of Mixed Families.” Journal of Theoretical Biology, vol. 120, no. 4, Elsevier,
1986, pp. 381–87, doi:10.1016/S0022-5193(86)80033-9.
short: N.H. Barton, R.J. Post, Journal of Theoretical Biology 120 (1986) 381–387.
date_created: 2018-12-11T12:08:15Z
date_published: 1986-06-21T00:00:00Z
date_updated: 2022-01-31T14:44:50Z
day: '21'
doi: 10.1016/S0022-5193(86)80033-9
extern: '1'
intvolume: ' 120'
issue: '4'
language:
- iso: eng
month: '06'
oa_version: None
page: 381 - 387
publication: Journal of Theoretical Biology
publication_identifier:
eissn:
- 1095-8541
issn:
- 0022-5193
publication_status: published
publisher: Elsevier
publist_id: '1720'
quality_controlled: '1'
status: public
title: Sibling competition and the advantage of mixed families
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 120
year: '1986'
...
---
_id: '4324'
abstract:
- lang: eng
text: 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.
acknowledgement: Thanks are due to J. Felsenstein, J. Gillespie, S. Rouhani, M. Slatkin,
and M. Turelli for stimulating discussions, and for their comments on the manuscript.
This work was sup- ported by a travel grant from the Royal Society, and by a research
grant from the SERC
article_processing_charge: No
article_type: original
author:
- first_name: Nicholas H
full_name: Barton, Nicholas H
id: 4880FE40-F248-11E8-B48F-1D18A9856A87
last_name: Barton
orcid: 0000-0002-8548-5240
citation:
ama: Barton NH. The maintenance of polygenic variation through a balance between
mutation and stabilising selection. Genetical Research. 1986;47(3):209-216.
doi:10.1017/S0016672300023156
apa: Barton, N. H. (1986). The maintenance of polygenic variation through a balance
between mutation and stabilising selection. Genetical Research. Cambridge
University Press. https://doi.org/10.1017/S0016672300023156
chicago: Barton, Nicholas H. “The Maintenance of Polygenic Variation through a Balance
between Mutation and Stabilising Selection.” Genetical Research. Cambridge
University Press, 1986. https://doi.org/10.1017/S0016672300023156.
ieee: N. H. Barton, “The maintenance of polygenic variation through a balance between
mutation and stabilising selection,” Genetical Research, vol. 47, no. 3.
Cambridge University Press, pp. 209–216, 1986.
ista: Barton NH. 1986. The maintenance of polygenic variation through a balance
between mutation and stabilising selection. Genetical Research. 47(3), 209–216.
mla: Barton, Nicholas H. “The Maintenance of Polygenic Variation through a Balance
between Mutation and Stabilising Selection.” Genetical Research, vol. 47,
no. 3, Cambridge University Press, 1986, pp. 209–16, doi:10.1017/S0016672300023156.
short: N.H. Barton, Genetical Research 47 (1986) 209–216.
date_created: 2018-12-11T12:08:15Z
date_published: 1986-06-01T00:00:00Z
date_updated: 2022-01-31T14:31:48Z
day: '01'
doi: 10.1017/S0016672300023156
extern: '1'
external_id:
pmid:
- '3744046'
intvolume: ' 47'
issue: '3'
language:
- iso: eng
month: '06'
oa_version: None
page: 209 - 216
pmid: 1
publication: Genetical Research
publication_identifier:
eissn:
- 1469-5073
issn:
- 0016-6723
publication_status: published
publisher: Cambridge University Press
publist_id: '1718'
quality_controlled: '1'
status: public
title: The maintenance of polygenic variation through a balance between mutation and
stabilising selection
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 47
year: '1986'
...