---
_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'
...
---
_id: '4111'
abstract:
- lang: eng
text: 'This paper describes an optimal solution for the following geometric search
problem defined for a set P of n points in three dimensions: Given a plane h with
all points of P on one side and a line ℓ in h, determine a point of P that is
hit first when h is rotated around ℓ. The solution takes O(n) space and O(log
n) time for a query. By use of geometric transforms, the post-office problem for
a finite set of points in two dimensions and certain two-dimensional point location
problems are reduced to the former problem and thus also optimally solved.'
acknowledgement: "Research reported in this paper was partially supported by the Austrian
Fonds zur Förderung tier wissenschaftlichen\r\nForschung. \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: Hermann
full_name: Maurer, Hermann
last_name: Maurer
citation:
ama: Edelsbrunner H, Maurer H. Finding extreme-points in 3-dimensions and solving
the post-office problem in the plane. Information Processing Letters. 1985;21(1):39-47.
doi:10.1016/0020-0190(85)90107-3
apa: Edelsbrunner, H., & Maurer, H. (1985). Finding extreme-points in 3-dimensions
and solving the post-office problem in the plane. Information Processing Letters.
Elsevier. https://doi.org/10.1016/0020-0190(85)90107-3
chicago: Edelsbrunner, Herbert, and Hermann Maurer. “Finding Extreme-Points in 3-Dimensions
and Solving the Post-Office Problem in the Plane.” Information Processing Letters.
Elsevier, 1985. https://doi.org/10.1016/0020-0190(85)90107-3.
ieee: H. Edelsbrunner and H. Maurer, “Finding extreme-points in 3-dimensions and
solving the post-office problem in the plane,” Information Processing Letters,
vol. 21, no. 1. Elsevier, pp. 39–47, 1985.
ista: Edelsbrunner H, Maurer H. 1985. Finding extreme-points in 3-dimensions and
solving the post-office problem in the plane. Information Processing Letters.
21(1), 39–47.
mla: Edelsbrunner, Herbert, and Hermann Maurer. “Finding Extreme-Points in 3-Dimensions
and Solving the Post-Office Problem in the Plane.” Information Processing Letters,
vol. 21, no. 1, Elsevier, 1985, pp. 39–47, doi:10.1016/0020-0190(85)90107-3.
short: H. Edelsbrunner, H. Maurer, Information Processing Letters 21 (1985) 39–47.
date_created: 2018-12-11T12:07:00Z
date_published: 1985-07-10T00:00:00Z
date_updated: 2022-01-31T12:49:12Z
day: '10'
doi: 10.1016/0020-0190(85)90107-3
extern: '1'
intvolume: ' 21'
issue: '1'
language:
- iso: eng
month: '07'
oa_version: None
page: 39 - 47
publication: Information Processing Letters
publication_identifier:
eissn:
- 1872-6119
issn:
- 0020-0190
publication_status: published
publisher: Elsevier
publist_id: '2009'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Finding extreme-points in 3-dimensions and solving the post-office problem
in the plane
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 21
year: '1985'
...
---
_id: '4112'
abstract:
- lang: eng
text: 'The batched static version of a searching problem asks for performing a given
set of queries on a given set of objects. All queries are known in advance. The
batched dynamic version of a searching problem is the following: given a sequence
of insertions, deletions, and queries, perform them on an initially empty set.
We will develop methods for solving batched static and batched dynamic versions
of searching problems which are in particular applicable to decomposable searching
problems. The techniques show that batched static (dynamic) versions of searching
problems can often be solved more efficiently than by using known static (dynamic)
data structures. In particular, a technique called “streaming” is described that
reduces the space requirements considerably. The methods have also a number of
applications on set problems. E.g., the k intersecting pairs in a set of n axis-parallel
hyper-rectangles in d dimensions can be reported in O (nlogd−1n + k) time using
only O(n) space.'
acknowledgement: "Research reported in this paper was done while the second author
visited the University of Graz. The first author was supported by the Austrian Fonds
zur Förderung der Wissenschaftlichen Forschung. The second author was supported
by the Netherlands Organization for the Advancement of Pure Research (ZWO). \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: Mark
full_name: Overmars, Mark
last_name: Overmars
citation:
ama: Edelsbrunner H, Overmars M. Batched dynamic solutions to decomposable searching
problems. Journal of Algorithms. 1985;6(4):515-542. doi:10.1016/0196-6774(85)90030-6
apa: Edelsbrunner, H., & Overmars, M. (1985). Batched dynamic solutions to decomposable
searching problems. Journal of Algorithms. Elsevier. https://doi.org/10.1016/0196-6774(85)90030-6
chicago: Edelsbrunner, Herbert, and Mark Overmars. “Batched Dynamic Solutions to
Decomposable Searching Problems.” Journal of Algorithms. Elsevier, 1985.
https://doi.org/10.1016/0196-6774(85)90030-6.
ieee: H. Edelsbrunner and M. Overmars, “Batched dynamic solutions to decomposable
searching problems,” Journal of Algorithms, vol. 6, no. 4. Elsevier, pp.
515–542, 1985.
ista: Edelsbrunner H, Overmars M. 1985. Batched dynamic solutions to decomposable
searching problems. Journal of Algorithms. 6(4), 515–542.
mla: Edelsbrunner, Herbert, and Mark Overmars. “Batched Dynamic Solutions to Decomposable
Searching Problems.” Journal of Algorithms, vol. 6, no. 4, Elsevier, 1985,
pp. 515–42, doi:10.1016/0196-6774(85)90030-6.
short: H. Edelsbrunner, M. Overmars, Journal of Algorithms 6 (1985) 515–542.
date_created: 2018-12-11T12:07:00Z
date_published: 1985-12-01T00:00:00Z
date_updated: 2022-01-31T13:36:56Z
day: '01'
doi: 10.1016/0196-6774(85)90030-6
extern: '1'
intvolume: ' 6'
issue: '4'
language:
- iso: eng
month: '12'
oa_version: None
page: 515 - 542
publication: Journal of Algorithms
publication_identifier:
eissn:
- 1090-2678
issn:
- 0196-6774
publication_status: published
publisher: Elsevier
publist_id: '2010'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Batched dynamic solutions to decomposable searching problems
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 6
year: '1985'
...
---
_id: '4113'
abstract:
- lang: eng
text: Let S denote a set of n points in the Euclidean plane. A subset S′ of S is
termed a k-set of S if it contains k points and there exists a straight line which
has no point of S on it and separates S′ from S−S′. We let fk(n) denote the maximum
number of k-sets which can be realized by a set of n points. This paper studies
the asymptotic behaviour of fk(n) as this function has applications to a number
of problems in computational geometry. A lower and an upper bound on fk(n) is
established. Both are nontrivial and improve bounds known before. In particular, is
shown by exhibiting special point-sets which realize that many k-sets. In addition, is
proved by the study of a combinatorial problem which is of interest in its own
right.
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. On the number of line separations of a finite set
in the plane. Journal of Combinatorial Theory Series A. 1985;38(1):15-29.
doi:10.1016/0097-3165(85)90017-2
apa: Edelsbrunner, H., & Welzl, E. (1985). On the number of line separations
of a finite set in the plane. Journal of Combinatorial Theory Series A.
Elsevier. https://doi.org/10.1016/0097-3165(85)90017-2
chicago: Edelsbrunner, Herbert, and Emo Welzl. “On the Number of Line Separations
of a Finite Set in the Plane.” Journal of Combinatorial Theory Series A.
Elsevier, 1985. https://doi.org/10.1016/0097-3165(85)90017-2.
ieee: H. Edelsbrunner and E. Welzl, “On the number of line separations of a finite
set in the plane,” Journal of Combinatorial Theory Series A, vol. 38, no.
1. Elsevier, pp. 15–29, 1985.
ista: Edelsbrunner H, Welzl E. 1985. On the number of line separations of a finite
set in the plane. Journal of Combinatorial Theory Series A. 38(1), 15–29.
mla: Edelsbrunner, Herbert, and Emo Welzl. “On the Number of Line Separations of
a Finite Set in the Plane.” Journal of Combinatorial Theory Series A, vol.
38, no. 1, Elsevier, 1985, pp. 15–29, doi:10.1016/0097-3165(85)90017-2.
short: H. Edelsbrunner, E. Welzl, Journal of Combinatorial Theory Series A 38 (1985)
15–29.
date_created: 2018-12-11T12:07:01Z
date_published: 1985-01-01T00:00:00Z
date_updated: 2022-01-31T14:14:25Z
day: '01'
doi: 10.1016/0097-3165(85)90017-2
extern: '1'
intvolume: ' 38'
issue: '1'
language:
- iso: eng
month: '01'
oa_version: None
page: 15 - 29
publication: Journal of Combinatorial Theory Series A
publication_identifier:
eissn:
- 1096-0899
issn:
- 0097-3165
publication_status: published
publisher: Elsevier
publist_id: '2011'
quality_controlled: '1'
scopus_import: '1'
status: public
title: On the number of line separations of a finite set in the plane
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 38
year: '1985'
...
---
_id: '4114'
abstract:
- lang: eng
text: Proportional link linkage (PLL) clustering methods are a parametric family
of monotone invariant agglomerative hierarchical clustering methods. This family
includes the single, minimedian, and complete linkage clustering methods as special
cases; its members are used in psychological and ecological applications. Since
the literature on clustering space distortion is oriented to quantitative input
data, we adapt its basic concepts to input data with only ordinal significance
and analyze the space distortion properties of PLL methods. To enable PLL methods
to be used when the numbern of objects being clustered is large, we describe an
efficient PLL algorithm that operates inO(n 2 logn) time andO(n 2) space
acknowledgement: This work was partially supported by the Natural Sciences and Engineering
Research Council of Canada and by the Austrian Fonds zur Förderung der wissenschaftlichen
Forschung.
article_processing_charge: No
article_type: original
author:
- first_name: William
full_name: Day, William
last_name: Day
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
citation:
ama: Day W, Edelsbrunner H. Investigation of Proportional Link Linkage Clustering
Methods. Journal of Classification. 1985;2(2-3):239-254. doi:10.1007/BF01908077
apa: Day, W., & Edelsbrunner, H. (1985). Investigation of Proportional Link
Linkage Clustering Methods. Journal of Classification. Springer. https://doi.org/10.1007/BF01908077
chicago: Day, William, and Herbert Edelsbrunner. “Investigation of Proportional
Link Linkage Clustering Methods.” Journal of Classification. Springer,
1985. https://doi.org/10.1007/BF01908077.
ieee: W. Day and H. Edelsbrunner, “Investigation of Proportional Link Linkage Clustering
Methods,” Journal of Classification, vol. 2, no. 2–3. Springer, pp. 239–254,
1985.
ista: Day W, Edelsbrunner H. 1985. Investigation of Proportional Link Linkage Clustering
Methods. Journal of Classification. 2(2–3), 239–254.
mla: Day, William, and Herbert Edelsbrunner. “Investigation of Proportional Link
Linkage Clustering Methods.” Journal of Classification, vol. 2, no. 2–3,
Springer, 1985, pp. 239–54, doi:10.1007/BF01908077.
short: W. Day, H. Edelsbrunner, Journal of Classification 2 (1985) 239–254.
date_created: 2018-12-11T12:07:01Z
date_published: 1985-12-01T00:00:00Z
date_updated: 2022-01-31T10:37:13Z
day: '01'
doi: 10.1007/BF01908077
extern: '1'
intvolume: ' 2'
issue: 2-3
language:
- iso: eng
month: '12'
oa_version: None
page: 239 - 254
publication: Journal of Classification
publication_identifier:
eissn:
- 1432-1343
issn:
- 0176-4268
publication_status: published
publisher: Springer
publist_id: '2006'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Investigation of Proportional Link Linkage Clustering Methods
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 2
year: '1985'
...
---
_id: '4115'
abstract:
- lang: eng
text: A polygon in the plane is convex if it contains all line segments connecting
any two of its points. Let P and Q denote two convex polygons. The computational
complexity of finding the minimum and maximum distance possible between two points
p in P and q in Q is studied. An algorithm is described that determines the minimum
distance (together with points p and q that realize it) in O(logm + logn) time,
where m and n denote the number of vertices of P and Q, respectively. This is
optimal in the worst case. For computing the maximum distance, a lower bound Ω(m
+ n) is proved. This bound is also shown to be best possible by establishing an
upper bound of O(m + 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
citation:
ama: Edelsbrunner H. Computing the extreme distances between two convex polygons.
Journal of Algorithms. 1985;6(2):213-224. doi:10.1016/0196-6774(85)90039-2
apa: Edelsbrunner, H. (1985). Computing the extreme distances between two convex
polygons. Journal of Algorithms. Academic Press. https://doi.org/10.1016/0196-6774(85)90039-2
chicago: Edelsbrunner, Herbert. “Computing the Extreme Distances between Two Convex
Polygons.” Journal of Algorithms. Academic Press, 1985. https://doi.org/10.1016/0196-6774(85)90039-2.
ieee: H. Edelsbrunner, “Computing the extreme distances between two convex polygons,”
Journal of Algorithms, vol. 6, no. 2. Academic Press, pp. 213–224, 1985.
ista: Edelsbrunner H. 1985. Computing the extreme distances between two convex polygons.
Journal of Algorithms. 6(2), 213–224.
mla: Edelsbrunner, Herbert. “Computing the Extreme Distances between Two Convex
Polygons.” Journal of Algorithms, vol. 6, no. 2, Academic Press, 1985,
pp. 213–24, doi:10.1016/0196-6774(85)90039-2.
short: H. Edelsbrunner, Journal of Algorithms 6 (1985) 213–224.
date_created: 2018-12-11T12:07:01Z
date_published: 1985-06-01T00:00:00Z
date_updated: 2022-01-31T10:44:41Z
day: '01'
doi: 10.1016/0196-6774(85)90039-2
extern: '1'
intvolume: ' 6'
issue: '2'
language:
- iso: eng
month: '06'
oa_version: None
page: 213 - 224
publication: Journal of Algorithms
publication_identifier:
eissn:
- 1090-2678
issn:
- 0196-6774
publication_status: published
publisher: Academic Press
publist_id: '2007'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Computing the extreme distances between two convex polygons
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 6
year: '1985'
...
---
_id: '4116'
abstract:
- lang: eng
text: 'A straight line that intersects all members of a set S of objects in the
real plane is called a transversal of S. Geometric transforms are described that
reduce transversal problems for various types of objects to convex hull problems
for points. These reductions lead to efficient algorithms for finding transversals
which are also described. Applications of the algorithms are found in computer
graphics: “Reproduce the line displayed by a collection of pixels”, and in statistics:
“Find the line that minimizes the maximum distance from a collection of (weighted)
points in the plane”.'
acknowledgement: 'The author gratefully acknowledges the criticism of an anonymous
referee who discovered a serious flaw in an earlier version 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
citation:
ama: Edelsbrunner H. Finding Transversals for Sets of Simple Geometric-Figures.
Theoretical Computer Science. 1985;35(1):55-69. doi:10.1016/0304-3975(85)90005-2
apa: Edelsbrunner, H. (1985). Finding Transversals for Sets of Simple Geometric-Figures.
Theoretical Computer Science. Elsevier. https://doi.org/10.1016/0304-3975(85)90005-2
chicago: Edelsbrunner, Herbert. “Finding Transversals for Sets of Simple Geometric-Figures.”
Theoretical Computer Science. Elsevier, 1985. https://doi.org/10.1016/0304-3975(85)90005-2.
ieee: H. Edelsbrunner, “Finding Transversals for Sets of Simple Geometric-Figures,”
Theoretical Computer Science, vol. 35, no. 1. Elsevier, pp. 55–69, 1985.
ista: Edelsbrunner H. 1985. Finding Transversals for Sets of Simple Geometric-Figures.
Theoretical Computer Science. 35(1), 55–69.
mla: Edelsbrunner, Herbert. “Finding Transversals for Sets of Simple Geometric-Figures.”
Theoretical Computer Science, vol. 35, no. 1, Elsevier, 1985, pp. 55–69,
doi:10.1016/0304-3975(85)90005-2.
short: H. Edelsbrunner, Theoretical Computer Science 35 (1985) 55–69.
date_created: 2018-12-11T12:07:02Z
date_published: 1985-01-01T00:00:00Z
date_updated: 2022-01-31T11:09:26Z
day: '01'
doi: 10.1016/0304-3975(85)90005-2
extern: '1'
intvolume: ' 35'
issue: '1'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://www.sciencedirect.com/science/article/pii/0304397585900052?via%3Dihub
month: '01'
oa: 1
oa_version: Published Version
page: 55 - 69
publication: Theoretical Computer Science
publication_identifier:
eissn:
- 0304-3975
issn:
- 0304-3975
publication_status: published
publisher: Elsevier
publist_id: '2008'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Finding Transversals for Sets of Simple Geometric-Figures
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 35
year: '1985'
...
---
_id: '4120'
abstract:
- lang: eng
text: 'Let P be a set of n points in the Euclidean plane and let C be a convex figure.
We study the problem of preprocessing P so that for any query point q, the points
of P in C+q can be retrieved efficiently. If constant time sumces for deciding
the inclusion of a point in C, we then demonstrate the existence of an optimal
solution: the algorithm requires O(n) space and O(k + log n) time for a query
with output size k. If C is a disk, the problem becomes the wellknown fixed-radius
neighbour problem, to which we thus provide the first known optimal solution.'
acknowledgement: The first author was supported i~1 part by NSF grants MCS 83-03925
and the Office of Naval Research and the Defense Advanced Research Projects Agency
under contract N00014-g3-K-0146 and ARPA Order No. 4786.
article_processing_charge: No
article_type: original
author:
- first_name: Bernard
full_name: Chazelle, Bernard
last_name: Chazelle
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
citation:
ama: Chazelle B, Edelsbrunner H. Optimal solutions for a class of point retrieval
problems. Journal of Symbolic Computation. 1985;1(1):47-56. doi:10.1016/S0747-7171(85)80028-6
apa: Chazelle, B., & Edelsbrunner, H. (1985). Optimal solutions for a class
of point retrieval problems. Journal of Symbolic Computation. Elsevier.
https://doi.org/10.1016/S0747-7171(85)80028-6
chicago: Chazelle, Bernard, and Herbert Edelsbrunner. “Optimal Solutions for a Class
of Point Retrieval Problems.” Journal of Symbolic Computation. Elsevier,
1985. https://doi.org/10.1016/S0747-7171(85)80028-6.
ieee: B. Chazelle and H. Edelsbrunner, “Optimal solutions for a class of point retrieval
problems,” Journal of Symbolic Computation, vol. 1, no. 1. Elsevier, pp.
47–56, 1985.
ista: Chazelle B, Edelsbrunner H. 1985. Optimal solutions for a class of point retrieval
problems. Journal of Symbolic Computation. 1(1), 47–56.
mla: Chazelle, Bernard, and Herbert Edelsbrunner. “Optimal Solutions for a Class
of Point Retrieval Problems.” Journal of Symbolic Computation, vol. 1,
no. 1, Elsevier, 1985, pp. 47–56, doi:10.1016/S0747-7171(85)80028-6.
short: B. Chazelle, H. Edelsbrunner, Journal of Symbolic Computation 1 (1985) 47–56.
date_created: 2018-12-11T12:07:03Z
date_published: 1985-03-01T00:00:00Z
date_updated: 2022-01-31T09:20:18Z
day: '01'
doi: 10.1016/S0747-7171(85)80028-6
extern: '1'
intvolume: ' 1'
issue: '1'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://www.sciencedirect.com/science/article/pii/S0747717185800286?via%3Dihub
month: '03'
oa: 1
oa_version: Published Version
page: 47 - 56
publication: Journal of Symbolic Computation
publication_identifier:
eissn:
- 1095-855X
issn:
- 0747-7171
publication_status: published
publisher: Elsevier
publist_id: '2004'
quality_controlled: '1'
status: public
title: Optimal solutions for a class of point retrieval problems
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 1
year: '1985'
...
---
_id: '4241'
alternative_title:
- 'Progress in leukocyte biology '
article_processing_charge: No
author:
- first_name: C.
full_name: Curtis, C.
last_name: Curtis
- first_name: J.
full_name: Curtis, J.
last_name: Curtis
- 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: 'Curtis C, Curtis J, Barton NH. Methodology for testing the hypothesis of single
locus control of host resistance to infection and malignancy. In: Skamene E, ed.
Genetic Control of Host Resistance to Infection and Malignancy. Vol 3.
Progress in leukocyte biology. Liss; 1985.'
apa: Curtis, C., Curtis, J., & Barton, N. H. (1985). Methodology for testing
the hypothesis of single locus control of host resistance to infection and malignancy.
In E. Skamene (Ed.), Genetic Control of Host Resistance to Infection and Malignancy
(Vol. 3). Liss.
chicago: Curtis, C., J. Curtis, and Nicholas H Barton. “Methodology for Testing
the Hypothesis of Single Locus Control of Host Resistance to Infection and Malignancy.”
In Genetic Control of Host Resistance to Infection and Malignancy, edited
by Emil Skamene, Vol. 3. Progress in Leukocyte Biology. Liss, 1985.
ieee: C. Curtis, J. Curtis, and N. H. Barton, “Methodology for testing the hypothesis
of single locus control of host resistance to infection and malignancy,” in Genetic
Control of Host Resistance to Infection and Malignancy, vol. 3, E. Skamene,
Ed. Liss, 1985.
ista: 'Curtis C, Curtis J, Barton NH. 1985.Methodology for testing the hypothesis
of single locus control of host resistance to infection and malignancy. In: Genetic
Control of Host Resistance to Infection and Malignancy. Progress in leukocyte
biology , vol. 3.'
mla: Curtis, C., et al. “Methodology for Testing the Hypothesis of Single Locus
Control of Host Resistance to Infection and Malignancy.” Genetic Control of
Host Resistance to Infection and Malignancy, edited by Emil Skamene, vol.
3, Liss, 1985.
short: C. Curtis, J. Curtis, N.H. Barton, in:, E. Skamene (Ed.), Genetic Control
of Host Resistance to Infection and Malignancy, Liss, 1985.
date_created: 2018-12-11T12:07:48Z
date_published: 1985-01-01T00:00:00Z
date_updated: 2022-02-02T09:23:20Z
day: '01'
editor:
- first_name: Emil
full_name: Skamene, Emil
last_name: Skamene
extern: '1'
intvolume: ' 3'
language:
- iso: eng
month: '01'
oa_version: None
publication: Genetic Control of Host Resistance to Infection and Malignancy
publication_identifier:
isbn:
- '9780845141021'
publication_status: published
publisher: Liss
publist_id: '1872'
quality_controlled: '1'
series_title: Progress in leukocyte biology
status: public
title: Methodology for testing the hypothesis of single locus control of host resistance
to infection and malignancy
type: book_chapter
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 3
year: '1985'
...
---
_id: '4325'
article_processing_charge: No
article_type: original
author:
- first_name: Steve
full_name: Jones, Steve
last_name: Jones
- 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: Jones S, Barton NH. Haldane’s Rule OK. Nature. 1985;314:668-668. doi:10.1038/314668a0
apa: Jones, S., & Barton, N. H. (1985). Haldane’s Rule OK. Nature. Nature
Publishing Group. https://doi.org/10.1038/314668a0
chicago: Jones, Steve, and Nicholas H Barton. “Haldane’s Rule OK.” Nature.
Nature Publishing Group, 1985. https://doi.org/10.1038/314668a0.
ieee: S. Jones and N. H. Barton, “Haldane’s Rule OK,” Nature, vol. 314. Nature
Publishing Group, pp. 668–668, 1985.
ista: Jones S, Barton NH. 1985. Haldane’s Rule OK. Nature. 314, 668–668.
mla: Jones, Steve, and Nicholas H. Barton. “Haldane’s Rule OK.” Nature, vol.
314, Nature Publishing Group, 1985, pp. 668–668, doi:10.1038/314668a0.
short: S. Jones, N.H. Barton, Nature 314 (1985) 668–668.
date_created: 2018-12-11T12:08:16Z
date_published: 1985-04-25T00:00:00Z
date_updated: 2022-01-28T12:42:09Z
day: '25'
doi: 10.1038/314668a0
extern: '1'
external_id:
pmid:
- '3990801'
intvolume: ' 314'
language:
- iso: eng
month: '04'
oa_version: None
page: 668 - 668
pmid: 1
publication: Nature
publication_status: published
publisher: Nature Publishing Group
publist_id: '1716'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Haldane's Rule OK
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 314
year: '1985'
...
---
_id: '4326'
acknowledgement: We thank R. Butlin, D. Currie, R. A. Nichols , and S. Rouhani for
their thoughtful comments on the manuscript, and their help in preparing the Figures
and Tables; all those (too numerous to name) who gave us details of their unpublished
work; and T. Tsang and S. Ward for their patient typing. This work was supported
by grants from the NERC and SERC to G. M. Hewitt, and from the SERC and the Nuffield
Foundation to N. H. Barton.
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: Godfrey
full_name: Hewitt, Godfrey
last_name: Hewitt
citation:
ama: Barton NH, Hewitt G. Analysis of hybrid zones. Annual Review of Ecology
and Systematics. 1985;16:113-148. doi:10.1146/annurev.es.16.110185.000553
apa: Barton, N. H., & Hewitt, G. (1985). Analysis of hybrid zones. Annual
Review of Ecology and Systematics. Annual Reviews. https://doi.org/10.1146/annurev.es.16.110185.000553
chicago: Barton, Nicholas H, and Godfrey Hewitt. “Analysis of Hybrid Zones.” Annual
Review of Ecology and Systematics. Annual Reviews, 1985. https://doi.org/10.1146/annurev.es.16.110185.000553.
ieee: N. H. Barton and G. Hewitt, “Analysis of hybrid zones,” Annual Review of
Ecology and Systematics, vol. 16. Annual Reviews, pp. 113–148, 1985.
ista: Barton NH, Hewitt G. 1985. Analysis of hybrid zones. Annual Review of Ecology
and Systematics. 16, 113–148.
mla: Barton, Nicholas H., and Godfrey Hewitt. “Analysis of Hybrid Zones.” Annual
Review of Ecology and Systematics, vol. 16, Annual Reviews, 1985, pp. 113–48,
doi:10.1146/annurev.es.16.110185.000553.
short: N.H. Barton, G. Hewitt, Annual Review of Ecology and Systematics 16 (1985)
113–148.
date_created: 2018-12-11T12:08:16Z
date_published: 1985-11-01T00:00:00Z
date_updated: 2022-01-28T12:32:23Z
day: '01'
doi: 10.1146/annurev.es.16.110185.000553
extern: '1'
intvolume: ' 16'
language:
- iso: eng
month: '11'
oa_version: None
page: 113 - 148
publication: Annual Review of Ecology and Systematics
publication_identifier:
eissn:
- 1545-2069
issn:
- 0066-4162
publication_status: published
publisher: Annual Reviews
publist_id: '1714'
quality_controlled: '1'
status: public
title: Analysis of hybrid zones
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 16
year: '1985'
...
---
_id: '3513'
article_processing_charge: No
author:
- first_name: David
full_name: Dobkin, David
last_name: Dobkin
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
citation:
ama: 'Dobkin D, Edelsbrunner H. Ham-sandwich theorems applied to intersection problems.
In: 9th International Workshop on Graph Theoretic Concepts in Computer Science.
WG. Teubner; 1984:88-99.'
apa: 'Dobkin, D., & Edelsbrunner, H. (1984). Ham-sandwich theorems applied to
intersection problems. In 9th International Workshop on Graph Theoretic Concepts
in Computer Science (pp. 88–99). Haus Ohrbeck, Germany: Teubner.'
chicago: Dobkin, David, and Herbert Edelsbrunner. “Ham-Sandwich Theorems Applied
to Intersection Problems.” In 9th International Workshop on Graph Theoretic
Concepts in Computer Science, 88–99. WG. Teubner, 1984.
ieee: D. Dobkin and H. Edelsbrunner, “Ham-sandwich theorems applied to intersection
problems,” in 9th International Workshop on Graph Theoretic Concepts in Computer
Science, Haus Ohrbeck, Germany, 1984, pp. 88–99.
ista: 'Dobkin D, Edelsbrunner H. 1984. Ham-sandwich theorems applied to intersection
problems. 9th International Workshop on Graph Theoretic Concepts in Computer Science.
WG: International Workshop on Graph Theoretic Concepts in Computer ScienceWG,
88–99.'
mla: Dobkin, David, and Herbert Edelsbrunner. “Ham-Sandwich Theorems Applied to
Intersection Problems.” 9th International Workshop on Graph Theoretic Concepts
in Computer Science, Teubner, 1984, pp. 88–99.
short: D. Dobkin, H. Edelsbrunner, in:, 9th International Workshop on Graph Theoretic
Concepts in Computer Science, Teubner, 1984, pp. 88–99.
conference:
location: Haus Ohrbeck, Germany
name: 'WG: International Workshop on Graph Theoretic Concepts in Computer Science'
date_created: 2018-12-11T12:03:43Z
date_published: 1984-01-01T00:00:00Z
date_updated: 2022-01-28T12:10:55Z
day: '01'
extern: '1'
language:
- iso: eng
main_file_link:
- url: http://pub.ist.ac.at/~edels/Papers/1984-P-06-HamSandwichTheorems.pdf
month: '01'
oa_version: None
page: 88 - 99
publication: 9th International Workshop on Graph Theoretic Concepts in Computer Science
publication_identifier:
isbn:
- 3-853-20311-6
publication_status: published
publisher: Teubner
publist_id: '2872'
quality_controlled: '1'
series_title: WG
status: public
title: Ham-sandwich theorems applied to intersection problems
type: conference
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
year: '1984'
...
---
_id: '4117'
abstract:
- lang: eng
text: "Two or more geometrical objects (solids) are said to be connected whenever
their union is a connected point set in the usual sense. Sets of geometrical objects
are naturally divided into connected components, which are maximal connected subsets.
We show that the connected components of a given collection of n horizontal and
vertical line segments in the plane can be computed in O (n log n) time and O
(n) space and prove that this is essentially optimal. The result is generalized
to compute the connected components of a set of n rectilinearly-oriented rectangles\r\nin
the plane with the same time and space bounds. Several extensions of the results
to higher dimensions and to dynamic sets of objects are discussed."
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: Jan
full_name: Van Leeuwen, Jan
last_name: Van Leeuwen
- first_name: Thomas
full_name: Ottmann, Thomas
last_name: Ottmann
- first_name: Derick
full_name: Wood, Derick
last_name: Wood
citation:
ama: Edelsbrunner H, Van Leeuwen J, Ottmann T, Wood D. Computing the connected components
of simple rectilinear geometrical objects in D-Space. Rairo-Informatique Theorique
Et Applications-Theoretical Informatics and Applications. 1984;18(2):171-183.
doi:10.1051/ita/1984180201711
apa: Edelsbrunner, H., Van Leeuwen, J., Ottmann, T., & Wood, D. (1984). Computing
the connected components of simple rectilinear geometrical objects in D-Space.
Rairo-Informatique Theorique Et Applications-Theoretical Informatics and Applications.
EDP Sciences. https://doi.org/10.1051/ita/1984180201711
chicago: Edelsbrunner, Herbert, Jan Van Leeuwen, Thomas Ottmann, and Derick Wood.
“Computing the Connected Components of Simple Rectilinear Geometrical Objects
in D-Space.” Rairo-Informatique Theorique Et Applications-Theoretical Informatics
and Applications. EDP Sciences, 1984. https://doi.org/10.1051/ita/1984180201711.
ieee: H. Edelsbrunner, J. Van Leeuwen, T. Ottmann, and D. Wood, “Computing the connected
components of simple rectilinear geometrical objects in D-Space,” Rairo-Informatique
Theorique Et Applications-Theoretical Informatics and Applications, vol. 18,
no. 2. EDP Sciences, pp. 171–183, 1984.
ista: Edelsbrunner H, Van Leeuwen J, Ottmann T, Wood D. 1984. Computing the connected
components of simple rectilinear geometrical objects in D-Space. Rairo-Informatique
Theorique Et Applications-Theoretical Informatics and Applications. 18(2), 171–183.
mla: Edelsbrunner, Herbert, et al. “Computing the Connected Components of Simple
Rectilinear Geometrical Objects in D-Space.” Rairo-Informatique Theorique Et
Applications-Theoretical Informatics and Applications, vol. 18, no. 2, EDP
Sciences, 1984, pp. 171–83, doi:10.1051/ita/1984180201711.
short: H. Edelsbrunner, J. Van Leeuwen, T. Ottmann, D. Wood, Rairo-Informatique
Theorique Et Applications-Theoretical Informatics and Applications 18 (1984) 171–183.
date_created: 2018-12-11T12:07:02Z
date_published: 1984-01-01T00:00:00Z
date_updated: 2022-01-27T15:22:30Z
day: '01'
doi: 10.1051/ita/1984180201711
extern: '1'
intvolume: ' 18'
issue: '2'
language:
- iso: eng
month: '01'
oa_version: None
page: 171 - 183
publication: Rairo-Informatique Theorique Et Applications-Theoretical Informatics
and Applications
publication_identifier:
eissn:
- 1290-385X
issn:
- 0397-9326
publication_status: published
publisher: EDP Sciences
publist_id: '2001'
quality_controlled: '1'
status: public
title: Computing the connected components of simple rectilinear geometrical objects
in D-Space
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 18
year: '1984'
...
---
_id: '4118'
abstract:
- lang: eng
text: A rectilinear polygon can be viewed as an art gallery room whose walls meet
at right angles. An algorithm is presented that stations guards in such a room
so that every interior point is visible to some guard. The algorithm partitions
the polygon into L-shaped pieces, a subclass of star-shaped pieces, and locates
one guard within each kernel. The algorithm runs in O(n log n) time in the worst
case for a polygon of n vertices.
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: Emo
full_name: Welzl, Emo
last_name: Welzl
citation:
ama: Edelsbrunner H, O’Rourke J, Welzl E. Stationing guards in rectilinear art galleries.
Computer Vision, Graphics, and Image Processing. 1984;27(2):167-176. doi:10.1016/S0734-189X(84)80041-9
apa: Edelsbrunner, H., O’Rourke, J., & Welzl, E. (1984). Stationing guards in
rectilinear art galleries. Computer Vision, Graphics, and Image Processing.
Elsevier. https://doi.org/10.1016/S0734-189X(84)80041-9
chicago: Edelsbrunner, Herbert, Joseph O’Rourke, and Emo Welzl. “Stationing Guards
in Rectilinear Art Galleries.” Computer Vision, Graphics, and Image Processing.
Elsevier, 1984. https://doi.org/10.1016/S0734-189X(84)80041-9.
ieee: H. Edelsbrunner, J. O’Rourke, and E. Welzl, “Stationing guards in rectilinear
art galleries,” Computer Vision, Graphics, and Image Processing, vol. 27,
no. 2. Elsevier, pp. 167–176, 1984.
ista: Edelsbrunner H, O’Rourke J, Welzl E. 1984. Stationing guards in rectilinear
art galleries. Computer Vision, Graphics, and Image Processing. 27(2), 167–176.
mla: Edelsbrunner, Herbert, et al. “Stationing Guards in Rectilinear Art Galleries.”
Computer Vision, Graphics, and Image Processing, vol. 27, no. 2, Elsevier,
1984, pp. 167–76, doi:10.1016/S0734-189X(84)80041-9.
short: H. Edelsbrunner, J. O’Rourke, E. Welzl, Computer Vision, Graphics, and Image
Processing 27 (1984) 167–176.
date_created: 2018-12-11T12:07:02Z
date_published: 1984-08-01T00:00:00Z
date_updated: 2022-01-28T08:03:51Z
day: '01'
doi: 10.1016/S0734-189X(84)80041-9
extern: '1'
intvolume: ' 27'
issue: '2'
language:
- iso: eng
month: '08'
oa_version: None
page: 167 - 176
publication: Computer Vision, Graphics, and Image Processing
publication_identifier:
eissn:
- 0734-189X
issn:
- 1557-895X
publication_status: published
publisher: Elsevier
publist_id: '2002'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Stationing guards in rectilinear art galleries
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 27
year: '1984'
...
---
_id: '4119'
alternative_title:
- LNCS
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. Monotone edge sequences in line arrangements and
applications. In: 11th International Symposium on Mathematical Foundations
of Computer Science. Vol 176. MFCS. Springer; 1984:265-272. doi:10.1007/BFb0030307'
apa: 'Edelsbrunner, H., & Welzl, E. (1984). Monotone edge sequences in line
arrangements and applications. In 11th International Symposium on Mathematical
Foundations of Computer Science (Vol. 176, pp. 265–272). Praha, Czechoslovakia:
Springer. https://doi.org/10.1007/BFb0030307'
chicago: Edelsbrunner, Herbert, and Emo Welzl. “Monotone Edge Sequences in Line
Arrangements and Applications.” In 11th International Symposium on Mathematical
Foundations of Computer Science, 176:265–72. MFCS. Springer, 1984. https://doi.org/10.1007/BFb0030307.
ieee: H. Edelsbrunner and E. Welzl, “Monotone edge sequences in line arrangements
and applications,” in 11th International Symposium on Mathematical Foundations
of Computer Science, Praha, Czechoslovakia, 1984, vol. 176, pp. 265–272.
ista: 'Edelsbrunner H, Welzl E. 1984. Monotone edge sequences in line arrangements
and applications. 11th International Symposium on Mathematical Foundations of
Computer Science. MFCS: Mathematical Foundations of Computer ScienceMFCS, LNCS,
vol. 176, 265–272.'
mla: Edelsbrunner, Herbert, and Emo Welzl. “Monotone Edge Sequences in Line Arrangements
and Applications.” 11th International Symposium on Mathematical Foundations
of Computer Science, vol. 176, Springer, 1984, pp. 265–72, doi:10.1007/BFb0030307.
short: H. Edelsbrunner, E. Welzl, in:, 11th International Symposium on Mathematical
Foundations of Computer Science, Springer, 1984, pp. 265–272.
conference:
end_date: 1984-09-07
location: Praha, Czechoslovakia
name: 'MFCS: Mathematical Foundations of Computer Science'
start_date: 1984-09-03
date_created: 2018-12-11T12:07:03Z
date_published: 1984-01-01T00:00:00Z
date_updated: 2022-01-28T08:52:23Z
day: '01'
doi: 10.1007/BFb0030307
extern: '1'
intvolume: ' 176'
language:
- iso: eng
month: '01'
oa_version: None
page: 265 - 272
publication: 11th International Symposium on Mathematical Foundations of Computer
Science
publication_identifier:
isbn:
- 3-540-13372-0
publication_status: published
publisher: Springer
publist_id: '2003'
quality_controlled: '1'
scopus_import: '1'
series_title: MFCS
status: public
title: Monotone edge sequences in line arrangements and applications
type: conference
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 176
year: '1984'
...
---
_id: '4121'
abstract:
- lang: eng
text: "Whenevern objects are characterized by a matrix of pairwise dissimilarities,
they may be clustered by any of a number of sequential, agglomerative, hierarchical,
nonoverlapping (SAHN) clustering methods. These SAHN clustering methods are defined
by a paradigmatic algorithm that usually requires 0(n 3) time, in the worst case,
to cluster the objects. An improved algorithm (Anderberg 1973), while still requiring
0(n 3) worst-case time, can reasonably be expected to exhibit 0(n 2) expected
behavior. By contrast, we describe a SAHN clustering algorithm that requires 0(n
2 logn) time in the worst case. When SAHN clustering methods exhibit reasonable
space distortion properties, further improvements are possible. We adapt a SAHN
clustering algorithm, based on the efficient construction of nearest neighbor
chains, to obtain a reasonably general SAHN clustering algorithm that requires
in the worst case 0(n 2) time and space.\r\nWhenevern objects are characterized
byk-tuples of real numbers, they may be clustered by any of a family of centroid
SAHN clustering methods. These methods are based on a geometric model in which
clusters are represented by points ink-dimensional real space and points being
agglomerated are replaced by a single (centroid) point. For this model, we have
solved a class of special packing problems involving point-symmetric convex objects
and have exploited it to design an efficient centroid clustering algorithm. Specifically,
we describe a centroid SAHN clustering algorithm that requires 0(n 2) time, in
the worst case, for fixedk and for a family of dissimilarity measures including
the Manhattan, Euclidean, Chebychev and all other Minkowski metrics."
article_processing_charge: No
article_type: original
author:
- first_name: William
full_name: Day, William
last_name: Day
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
citation:
ama: Day W, Edelsbrunner H. Efficient algorithms for agglomerative hierarchical
clustering methods. Journal of Classification. 1984;1:7-24. doi:10.1007/BF01890115
apa: Day, W., & Edelsbrunner, H. (1984). Efficient algorithms for agglomerative
hierarchical clustering methods. Journal of Classification. Springer. https://doi.org/10.1007/BF01890115
chicago: Day, William, and Herbert Edelsbrunner. “Efficient Algorithms for Agglomerative
Hierarchical Clustering Methods.” Journal of Classification. Springer,
1984. https://doi.org/10.1007/BF01890115.
ieee: W. Day and H. Edelsbrunner, “Efficient algorithms for agglomerative hierarchical
clustering methods,” Journal of Classification, vol. 1. Springer, pp. 7–24,
1984.
ista: Day W, Edelsbrunner H. 1984. Efficient algorithms for agglomerative hierarchical
clustering methods. Journal of Classification. 1, 7–24.
mla: Day, William, and Herbert Edelsbrunner. “Efficient Algorithms for Agglomerative
Hierarchical Clustering Methods.” Journal of Classification, vol. 1, Springer,
1984, pp. 7–24, doi:10.1007/BF01890115.
short: W. Day, H. Edelsbrunner, Journal of Classification 1 (1984) 7–24.
date_created: 2018-12-11T12:07:04Z
date_published: 1984-01-01T00:00:00Z
date_updated: 2022-01-27T14:16:27Z
day: '01'
doi: 10.1007/BF01890115
extern: '1'
intvolume: ' 1'
language:
- iso: eng
main_file_link:
- url: https://link.springer.com/article/10.1007%2FBF01890115
month: '01'
oa_version: None
page: 7 - 24
publication: Journal of Classification
publication_identifier:
eissn:
- 1432-1343
issn:
- 0176-4268
publication_status: published
publisher: Springer
publist_id: '1998'
quality_controlled: '1'
status: public
title: Efficient algorithms for agglomerative hierarchical clustering methods
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 1
year: '1984'
...
---
_id: '4122'
abstract:
- lang: eng
text: Computational geometry, considered a subfield of computer science, is concerned
with the computational aspects of geometric problems. The increasing activity
in this rather young field made it split into several reasonably independent subareas.
This paper presents several key-problems of the classical part of computational
geometry which exhibit strong interrelations. A unified view of the problems is
stressed, and the general ideas behind the methods that solve them are worked
out.
alternative_title:
- LNCS
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
citation:
ama: 'Edelsbrunner H. Key-problems and key-methods in computational geometry. In:
1st Symposium of Theoretical Aspects of Computer Science. Vol 166. STACS.
Springer; 1984:1-13. doi:10.1007/3-540-12920-0_1'
apa: 'Edelsbrunner, H. (1984). Key-problems and key-methods in computational geometry.
In 1st Symposium of Theoretical Aspects of Computer Science (Vol. 166,
pp. 1–13). Paris, France: Springer. https://doi.org/10.1007/3-540-12920-0_1'
chicago: Edelsbrunner, Herbert. “Key-Problems and Key-Methods in Computational Geometry.”
In 1st Symposium of Theoretical Aspects of Computer Science, 166:1–13.
STACS. Springer, 1984. https://doi.org/10.1007/3-540-12920-0_1.
ieee: H. Edelsbrunner, “Key-problems and key-methods in computational geometry,”
in 1st Symposium of Theoretical Aspects of Computer Science, Paris, France,
1984, vol. 166, pp. 1–13.
ista: 'Edelsbrunner H. 1984. Key-problems and key-methods in computational geometry.
1st Symposium of Theoretical Aspects of Computer Science. STACS: Theoretical Aspects
of Computer ScienceSTACS, LNCS, vol. 166, 1–13.'
mla: Edelsbrunner, Herbert. “Key-Problems and Key-Methods in Computational Geometry.”
1st Symposium of Theoretical Aspects of Computer Science, vol. 166, Springer,
1984, pp. 1–13, doi:10.1007/3-540-12920-0_1.
short: H. Edelsbrunner, in:, 1st Symposium of Theoretical Aspects of Computer Science,
Springer, 1984, pp. 1–13.
conference:
end_date: 1984-04-13
location: Paris, France
name: 'STACS: Theoretical Aspects of Computer Science'
start_date: 1984-04-11
date_created: 2018-12-11T12:07:04Z
date_published: 1984-01-01T00:00:00Z
date_updated: 2022-01-27T14:48:15Z
day: '01'
doi: 10.1007/3-540-12920-0_1
extern: '1'
intvolume: ' 166'
language:
- iso: eng
month: '01'
oa_version: None
page: 1 - 13
publication: 1st Symposium of Theoretical Aspects of Computer Science
publication_identifier:
isbn:
- 3-540-12920-0
publication_status: published
publisher: Springer
publist_id: '1999'
quality_controlled: '1'
scopus_import: '1'
series_title: STACS
status: public
title: Key-problems and key-methods in computational geometry
type: conference
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 166
year: '1984'
...
---
_id: '4123'
abstract:
- lang: eng
text: Windowing a two-dimensional picture means to determine those line segments
of the picture that are visible through an axis-parallel window. A study of some
algorithmic problems involved in windowing a picture is offered. Some methods
from computational geometry are exploited to store the picture in a computer such
that (1) those line segments inside or partially inside of a window can be determined
efficiently, and (2) the set of those line segments can be maintained efficiently
while the window is moved parallel to a coordinate axis and/or it is enlarged
or reduced.
acknowledgement: "Research reported in this paper was done while the second author
visited the Technical University of Graz. He was supported by the Netherlands Organization
for the Advancement of Pure Research (ZWO). The first author was supported by the
Austrian Fonds zur Foerderung der wissenschaftlichen Forschung.\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: Mark
full_name: Overmars, Mark
last_name: Overmars
- first_name: Raimund
full_name: Seidel, Raimund
last_name: Seidel
citation:
ama: Edelsbrunner H, Overmars M, Seidel R. Some methods of computational geometry
applied to computer graphics. Computer Vision, Graphics, and Image Processing.
1984;28(1):92-108. doi:10.1016/0734-189X(84)90142-7
apa: Edelsbrunner, H., Overmars, M., & Seidel, R. (1984). Some methods of computational
geometry applied to computer graphics. Computer Vision, Graphics, and Image
Processing. Elsevier. https://doi.org/10.1016/0734-189X(84)90142-7
chicago: Edelsbrunner, Herbert, Mark Overmars, and Raimund Seidel. “Some Methods
of Computational Geometry Applied to Computer Graphics.” Computer Vision, Graphics,
and Image Processing. Elsevier, 1984. https://doi.org/10.1016/0734-189X(84)90142-7.
ieee: H. Edelsbrunner, M. Overmars, and R. Seidel, “Some methods of computational
geometry applied to computer graphics,” Computer Vision, Graphics, and Image
Processing, vol. 28, no. 1. Elsevier, pp. 92–108, 1984.
ista: Edelsbrunner H, Overmars M, Seidel R. 1984. Some methods of computational
geometry applied to computer graphics. Computer Vision, Graphics, and Image Processing.
28(1), 92–108.
mla: Edelsbrunner, Herbert, et al. “Some Methods of Computational Geometry Applied
to Computer Graphics.” Computer Vision, Graphics, and Image Processing,
vol. 28, no. 1, Elsevier, 1984, pp. 92–108, doi:10.1016/0734-189X(84)90142-7.
short: H. Edelsbrunner, M. Overmars, R. Seidel, Computer Vision, Graphics, and Image
Processing 28 (1984) 92–108.
date_created: 2018-12-11T12:07:04Z
date_published: 1984-10-01T00:00:00Z
date_updated: 2022-01-27T15:10:04Z
day: '01'
doi: 10.1016/0734-189X(84)90142-7
extern: '1'
intvolume: ' 28'
issue: '1'
language:
- iso: eng
month: '10'
oa_version: None
page: 92 - 108
publication: Computer Vision, Graphics, and Image Processing
publication_identifier:
eissn:
- 1557-895X
issn:
- 0734-189X
publication_status: published
publisher: Elsevier
publist_id: '2000'
quality_controlled: '1'
status: public
title: Some methods of computational geometry applied to computer graphics
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 28
year: '1984'
...