---
_id: '4096'
acknowledgement: Research on this paper was supported by the National Science Foundation
under grant CCR-8714565.
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. Geometric structures in computational geometry. In: 15th
International Colloquium on Automata, Languages and Programming. Vol 317.
Springer; 1988:201-213. doi:10.1007/3-540-19488-6_117'
apa: 'Edelsbrunner, H. (1988). Geometric structures in computational geometry. In
15th International Colloquium on Automata, Languages and Programming (Vol.
317, pp. 201–213). Tampere, Finland: Springer. https://doi.org/10.1007/3-540-19488-6_117'
chicago: Edelsbrunner, Herbert. “Geometric Structures in Computational Geometry.”
In 15th International Colloquium on Automata, Languages and Programming,
317:201–13. Springer, 1988. https://doi.org/10.1007/3-540-19488-6_117.
ieee: H. Edelsbrunner, “Geometric structures in computational geometry,” in 15th
International Colloquium on Automata, Languages and Programming, Tampere,
Finland, 1988, vol. 317, pp. 201–213.
ista: 'Edelsbrunner H. 1988. Geometric structures in computational geometry. 15th
International Colloquium on Automata, Languages and Programming. ALP: Automata,
Languages and Programming, LNCS, vol. 317, 201–213.'
mla: Edelsbrunner, Herbert. “Geometric Structures in Computational Geometry.” 15th
International Colloquium on Automata, Languages and Programming, vol. 317,
Springer, 1988, pp. 201–13, doi:10.1007/3-540-19488-6_117.
short: H. Edelsbrunner, in:, 15th International Colloquium on Automata, Languages
and Programming, Springer, 1988, pp. 201–213.
conference:
end_date: 1988-07-15
location: Tampere, Finland
name: 'ALP: Automata, Languages and Programming'
start_date: 1988-07-11
date_created: 2018-12-11T12:06:55Z
date_published: 1988-01-01T00:00:00Z
date_updated: 2022-02-08T09:53:52Z
day: '01'
doi: 10.1007/3-540-19488-6_117
extern: '1'
intvolume: ' 317'
language:
- iso: eng
main_file_link:
- url: https://link.springer.com/chapter/10.1007/3-540-19488-6_117
month: '01'
oa_version: None
page: 201 - 213
publication: 15th International Colloquium on Automata, Languages and Programming
publication_identifier:
eisbn:
- 978-3-540-39291-0
isbn:
- 978-3-540-19488-0
publication_status: published
publisher: Springer
publist_id: '2027'
quality_controlled: '1'
status: public
title: Geometric structures in computational geometry
type: conference
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 317
year: '1988'
...
---
_id: '4097'
abstract:
- lang: eng
text: Arrangements of curves in the plane are of fundamental significance in many
problems of computational and combinatorial geometry (e.g. motion planning, algebraic
cell decomposition, etc.). In this paper we study various topological and combinatorial
properties of such arrangements under some mild assumptions on the shape of the
curves, and develop basic tools for the construction, manipulation, and analysis
of these arrangements. Our main results include a generalization of the zone theorem
of [EOS], [CGL] to arrangements of curves (in which we show that the combinatorial
complexity of the zone of a curve is nearly linear in the number of curves), and
an application of (some weaker variant of) that theorem to obtain a nearly quadratic
incremental algorithm for the construction of such arrangements.
acknowledgement: Work on this paper by the first author has been supported by Amoco
Fnd. Fac. Dev. Comput. Sci. 1-6-44862 and by the National Science Foundation under
grant CCR-8714566. Work on this paper by the third and sixth authors has been supported
by Office of Naval Research Grant N00014-82-K-0381, by National Science Foundation
Grant No. NSF-DCR-83-20085, by grants from the Digital Equipment Corporation, and
the IBM Corporation. Work by the sixth author has also been supported by a research
grant from the NCRD — the Israeli National Council for Research and Development.
Work by the fourth author has been supported by National Science Foundation Grant
DMS-8501947.
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: Leonidas
full_name: Guibas, Leonidas
last_name: Guibas
- first_name: János
full_name: Pach, János
last_name: Pach
- first_name: Richard
full_name: Pollack, Richard
last_name: Pollack
- first_name: Raimund
full_name: Seidel, Raimund
last_name: Seidel
- first_name: Micha
full_name: Sharir, Micha
last_name: Sharir
citation:
ama: 'Edelsbrunner H, Guibas L, Pach J, Pollack R, Seidel R, Sharir M. Arrangements
of curves in the plane - topology, combinatorics, and algorithms. In: 15th
International Colloquium on Automata, Languages and Programming. Vol 317.
Springer; 1988:214-229. doi:10.1007/3-540-19488-6_118'
apa: 'Edelsbrunner, H., Guibas, L., Pach, J., Pollack, R., Seidel, R., & Sharir,
M. (1988). Arrangements of curves in the plane - topology, combinatorics, and
algorithms. In 15th International Colloquium on Automata, Languages and Programming
(Vol. 317, pp. 214–229). Tampere, Finland: Springer. https://doi.org/10.1007/3-540-19488-6_118'
chicago: Edelsbrunner, Herbert, Leonidas Guibas, János Pach, Richard Pollack, Raimund
Seidel, and Micha Sharir. “Arrangements of Curves in the Plane - Topology, Combinatorics,
and Algorithms.” In 15th International Colloquium on Automata, Languages and
Programming, 317:214–29. Springer, 1988. https://doi.org/10.1007/3-540-19488-6_118.
ieee: H. Edelsbrunner, L. Guibas, J. Pach, R. Pollack, R. Seidel, and M. Sharir,
“Arrangements of curves in the plane - topology, combinatorics, and algorithms,”
in 15th International Colloquium on Automata, Languages and Programming,
Tampere, Finland, 1988, vol. 317, pp. 214–229.
ista: 'Edelsbrunner H, Guibas L, Pach J, Pollack R, Seidel R, Sharir M. 1988. Arrangements
of curves in the plane - topology, combinatorics, and algorithms. 15th International
Colloquium on Automata, Languages and Programming. ICALP: Automata, Languages
and Programming, LNCS, vol. 317, 214–229.'
mla: Edelsbrunner, Herbert, et al. “Arrangements of Curves in the Plane - Topology,
Combinatorics, and Algorithms.” 15th International Colloquium on Automata,
Languages and Programming, vol. 317, Springer, 1988, pp. 214–29, doi:10.1007/3-540-19488-6_118.
short: H. Edelsbrunner, L. Guibas, J. Pach, R. Pollack, R. Seidel, M. Sharir, in:,
15th International Colloquium on Automata, Languages and Programming, Springer,
1988, pp. 214–229.
conference:
end_date: 1988-07-15
location: Tampere, Finland
name: 'ICALP: Automata, Languages and Programming'
start_date: 1988-07-11
date_created: 2018-12-11T12:06:55Z
date_published: 1988-01-01T00:00:00Z
date_updated: 2022-02-08T10:15:09Z
day: '01'
doi: 10.1007/3-540-19488-6_118
extern: '1'
intvolume: ' 317'
keyword:
- line segment
- computational geometry
- Jordan curve
- cell decomposition
- vertical tangency
language:
- iso: eng
main_file_link:
- url: https://link.springer.com/chapter/10.1007/3-540-19488-6_118
month: '01'
oa_version: None
page: 214 - 229
publication: 15th International Colloquium on Automata, Languages and Programming
publication_identifier:
isbn:
- 978-3-540-19488-0
publication_status: published
publisher: Springer
publist_id: '2028'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Arrangements of curves in the plane - topology, combinatorics, and algorithms
type: conference
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 317
year: '1988'
...
---
_id: '4315'
article_processing_charge: No
author:
- first_name: Jerry
full_name: Coyne, Jerry
last_name: Coyne
- 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: Coyne J, Barton NH. What do we know about speciation? Nature. 1988;331:485-486.
doi:10.1038/331485a0
apa: Coyne, J., & Barton, N. H. (1988). What do we know about speciation? Nature.
Nature Publishing Group. https://doi.org/10.1038/331485a0
chicago: Coyne, Jerry, and Nicholas H Barton. “What Do We Know about Speciation?”
Nature. Nature Publishing Group, 1988. https://doi.org/10.1038/331485a0.
ieee: J. Coyne and N. H. Barton, “What do we know about speciation?,” Nature,
vol. 331. Nature Publishing Group, pp. 485–486, 1988.
ista: Coyne J, Barton NH. 1988. What do we know about speciation? Nature. 331, 485–486.
mla: Coyne, Jerry, and Nicholas H. Barton. “What Do We Know about Speciation?” Nature,
vol. 331, Nature Publishing Group, 1988, pp. 485–86, doi:10.1038/331485a0.
short: J. Coyne, N.H. Barton, Nature 331 (1988) 485–486.
date_created: 2018-12-11T12:08:12Z
date_published: 1988-02-11T00:00:00Z
date_updated: 2022-02-08T09:40:40Z
day: '11'
doi: 10.1038/331485a0
extern: '1'
intvolume: ' 331'
language:
- iso: eng
main_file_link:
- url: https://www.nature.com/articles/331485a0
month: '02'
oa_version: None
page: 485 - 486
publication: Nature
publication_identifier:
eissn:
- 1476-4687
issn:
- 0028-0836
publication_status: published
publisher: Nature Publishing Group
publist_id: '1738'
quality_controlled: '1'
status: public
title: What do we know about speciation?
type: review
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 331
year: '1988'
...
---
_id: '4316'
article_processing_charge: No
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: Steve
full_name: Jones, Steve
last_name: Jones
citation:
ama: Barton NH, Jones S. Molecular evolutionary genetics. Nature. 1988;332:597-597.
doi:10.1038/332597a0
apa: Barton, N. H., & Jones, S. (1988). Molecular evolutionary genetics. Nature.
Springer Nature. https://doi.org/10.1038/332597a0
chicago: Barton, Nicholas H, and Steve Jones. “Molecular Evolutionary Genetics.”
Nature. Springer Nature, 1988. https://doi.org/10.1038/332597a0.
ieee: N. H. Barton and S. Jones, “Molecular evolutionary genetics,” Nature,
vol. 332. Springer Nature, pp. 597–597, 1988.
ista: Barton NH, Jones S. 1988. Molecular evolutionary genetics. Nature. 332, 597–597.
mla: Barton, Nicholas H., and Steve Jones. “Molecular Evolutionary Genetics.” Nature,
vol. 332, Springer Nature, 1988, pp. 597–597, doi:10.1038/332597a0.
short: N.H. Barton, S. Jones, Nature 332 (1988) 597–597.
date_created: 2018-12-11T12:08:13Z
date_published: 1988-01-01T00:00:00Z
date_updated: 2022-02-08T09:44:51Z
day: '01'
doi: 10.1038/332597a0
extern: '1'
intvolume: ' 332'
language:
- iso: eng
main_file_link:
- url: https://www.nature.com/articles/332597a0
month: '01'
oa_version: None
page: 597 - 597
publication: Nature
publication_identifier:
eissn:
- 1476-4687
issn:
- 0028-0836
publication_status: published
publisher: Springer Nature
publist_id: '1739'
quality_controlled: '1'
status: public
title: Molecular evolutionary genetics
type: review
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 332
year: '1988'
...
---
_id: '4317'
article_processing_charge: No
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. Speciation. In: Myers A, Giller P, eds. Analytical Biogeography:
An Integrated Approach to the Study of Animal and Plant Distributions. 1st
ed. Springer; 1988:185-218. doi:10.1007/978-94-009-0435-4'
apa: 'Barton, N. H. (1988). Speciation. In A. Myers & P. Giller (Eds.), Analytical
biogeography: An integrated approach to the study of animal and plant distributions
(1st ed., pp. 185–218). Springer. https://doi.org/10.1007/978-94-009-0435-4'
chicago: 'Barton, Nicholas H. “Speciation.” In Analytical Biogeography: An Integrated
Approach to the Study of Animal and Plant Distributions, edited by Alan Myers
and Paul Giller, 1st ed., 185–218. Springer, 1988. https://doi.org/10.1007/978-94-009-0435-4.'
ieee: 'N. H. Barton, “Speciation,” in Analytical biogeography: An integrated
approach to the study of animal and plant distributions, 1st ed., A. Myers
and P. Giller, Eds. Springer, 1988, pp. 185–218.'
ista: 'Barton NH. 1988.Speciation. In: Analytical biogeography: An integrated approach
to the study of animal and plant distributions. , 185–218.'
mla: 'Barton, Nicholas H. “Speciation.” Analytical Biogeography: An Integrated
Approach to the Study of Animal and Plant Distributions, edited by Alan Myers
and Paul Giller, 1st ed., Springer, 1988, pp. 185–218, doi:10.1007/978-94-009-0435-4.'
short: 'N.H. Barton, in:, A. Myers, P. Giller (Eds.), Analytical Biogeography: An
Integrated Approach to the Study of Animal and Plant Distributions, 1st ed., Springer,
1988, pp. 185–218.'
date_created: 2018-12-11T12:08:13Z
date_published: 1988-01-01T00:00:00Z
date_updated: 2022-02-08T09:19:50Z
day: '01'
doi: 10.1007/978-94-009-0435-4
edition: '1'
editor:
- first_name: Alan
full_name: Myers, Alan
last_name: Myers
- first_name: Paul
full_name: Giller, Paul
last_name: Giller
extern: '1'
keyword:
- biogeography
- biology
- complexity
- distribution
- evolution
- geology
language:
- iso: eng
main_file_link:
- url: https://link.springer.com/book/10.1007/978-94-009-0435-4#toc
month: '01'
oa_version: None
page: 185 - 218
publication: 'Analytical biogeography: An integrated approach to the study of animal
and plant distributions'
publication_identifier:
eissn:
- 978-94-009-0435-4
isbn:
- 978-0-412-40050-6
publication_status: published
publisher: Springer
publist_id: '1736'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Speciation
type: book_chapter
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
year: '1988'
...
---
_id: '4318'
article_processing_charge: No
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: Steve
full_name: Jones, Steve
last_name: Jones
- first_name: James
full_name: Mallet, James
last_name: Mallet
citation:
ama: Barton NH, Jones S, Mallet J. No barriers to speciation. Nature. 1988;336:13-14.
doi:10.1038/336013a0
apa: Barton, N. H., Jones, S., & Mallet, J. (1988). No barriers to speciation.
Nature. Springer Nature. https://doi.org/10.1038/336013a0
chicago: Barton, Nicholas H, Steve Jones, and James Mallet. “No Barriers to Speciation.”
Nature. Springer Nature, 1988. https://doi.org/10.1038/336013a0.
ieee: N. H. Barton, S. Jones, and J. Mallet, “No barriers to speciation,” Nature,
vol. 336. Springer Nature, pp. 13–14, 1988.
ista: Barton NH, Jones S, Mallet J. 1988. No barriers to speciation. Nature. 336,
13–14.
mla: Barton, Nicholas H., et al. “No Barriers to Speciation.” Nature, vol.
336, Springer Nature, 1988, pp. 13–14, doi:10.1038/336013a0.
short: N.H. Barton, S. Jones, J. Mallet, Nature 336 (1988) 13–14.
date_created: 2018-12-11T12:08:13Z
date_published: 1988-11-03T00:00:00Z
date_updated: 2022-02-08T09:36:20Z
day: '03'
doi: 10.1038/336013a0
extern: '1'
intvolume: ' 336'
language:
- iso: eng
main_file_link:
- url: https://www.nature.com/articles/336013a0
month: '11'
oa_version: None
page: 13 - 14
publication: Nature
publication_identifier:
eissn:
- 1476-4687
issn:
- 0028-0836
publication_status: published
publisher: Springer Nature
publist_id: '1737'
quality_controlled: '1'
status: public
title: No barriers to speciation
type: review
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 336
year: '1988'
...
---
_id: '2521'
article_processing_charge: No
author:
- first_name: Masaki
full_name: Nishimura, Masaki
last_name: Nishimura
- first_name: Ryuichi
full_name: Shigemoto, Ryuichi
id: 499F3ABC-F248-11E8-B48F-1D18A9856A87
last_name: Shigemoto
orcid: 0000-0001-8761-9444
- first_name: K
full_name: Matsubayashi, K
last_name: Matsubayashi
- first_name: Y
full_name: Mimori, Y
last_name: Mimori
- first_name: Masakuni
full_name: Kameyama, Masakuni
last_name: Kameyama
citation:
ama: Nishimura M, Shigemoto R, Matsubayashi K, Mimori Y, Kameyama M. Meningoencephalitis
during the pre-icteric phase of hepatitis A - a case report. Clinical Neurology.
1987;27(11):1441-1444.
apa: Nishimura M., Shigemoto R., Matsubayashi K., Mimori Y., & Kameyama M. (1987).
Meningoencephalitis during the pre-icteric phase of hepatitis A - a case report.
Clinical Neurology. Societas Neurologica Japonica.
chicago: Nishimura Masaki, Shigemoto Ryuichi, Matsubayashi K, Mimori Y, and Kameyama
Masakuni. “Meningoencephalitis during the pre-icteric phase of hepatitis A - a
case report.” Clinical Neurology. Societas Neurologica Japonica, 1987.
ieee: Nishimura M., Shigemoto R., Matsubayashi K., Mimori Y., and Kameyama M., “Meningoencephalitis
during the pre-icteric phase of hepatitis A - a case report,” Clinical Neurology,
vol. 27, no. 11. Societas Neurologica Japonica, pp. 1441–1444, 1987.
ista: Nishimura M, Shigemoto R, Matsubayashi K, Mimori Y, Kameyama M. 1987. Meningoencephalitis
during the pre-icteric phase of hepatitis A - a case report. Clinical Neurology.
27(11), 1441–1444.
mla: Nishimura Masaki, et al. “Meningoencephalitis during the pre-icteric phase
of hepatitis A - a case report.” Clinical Neurology, vol. 27, no. 11, Societas
Neurologica Japonica, 1987, pp. 1441–44.
short: Nishimura M., Shigemoto R., Matsubayashi K., Mimori Y., Kameyama M., Clinical
Neurology 27 (1987) 1441–1444.
date_created: 2018-12-11T11:58:09Z
date_published: 1987-11-01T00:00:00Z
date_updated: 2022-02-07T16:17:34Z
day: '01'
extern: '1'
intvolume: ' 27'
issue: '11'
language:
- iso: jpn
month: '11'
oa_version: None
page: 1441 - 1444
publication: Clinical Neurology
publication_status: published
publisher: Societas Neurologica Japonica
publist_id: '4378'
status: public
title: Meningoencephalitis during the pre-icteric phase of hepatitis A - a case report
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 27
year: '1987'
...
---
_id: '3514'
abstract:
- lang: eng
text: We consider the problem of obtaining sharp (nearly quadratic) bounds for the
combinatorial complexity of the lower envelope (i.e. pointwise minimum) of a collection
of n bivariate (or generally multi-variate) continuous and "simple"
functions, and of designing efficient algorithms for the calculation of this envelope.
This problem generalizes the well-studied univariate case (whose analysis is based
on the theory of Davenport-Schinzel sequences), but appears to be much more difficult
and still largely unsolved. It is a central problem that arises in many areas
in computational and combinatorial geometry, and has numerous applications including
generalized planar Voronoi diagrams, hidden surface elimination for intersecting
surfaces, purely translational motion planning, finding common transversals of
polyhedra, and more. In this abstract we provide several partial solutions and
generalizations of this problem, and apply them to the problems mentioned above.
The most significant of our results is that the lower envelope of n triangles
in three dimensions has combinatorial complexity at most O(n2α(n)) (where α(n)
is the extremely slowly growing inverse of Ackermann's function), that this bound
is tight in the worst case, and that this envelope can be calculated in time O(n2α(n)).
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: János
full_name: Pach, János
last_name: Pach
- first_name: Jacob
full_name: Schwartz, Jacob
last_name: Schwartz
- first_name: Micha
full_name: Sharir, Micha
last_name: Sharir
citation:
ama: 'Edelsbrunner H, Pach J, Schwartz J, Sharir M. On the lower envelope of bivariate
functions and its applications. In: 28th Annual Symposium on Foundations of
Computer Science . IEEE; 1987:27-37. doi:10.1109/SFCS.1987.44'
apa: 'Edelsbrunner, H., Pach, J., Schwartz, J., & Sharir, M. (1987). On the
lower envelope of bivariate functions and its applications. In 28th Annual
Symposium on Foundations of Computer Science (pp. 27–37). Los Angeles, CA,
USA: IEEE. https://doi.org/10.1109/SFCS.1987.44'
chicago: Edelsbrunner, Herbert, János Pach, Jacob Schwartz, and Micha Sharir. “On
the Lower Envelope of Bivariate Functions and Its Applications.” In 28th Annual
Symposium on Foundations of Computer Science , 27–37. IEEE, 1987. https://doi.org/10.1109/SFCS.1987.44.
ieee: H. Edelsbrunner, J. Pach, J. Schwartz, and M. Sharir, “On the lower envelope
of bivariate functions and its applications,” in 28th Annual Symposium on Foundations
of Computer Science , Los Angeles, CA, USA, 1987, pp. 27–37.
ista: 'Edelsbrunner H, Pach J, Schwartz J, Sharir M. 1987. On the lower envelope
of bivariate functions and its applications. 28th Annual Symposium on Foundations
of Computer Science . FOCS: Foundations of Computer Science, 27–37.'
mla: Edelsbrunner, Herbert, et al. “On the Lower Envelope of Bivariate Functions
and Its Applications.” 28th Annual Symposium on Foundations of Computer Science
, IEEE, 1987, pp. 27–37, doi:10.1109/SFCS.1987.44.
short: H. Edelsbrunner, J. Pach, J. Schwartz, M. Sharir, in:, 28th Annual Symposium
on Foundations of Computer Science , IEEE, 1987, pp. 27–37.
conference:
end_date: 1987-10-14
location: Los Angeles, CA, USA
name: 'FOCS: Foundations of Computer Science'
start_date: 1987-10-12
date_created: 2018-12-11T12:03:44Z
date_published: 1987-10-14T00:00:00Z
date_updated: 2022-02-07T15:14:55Z
day: '14'
doi: 10.1109/SFCS.1987.44
extern: '1'
language:
- iso: eng
main_file_link:
- url: https://ieeexplore.ieee.org/document/4568253?denied=
month: '10'
oa_version: None
page: 27 - 37
publication: '28th Annual Symposium on Foundations of Computer Science '
publication_identifier:
isbn:
- 0-8186-0807-2
issn:
- 0272-5428
publication_status: published
publisher: IEEE
publist_id: '2871'
quality_controlled: '1'
scopus_import: '1'
status: public
title: On the lower envelope of bivariate functions and its applications
type: conference
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
year: '1987'
...
---
_id: '3656'
abstract:
- lang: eng
text: We have analysed the role of sampling drift in inducing shifts between alternative
adaptive peaks, in small and rapidly growing populations. Using a simple model
of disruptive selection on a polygenic character, we calculate the net probabilityofapeakshift.
If the growth rate is high, theprobabilityofashiftina growing population is insensitive
to selection on the character. Assuming that the character is effectively neutral
during the brief initial increase, we find that theprobabilityofapeakshift is
given by theprobabilityof finding a standard normal variate greater than √2ΔV
where ΔV is the reduction in additive genetic variance during the growth period.
This result holds for arbitrary pattern of increase in size, provided that the
rate of increase is high enough for selection to be negligible, and the character
depends on a large number of loci. Comparing theprobabilityofpeakshiftsin founding
populations with the rate ofshiftsin static and allopatric populations it appears
that although strongly selected shifts are only likely to occur ina growing population,
a static population is a more congenial setting for adaptive shifts.
article_processing_charge: No
article_type: original
author:
- first_name: Shahin
full_name: Rouhani, Shahin
last_name: Rouhani
- 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: Rouhani S, Barton NH. The probability of peak shifts in a founder population.
Journal of Theoretical Biology. 1987;126(1):51-62. doi:10.1016/S0022-5193(87)80100-5
apa: Rouhani, S., & Barton, N. H. (1987). The probability of peak shifts in
a founder population. Journal of Theoretical Biology. Elsevier. https://doi.org/10.1016/S0022-5193(87)80100-5
chicago: Rouhani, Shahin, and Nicholas H Barton. “The Probability of Peak Shifts
in a Founder Population.” Journal of Theoretical Biology. Elsevier, 1987.
https://doi.org/10.1016/S0022-5193(87)80100-5.
ieee: S. Rouhani and N. H. Barton, “The probability of peak shifts in a founder
population,” Journal of Theoretical Biology, vol. 126, no. 1. Elsevier,
pp. 51–62, 1987.
ista: Rouhani S, Barton NH. 1987. The probability of peak shifts in a founder population.
Journal of Theoretical Biology. 126(1), 51–62.
mla: Rouhani, Shahin, and Nicholas H. Barton. “The Probability of Peak Shifts in
a Founder Population.” Journal of Theoretical Biology, vol. 126, no. 1,
Elsevier, 1987, pp. 51–62, doi:10.1016/S0022-5193(87)80100-5.
short: S. Rouhani, N.H. Barton, Journal of Theoretical Biology 126 (1987) 51–62.
date_created: 2018-12-11T12:04:28Z
date_published: 1987-05-07T00:00:00Z
date_updated: 2022-02-04T12:36:32Z
day: '07'
doi: 10.1016/S0022-5193(87)80100-5
extern: '1'
intvolume: ' 126'
issue: '1'
language:
- iso: eng
main_file_link:
- url: https://www.sciencedirect.com/science/article/pii/S0022519387801005?via%3Dihub
month: '05'
oa_version: None
page: 51 - 62
publication: Journal of Theoretical Biology
publication_identifier:
eissn:
- 1095-8541
issn:
- 0022-5193
publication_status: published
publisher: Elsevier
publist_id: '2727'
quality_controlled: '1'
scopus_import: '1'
status: public
title: The probability of peak shifts in a founder population
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 126
year: '1987'
...
---
_id: '3657'
abstract:
- lang: eng
text: Shifts between adaptive peaks, caused by sampling drift, are involved in both
speciation and adaptation via Wright's “shiftingbalance.” We use techniques from
statistical mechanics to calculate the rate of such transitions for apopulation
in a single panmictic deme and for apopulation which is continuously distributed
over one- and two-dimensional regions. This calculation applies in the limit where
transitions are rare. Our results indicate that stochastic divergence is feasible
despite free gene flow, provided that neighbourhood size is low enough. In two
dimensions, the rate of transition depends primarily on neighbourhood size N and
only weakly on selection pressure (≈sk exp(− cN)), where k is a number determined
by the local population structure, in contrast with the exponential dependence
on selection pressure in one dimension (≈exp(− cN √s)) or in a single deme (≈exp(−
cNs)). Our calculations agree with simulations of a single deme and a one-dimensional
population.
acknowledgement: "We thank M. Shaw, J. Felsenstein, M. Kirkpatrick, S. Via, J. S.
Jones, M. Slatkin, J. Mallet, and B. Charlesworth for their helpful comments. This
work was supported by grants from the SERC (GR/C/91529), the University of London
Central Research Fund, and the Nufield Foundation. \r\n"
article_processing_charge: No
article_type: original
author:
- first_name: Shahin
full_name: Rouhani, Shahin
last_name: Rouhani
- 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: Rouhani S, Barton NH. Speciation and the "shifting balance"
in a continuous population. Theoretical Population Biology. 1987;31(3):465-492.
doi:10.1016/0040-5809(87)90016-5
apa: Rouhani, S., & Barton, N. H. (1987). Speciation and the "shifting
balance" in a continuous population. Theoretical Population Biology.
Elsevier. https://doi.org/10.1016/0040-5809(87)90016-5
chicago: Rouhani, Shahin, and Nicholas H Barton. “Speciation and the "Shifting
Balance" in a Continuous Population.” Theoretical Population Biology.
Elsevier, 1987. https://doi.org/10.1016/0040-5809(87)90016-5.
ieee: S. Rouhani and N. H. Barton, “Speciation and the "shifting balance"
in a continuous population,” Theoretical Population Biology, vol. 31, no.
3. Elsevier, pp. 465–492, 1987.
ista: Rouhani S, Barton NH. 1987. Speciation and the "shifting balance"
in a continuous population. Theoretical Population Biology. 31(3), 465–492.
mla: Rouhani, Shahin, and Nicholas H. Barton. “Speciation and the "Shifting
Balance" in a Continuous Population.” Theoretical Population Biology,
vol. 31, no. 3, Elsevier, 1987, pp. 465–92, doi:10.1016/0040-5809(87)90016-5.
short: S. Rouhani, N.H. Barton, Theoretical Population Biology 31 (1987) 465–492.
date_created: 2018-12-11T12:04:28Z
date_published: 1987-06-01T00:00:00Z
date_updated: 2022-02-04T12:30:10Z
day: '01'
doi: 10.1016/0040-5809(87)90016-5
extern: '1'
intvolume: ' 31'
issue: '3'
language:
- iso: eng
main_file_link:
- url: https://www.sciencedirect.com/science/article/pii/0040580987900165?via%3Dihub
month: '06'
oa_version: None
page: 465 - 492
publication: Theoretical Population Biology
publication_identifier:
eissn:
- 1096-0325
issn:
- 0040-5809
publication_status: published
publisher: Elsevier
publist_id: '2726'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Speciation and the "shifting balance" in a continuous population
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 31
year: '1987'
...
---
_id: '3658'
abstract:
- lang: eng
text: Females of the grasshopper Podisima pedestris were collected from the middle
of a hybrid zone between two chromosomal races in the Alpes Maritimes. They had
already mated in the field, and could therefore lay fertilised eggs in the laboratory.
The embryos were karyotyped, and found to contain an excess of chromosomal homozygotes.
No evidence of assortative mating was found from copulating pairs taken in the
field. The excess appears to have been caused by a combination of multiple insemination
and assortative fertilisation. The genetics of the assortment, and the implications
for the evolution of reproductive isolation are discussed.
acknowledgement: "We are most grateful to Manse East for excellent technical assistance,
to Dr Michael Shaw and Martin Dransfield for statistical advice and to Dr Roger
Butlin for critical reading of the manuscript. It is a pleasure to thank M. and
Mme. Aviotti and family at Casterino for their help and hospitality over several
years of field work. The authorities of Le Parc National de Mercantour kindly gave
permission for the collections. This work was financed by grants from the N.E.R.C.
and S.E.R.C.\r\n"
article_processing_charge: No
article_type: original
author:
- first_name: Godfrey
full_name: Hewitt, Godfrey
last_name: Hewitt
- first_name: R.
full_name: Nichols, R.
last_name: Nichols
- 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: Hewitt G, Nichols R, Barton NH. Homogamy in a hybrid zone in the alpine grasshopper
Podisma pedestris. Heredity. 1987;59(3):457-466. doi:10.1038/hdy.1987.156
apa: Hewitt, G., Nichols, R., & Barton, N. H. (1987). Homogamy in a hybrid zone
in the alpine grasshopper Podisma pedestris. Heredity. Nature Publishing
Group. https://doi.org/10.1038/hdy.1987.156
chicago: Hewitt, Godfrey, R. Nichols, and Nicholas H Barton. “Homogamy in a Hybrid
Zone in the Alpine Grasshopper Podisma Pedestris.” Heredity. Nature Publishing
Group, 1987. https://doi.org/10.1038/hdy.1987.156.
ieee: G. Hewitt, R. Nichols, and N. H. Barton, “Homogamy in a hybrid zone in the
alpine grasshopper Podisma pedestris,” Heredity, vol. 59, no. 3. Nature
Publishing Group, pp. 457–466, 1987.
ista: Hewitt G, Nichols R, Barton NH. 1987. Homogamy in a hybrid zone in the alpine
grasshopper Podisma pedestris. Heredity. 59(3), 457–466.
mla: Hewitt, Godfrey, et al. “Homogamy in a Hybrid Zone in the Alpine Grasshopper
Podisma Pedestris.” Heredity, vol. 59, no. 3, Nature Publishing Group,
1987, pp. 457–66, doi:10.1038/hdy.1987.156.
short: G. Hewitt, R. Nichols, N.H. Barton, Heredity 59 (1987) 457–466.
date_created: 2018-12-11T12:04:28Z
date_published: 1987-12-01T00:00:00Z
date_updated: 2022-02-04T12:20:46Z
day: '01'
doi: 10.1038/hdy.1987.156
extern: '1'
intvolume: ' 59'
issue: '3'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://www.nature.com/articles/hdy1987156
month: '12'
oa: 1
oa_version: Published Version
page: 457 - 466
publication: Heredity
publication_identifier:
eissn:
- 1365-2540
issn:
- 0018-067X
publication_status: published
publisher: Nature Publishing Group
publist_id: '2725'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Homogamy in a hybrid zone in the alpine grasshopper Podisma pedestris
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 59
year: '1987'
...
---
_id: '3659'
abstract:
- lang: eng
text: We develop models of the rates of evolution at sex-linked and autosomal loci
and of the rates of fixation of chromosomal rearrangements involving sex chromosomes
and autosomes. We show that the substitution of selectively favorable mutations
often proceeds more rapidly for X- or Y-linked loci than for the autosomes, provided
that mutations are recessive or partially recessive on the average. Selection
acting on a quantitative character is expected to result in similar long-term
rates of gene substitution for X-linked and autosomal loci, unless there is strong
directional dominance. Short-term responses to such selection often preferentially
fix alleles at autosomal loci. The fixation of slightly deleterious alleles by
random drift and the stochastic turnover of alleles at loci controlling quantitative
characters under stabilizing selection usually proceed somewhat more slowly at
sex-linked loci. In contrast, the fixation of underdominant chromosomal rearrangements
by random genetic drift is faster with sex linkage. Sex-specific selection may
also differentially favor the fixation of sex-linked rearrangements. These results
are discussed in relation to genetic and cytological data on species differences.
We show that the frequently disproportionate effects of the sex chromosomes on
interspecific inviability or sterility are consistent with the hypothesis that
the gene differences concerned involve recessive or partially recessive alleles
fixed by selection. Haldane's rule is readily interpreted in this light. There
is little evidence for strong effects of the sex chromosomes on quantitative characters
in interspecific crosses, in accordance with our theoretical results. Thus, the
evolution of reproductive isolation may not be the byproduct of selective change
in additively inherited, polygenic traits. Rather, it may be due mainly to the
fixation of favorable mutations whose effects on fitness reflect locus-specific
effects on the phenotype. These mutations behave as major genes in the sense of
contributing the bulk of the genetic variance in the characters that they control
during the course of the mutations' substitution. The data on the genetics of
short-term responses to selection in Drosophila are hard to interpret, but, in
accordance with theory, these responses do not usually seem to involve the X chromosome
disproportionately. In some groups, there is evidence for a disproportionate role
of the sex chromosomes in chromosomal changes, but others show no clear pattern.
Factors that may distort the expectations of the simple models of chromosomal
evolution are discussed.
article_processing_charge: No
article_type: original
author:
- first_name: Brian
full_name: Charlesworth, Brian
last_name: Charlesworth
- first_name: Jerry
full_name: Coyne, Jerry
last_name: Coyne
- 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: Charlesworth B, Coyne J, Barton NH. The relative rates of evolution of sex
chromosomes and autosomes. American Naturalist. 1987;130(1):113-146. doi:10.1086/284701
apa: Charlesworth, B., Coyne, J., & Barton, N. H. (1987). The relative rates
of evolution of sex chromosomes and autosomes. American Naturalist. University
of Chicago Press. https://doi.org/10.1086/284701
chicago: Charlesworth, Brian, Jerry Coyne, and Nicholas H Barton. “The Relative
Rates of Evolution of Sex Chromosomes and Autosomes.” American Naturalist.
University of Chicago Press, 1987. https://doi.org/10.1086/284701.
ieee: B. Charlesworth, J. Coyne, and N. H. Barton, “The relative rates of evolution
of sex chromosomes and autosomes,” American Naturalist, vol. 130, no. 1.
University of Chicago Press, pp. 113–146, 1987.
ista: Charlesworth B, Coyne J, Barton NH. 1987. The relative rates of evolution
of sex chromosomes and autosomes. American Naturalist. 130(1), 113–146.
mla: Charlesworth, Brian, et al. “The Relative Rates of Evolution of Sex Chromosomes
and Autosomes.” American Naturalist, vol. 130, no. 1, University of Chicago
Press, 1987, pp. 113–46, doi:10.1086/284701.
short: B. Charlesworth, J. Coyne, N.H. Barton, American Naturalist 130 (1987) 113–146.
date_created: 2018-12-11T12:04:29Z
date_published: 1987-01-01T00:00:00Z
date_updated: 2022-02-04T12:11:20Z
day: '01'
doi: 10.1086/284701
extern: '1'
intvolume: ' 130'
issue: '1'
language:
- iso: eng
main_file_link:
- url: ' http://www.jstor.org/stable/2461884'
month: '01'
oa_version: None
page: 113 - 146
publication: American Naturalist
publication_identifier:
eissn:
- 1537-5323
issn:
- 0003-0147
publication_status: published
publisher: University of Chicago Press
publist_id: '2724'
quality_controlled: '1'
status: public
title: The relative rates of evolution of sex chromosomes and autosomes
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 130
year: '1987'
...
---
_id: '3660'
abstract:
- lang: eng
text: "The maintenance of polygenic variability by a balance between mutation and
stabilizing selection has been analysed using two approximations: the ‘Gaussian’
and the ‘house of cards’. These lead to qualitatively different relationships
between the equilibrium genetic variance and the parameters describing selection
and mutation. Here we generalize these approximations to describe the dynamics
of genetic means and variances under arbitrary patterns of selection and mutation.
We incorporate genetic drift into the same mathematical framework.\r\nThe effects
of frequency-independent selection and genetic drift can be determined from the
gradient of log mean fitness and a covariance matrix that depends on genotype
frequencies. These equations describe an ‘adaptive landscape’, with a natural
metric of genetic distance set by the covariance matrix. From this representation
we can change coordinates to derive equations describing the dynamics of an additive
polygenic character in terms of the moments (means, variances, …) of allelic effects
at individual loci. Only under certain simplifying conditions, such as those derived
from the Gaussian and house-of-cards approximations, do these general recursions
lead to tractable equations for the first few phenotypic moments. The alternative
approximations differ in the constraints they impose on the distributions of allelic
effects at individual loci. The Gaussian-based prediction that evolution of the
phenotypic mean does not change the genetic variance is shown to be a consequence
of the assumption that the allelic distributions are never skewed. We present
both analytical and numerical results delimiting the parameter values consistent
with our approximations."
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: Michael
full_name: Turelli, Michael
last_name: Turelli
citation:
ama: Barton NH, Turelli M. Adaptive landscapes, genetic distance, and the evolution
of quantitative characters. Genetical Research. 1987;49(2):157-174. doi:10.1017/S0016672300026951
apa: Barton, N. H., & Turelli, M. (1987). Adaptive landscapes, genetic distance,
and the evolution of quantitative characters. Genetical Research. Cambridge
University Press. https://doi.org/10.1017/S0016672300026951
chicago: Barton, Nicholas H, and Michael Turelli. “Adaptive Landscapes, Genetic
Distance, and the Evolution of Quantitative Characters.” Genetical Research.
Cambridge University Press, 1987. https://doi.org/10.1017/S0016672300026951.
ieee: N. H. Barton and M. Turelli, “Adaptive landscapes, genetic distance, and the
evolution of quantitative characters,” Genetical Research, vol. 49, no.
2. Cambridge University Press, pp. 157–174, 1987.
ista: Barton NH, Turelli M. 1987. Adaptive landscapes, genetic distance, and the
evolution of quantitative characters. Genetical Research. 49(2), 157–174.
mla: Barton, Nicholas H., and Michael Turelli. “Adaptive Landscapes, Genetic Distance,
and the Evolution of Quantitative Characters.” Genetical Research, vol.
49, no. 2, Cambridge University Press, 1987, pp. 157–74, doi:10.1017/S0016672300026951.
short: N.H. Barton, M. Turelli, Genetical Research 49 (1987) 157–174.
date_created: 2018-12-11T12:04:29Z
date_published: 1987-04-01T00:00:00Z
date_updated: 2022-02-04T10:54:31Z
day: '01'
doi: 10.1017/S0016672300026951
extern: '1'
intvolume: ' 49'
issue: '2'
language:
- iso: eng
main_file_link:
- url: https://www.cambridge.org/core/journals/genetics-research/article/adaptive-landscapes-genetic-distance-and-the-evolution-of-quantitative-characters/25C2D277AC7554F805D67F6C32579549
month: '04'
oa_version: None
page: 157 - 174
publication: Genetical Research
publication_identifier:
eissn:
- 1469-5073
issn:
- 0016-6723
publication_status: published
publisher: Cambridge University Press
publist_id: '2723'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Adaptive landscapes, genetic distance, and the evolution of quantitative characters
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 49
year: '1987'
...
---
_id: '3661'
abstract:
- lang: eng
text: We derive a formula giving thefrequency with which random drift shifts a population
betweenalternativeequilibria. This formula is valid when such shifts are rare
(Ns >> 1), and applies over a wide range of mutation rates. When the number
of mutations entering the population is low (4Nμ << 1), the rate of stochastic
shifts reduces to the product ofthe mutation rate and the probability of fixation
of a single mutation. However, when many mutations enter the population in each
generation (4Nμ >> 1), the rate is higher than would be expected if mutations
were established independently, and converges to that given by a gaussian approximation.
We apply recent results on bistable systems to extend this formula to the general
multidimensional case. This gives an explicit expression for thefrequencyof stochastic
shifts, which depends only on theequilibrium probability distribution near the
saddle point separating thealternative stable states. The plausibility of theories
of speciation through random drift are discussed in the light of these results.
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: Shahin
full_name: Rouhani, Shahin
last_name: Rouhani
citation:
ama: Barton NH, Rouhani S. The frequency of shifts between alternative equilibria.
Journal of Theoretical Biology. 1987;125(4):397-418. doi:10.1016/S0022-5193(87)80210-2
apa: Barton, N. H., & Rouhani, S. (1987). The frequency of shifts between alternative
equilibria. Journal of Theoretical Biology. Elsevier. https://doi.org/10.1016/S0022-5193(87)80210-2
chicago: Barton, Nicholas H, and Shahin Rouhani. “The Frequency of Shifts between
Alternative Equilibria.” Journal of Theoretical Biology. Elsevier, 1987.
https://doi.org/10.1016/S0022-5193(87)80210-2.
ieee: N. H. Barton and S. Rouhani, “The frequency of shifts between alternative
equilibria,” Journal of Theoretical Biology, vol. 125, no. 4. Elsevier,
pp. 397–418, 1987.
ista: Barton NH, Rouhani S. 1987. The frequency of shifts between alternative equilibria.
Journal of Theoretical Biology. 125(4), 397–418.
mla: Barton, Nicholas H., and Shahin Rouhani. “The Frequency of Shifts between Alternative
Equilibria.” Journal of Theoretical Biology, vol. 125, no. 4, Elsevier,
1987, pp. 397–418, doi:10.1016/S0022-5193(87)80210-2.
short: N.H. Barton, S. Rouhani, Journal of Theoretical Biology 125 (1987) 397–418.
date_created: 2018-12-11T12:04:29Z
date_published: 1987-04-21T00:00:00Z
date_updated: 2022-02-04T10:39:15Z
day: '21'
doi: 10.1016/S0022-5193(87)80210-2
extern: '1'
intvolume: ' 125'
issue: '4'
language:
- iso: eng
main_file_link:
- url: https://www.sciencedirect.com/science/article/pii/S0022519387802102?via%3Dihub
month: '04'
oa_version: None
page: 397 - 418
publication: Journal of Theoretical Biology
publication_identifier:
eissn:
- 1095-8541
issn:
- 0022-5193
publication_status: published
publisher: Elsevier
publist_id: '2722'
status: public
title: The frequency of shifts between alternative equilibria
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 125
year: '1987'
...
---
_id: '3900'
abstract:
- lang: eng
text: Computational geometry as an area of research in its own right emerged in
the early seventies of this century. Right from the beginning, it was obvious
that strong connections of various kinds exist to questions studied in the considerably
older field of combinatorial geometry. For example, the combinatorial structure
of a geometric problem usually decides which algorithmic method solves the problem
most efficiently. Furthermore, the analysis of an algorithm often requires a great
deal of combinatorial knowledge. As it turns out, however, the connection between
the two research areas commonly referred to as computa tional geometry and combinatorial
geometry is not as lop-sided as it appears. Indeed, the interest in computational
issues in geometry gives a new and con structive direction to the combinatorial
study of geometry. It is the intention of this book to demonstrate that computational
and com binatorial investigations in geometry are doomed to profit from each
other. To reach this goal, I designed this book to consist of three parts, acorn
binatorial part, a computational part, and one that presents applications of the
results of the first two parts. The choice of the topics covered in this book
was guided by my attempt to describe the most fundamental algorithms in computational
geometry that have an interesting combinatorial structure. In this early stage
geometric transforms played an important role as they reveal connections between
seemingly unrelated problems and thus help to structure the field.
alternative_title:
- EATCS monographs on theoretical computer science
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. Algorithms in Combinatorial Geometry. Vol 10. Berlin ;
Heidelberg: Springer; 1987. doi:10.1007/978-3-642-61568-9'
apa: 'Edelsbrunner, H. (1987). Algorithms in Combinatorial Geometry (Vol.
10). Berlin ; Heidelberg: Springer. https://doi.org/10.1007/978-3-642-61568-9'
chicago: 'Edelsbrunner, Herbert. Algorithms in Combinatorial Geometry. Vol.
10. Berlin ; Heidelberg: Springer, 1987. https://doi.org/10.1007/978-3-642-61568-9.'
ieee: 'H. Edelsbrunner, Algorithms in Combinatorial Geometry, vol. 10. Berlin ;
Heidelberg: Springer, 1987.'
ista: 'Edelsbrunner H. 1987. Algorithms in Combinatorial Geometry, Berlin ; Heidelberg:
Springer, XV, 423p.'
mla: Edelsbrunner, Herbert. Algorithms in Combinatorial Geometry. Vol. 10,
Springer, 1987, doi:10.1007/978-3-642-61568-9.
short: H. Edelsbrunner, Algorithms in Combinatorial Geometry, Springer, Berlin ;
Heidelberg, 1987.
date_created: 2018-12-11T12:05:47Z
date_published: 1987-01-01T00:00:00Z
date_updated: 2021-12-22T12:59:57Z
day: '01'
doi: 10.1007/978-3-642-61568-9
extern: '1'
intvolume: ' 10'
language:
- iso: eng
month: '01'
oa_version: None
page: XV, 423
place: Berlin ; Heidelberg
publication_identifier:
eisbn:
- 978-3-642-61568-9
isbn:
- 978-3-540-13722-1
issn:
- 1431-2654
publication_status: published
publisher: Springer
publist_id: '2257'
quality_controlled: '1'
related_material:
link:
- description: available via catalog IST BookList
relation: other
url: https://koha.app.ist.ac.at/cgi-bin/koha/opac-detail.pl?biblionumber=4096
status: public
title: Algorithms in Combinatorial Geometry
type: book
user_id: 8b945eb4-e2f2-11eb-945a-df72226e66a9
volume: 10
year: '1987'
...
---
_id: '4094'
abstract:
- lang: eng
text: The visibility graph of a finite set of line segments in the plane connects
two endpoints u and v if and only if the straight line connection between u and
v does not cross any line segment of the set. This article proves that 5n - 4
is a lower bound on the number of edges in the visibility graph of n nonintersecting
line segments in the plane. This bound is tight.
acknowledgement: "Research of this author ‘was supported by the Amoco Foundation for
Facilitation of Development of Computer\r\nScience under Grant No. l-6-44862."
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: Xiaojun
full_name: Shen, Xiaojun
last_name: Shen
citation:
ama: Edelsbrunner H, Shen X. A tight lower bound on the size of visibility graphs.
Information Processing Letters. 1987;26(2):61-64. doi:10.1016/0020-0190(87)90038-X
apa: Edelsbrunner, H., & Shen, X. (1987). A tight lower bound on the size of
visibility graphs. Information Processing Letters. Elsevier. https://doi.org/10.1016/0020-0190(87)90038-X
chicago: Edelsbrunner, Herbert, and Xiaojun Shen. “A Tight Lower Bound on the Size
of Visibility Graphs.” Information Processing Letters. Elsevier, 1987.
https://doi.org/10.1016/0020-0190(87)90038-X.
ieee: H. Edelsbrunner and X. Shen, “A tight lower bound on the size of visibility
graphs,” Information Processing Letters, vol. 26, no. 2. Elsevier, pp.
61–64, 1987.
ista: Edelsbrunner H, Shen X. 1987. A tight lower bound on the size of visibility
graphs. Information Processing Letters. 26(2), 61–64.
mla: Edelsbrunner, Herbert, and Xiaojun Shen. “A Tight Lower Bound on the Size of
Visibility Graphs.” Information Processing Letters, vol. 26, no. 2, Elsevier,
1987, pp. 61–64, doi:10.1016/0020-0190(87)90038-X.
short: H. Edelsbrunner, X. Shen, Information Processing Letters 26 (1987) 61–64.
date_created: 2018-12-11T12:06:54Z
date_published: 1987-10-19T00:00:00Z
date_updated: 2022-02-03T14:05:19Z
day: '19'
doi: 10.1016/0020-0190(87)90038-X
extern: '1'
intvolume: ' 26'
issue: '2'
language:
- iso: eng
main_file_link:
- url: https://www.sciencedirect.com/science/article/pii/002001908790038X?via%3Dihub
month: '10'
oa_version: None
page: 61 - 64
publication: Information Processing Letters
publication_identifier:
eissn:
- 1872-6119
issn:
- 0020-0190
publication_status: published
publisher: Elsevier
publist_id: '2025'
quality_controlled: '1'
scopus_import: '1'
status: public
title: A tight lower bound on the size of visibility graphs
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 26
year: '1987'
...
---
_id: '4095'
abstract:
- lang: eng
text: he kth-order Voronoi diagram of a finite set of sites in the Euclidean plane
E2 subdivides E2 into maximal regions such that all points within a given region
have the same k nearest sites. Two versions of an algorithm are developed for
constructing the kth-order Voronoi diagram of a set of n sites in O(n2 log n +
k(n - k) log2 n) time, O(k(n - k)) storage, and in O(n2 + k(n - k) log2 n) time,
O(n2) storage, respectively.
acknowledgement: 'We would like to thank two anonymous referees for their constructive
criticism. '
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. An improved algorithm for constructing kth-order
Voronoi diagrams. IEEE Transactions on Computers. 1987;36(11):1349-1354.
doi:10.1109/TC.1987.5009474
apa: Chazelle, B., & Edelsbrunner, H. (1987). An improved algorithm for constructing
kth-order Voronoi diagrams. IEEE Transactions on Computers. IEEE. https://doi.org/10.1109/TC.1987.5009474
chicago: Chazelle, Bernard, and Herbert Edelsbrunner. “An Improved Algorithm for
Constructing Kth-Order Voronoi Diagrams.” IEEE Transactions on Computers.
IEEE, 1987. https://doi.org/10.1109/TC.1987.5009474.
ieee: B. Chazelle and H. Edelsbrunner, “An improved algorithm for constructing kth-order
Voronoi diagrams,” IEEE Transactions on Computers, vol. 36, no. 11. IEEE,
pp. 1349–1354, 1987.
ista: Chazelle B, Edelsbrunner H. 1987. An improved algorithm for constructing kth-order
Voronoi diagrams. IEEE Transactions on Computers. 36(11), 1349–1354.
mla: Chazelle, Bernard, and Herbert Edelsbrunner. “An Improved Algorithm for Constructing
Kth-Order Voronoi Diagrams.” IEEE Transactions on Computers, vol. 36, no.
11, IEEE, 1987, pp. 1349–54, doi:10.1109/TC.1987.5009474.
short: B. Chazelle, H. Edelsbrunner, IEEE Transactions on Computers 36 (1987) 1349–1354.
date_created: 2018-12-11T12:06:54Z
date_published: 1987-11-01T00:00:00Z
date_updated: 2022-02-04T10:32:27Z
day: '01'
doi: 10.1109/TC.1987.5009474
extern: '1'
intvolume: ' 36'
issue: '11'
language:
- iso: eng
main_file_link:
- url: https://ieeexplore.ieee.org/document/5009474
month: '11'
oa_version: None
page: 1349 - 1354
publication: IEEE Transactions on Computers
publication_identifier:
eissn:
- 1557-9956
issn:
- 0018-9340
publication_status: published
publisher: IEEE
publist_id: '2026'
quality_controlled: '1'
scopus_import: '1'
status: public
title: An improved algorithm for constructing kth-order Voronoi diagrams
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 36
year: '1987'
...
---
_id: '4100'
abstract:
- lang: eng
text: "This paper investigates the existence of linear space data structures for
range searching. We examine thehomothetic range search problem, where a setS ofn
points in the plane is to be preprocessed so that for any triangleT with sides
parallel to three fixed directions the points ofS that lie inT can be computed
efficiently. We also look atdomination searching in three dimensions. In this
problem,S is a set ofn points inE 3 and the question is to retrieve all points
ofS that are dominated by some query point. We describe linear space data structures
for both problems. The query time is optimal in the first case and nearly optimal
in the second.\r\n"
acknowledgement: This research was conducted while the first author was with Brown
University and the second author was with the Technical University of Graz, Austria.
The first author was supported in part by NSF Grant MCS 83-03925.
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. Linear space data structures for two types of range
search. Discrete & Computational Geometry. 1987;2(1):113-126. doi:10.1007/BF02187875
apa: Chazelle, B., & Edelsbrunner, H. (1987). Linear space data structures for
two types of range search. Discrete & Computational Geometry. Springer.
https://doi.org/10.1007/BF02187875
chicago: Chazelle, Bernard, and Herbert Edelsbrunner. “Linear Space Data Structures
for Two Types of Range Search.” Discrete & Computational Geometry.
Springer, 1987. https://doi.org/10.1007/BF02187875.
ieee: B. Chazelle and H. Edelsbrunner, “Linear space data structures for two types
of range search,” Discrete & Computational Geometry, vol. 2, no. 1.
Springer, pp. 113–126, 1987.
ista: Chazelle B, Edelsbrunner H. 1987. Linear space data structures for two types
of range search. Discrete & Computational Geometry. 2(1), 113–126.
mla: Chazelle, Bernard, and Herbert Edelsbrunner. “Linear Space Data Structures
for Two Types of Range Search.” Discrete & Computational Geometry,
vol. 2, no. 1, Springer, 1987, pp. 113–26, doi:10.1007/BF02187875.
short: B. Chazelle, H. Edelsbrunner, Discrete & Computational Geometry 2 (1987)
113–126.
date_created: 2018-12-11T12:06:56Z
date_published: 1987-01-01T00:00:00Z
date_updated: 2022-02-03T11:07:26Z
day: '01'
doi: 10.1007/BF02187875
extern: '1'
intvolume: ' 2'
issue: '1'
language:
- iso: eng
month: '01'
oa_version: None
page: 113 - 126
publication: Discrete & Computational Geometry
publication_identifier:
eissn:
- 1432-0444
issn:
- 0179-5376
publication_status: published
publisher: Springer
publist_id: '2022'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Linear space data structures for two types of range search
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 2
year: '1987'
...
---
_id: '4101'
abstract:
- lang: eng
text: In a number of recent papers, techniques from computational geometry (the
field of algorithm design that deals with objects in multi-dimensional space)
have been applied to some problems in the area of computer graphics. In this way,
efficient solutions were obtained for the windowing problem that asks for those
line segments in a planar set that lie in given window (range) and the moving
problem that asks for the first line segment that comes into the window when moving
the window in some direction. In this paper we show that also the zooming problem,
which asks for the first line segment that comes into the window when we enlarge
it, can be solved efficiently. This is done by repeatedly performing range queries
with ranges of varying sizes. The obtained structure is dynamic and yields a query
time of O(log2n) and an insertion and deletion time of O(log2n), where n is the
number of line segments in the set. The amount of storage required is O(n log
n). It is also shown that the technique of repeated range search can be used to
solve several other problems efficiently.
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. Zooming by repeated range detection. Information
Processing Letters. 1987;24(6):413-417. doi:10.1016/0020-0190(87)90120-7
apa: Edelsbrunner, H., & Overmars, M. (1987). Zooming by repeated range detection.
Information Processing Letters. Elsevier. https://doi.org/10.1016/0020-0190(87)90120-7
chicago: Edelsbrunner, Herbert, and Mark Overmars. “Zooming by Repeated Range Detection.”
Information Processing Letters. Elsevier, 1987. https://doi.org/10.1016/0020-0190(87)90120-7.
ieee: H. Edelsbrunner and M. Overmars, “Zooming by repeated range detection,” Information
Processing Letters, vol. 24, no. 6. Elsevier, pp. 413–417, 1987.
ista: Edelsbrunner H, Overmars M. 1987. Zooming by repeated range detection. Information
Processing Letters. 24(6), 413–417.
mla: Edelsbrunner, Herbert, and Mark Overmars. “Zooming by Repeated Range Detection.”
Information Processing Letters, vol. 24, no. 6, Elsevier, 1987, pp. 413–17,
doi:10.1016/0020-0190(87)90120-7.
short: H. Edelsbrunner, M. Overmars, Information Processing Letters 24 (1987) 413–417.
date_created: 2018-12-11T12:06:57Z
date_published: 1987-04-06T00:00:00Z
date_updated: 2022-02-03T13:29:17Z
day: '06'
doi: 10.1016/0020-0190(87)90120-7
extern: '1'
intvolume: ' 24'
issue: '6'
language:
- iso: eng
main_file_link:
- url: https://www.sciencedirect.com/science/article/pii/0020019087901207?via%3Dihub
month: '04'
oa_version: None
page: 413 - 417
publication: Information Processing Letters
publication_identifier:
eissn:
- 1872-6119
issn:
- 0020-0190
publication_status: published
publisher: Elsevier
publist_id: '2023'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Zooming by repeated range detection
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 24
year: '1987'
...
---
_id: '4102'
abstract:
- lang: eng
text: Determining or counting geometric objects that intersect another geometric
query object is at the core of algorithmic problems in a number of applied areas
of computer science. This article presents a family of space-efficient data structures
that realize sublinear query time for points, line segments, lines and polygons
in the plane, and points, line segments, planes, and polyhedra in three dimensions.
article_processing_charge: No
article_type: original
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. Space searching for intersecting objects. Journal
of Algorithms. 1987;8(3):348-361. doi:10.1016/0196-6774(87)90015-0
apa: Dobkin, D., & Edelsbrunner, H. (1987). Space searching for intersecting
objects. Journal of Algorithms. Academic Press. https://doi.org/10.1016/0196-6774(87)90015-0
chicago: Dobkin, David, and Herbert Edelsbrunner. “Space Searching for Intersecting
Objects.” Journal of Algorithms. Academic Press, 1987. https://doi.org/10.1016/0196-6774(87)90015-0.
ieee: D. Dobkin and H. Edelsbrunner, “Space searching for intersecting objects,”
Journal of Algorithms, vol. 8, no. 3. Academic Press, pp. 348–361, 1987.
ista: Dobkin D, Edelsbrunner H. 1987. Space searching for intersecting objects.
Journal of Algorithms. 8(3), 348–361.
mla: Dobkin, David, and Herbert Edelsbrunner. “Space Searching for Intersecting
Objects.” Journal of Algorithms, vol. 8, no. 3, Academic Press, 1987, pp.
348–61, doi:10.1016/0196-6774(87)90015-0.
short: D. Dobkin, H. Edelsbrunner, Journal of Algorithms 8 (1987) 348–361.
date_created: 2018-12-11T12:06:57Z
date_published: 1987-09-01T00:00:00Z
date_updated: 2022-02-03T13:47:53Z
day: '01'
doi: 10.1016/0196-6774(87)90015-0
extern: '1'
intvolume: ' 8'
issue: '3'
language:
- iso: eng
main_file_link:
- url: https://www.sciencedirect.com/science/article/pii/0196677487900150?via%3Dihub
month: '09'
oa_version: None
page: 348 - 361
publication: Journal of Algorithms
publication_identifier:
eissn:
- 1090-2678
issn:
- 0196-6774
publication_status: published
publisher: Academic Press
publist_id: '2024'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Space searching for intersecting objects
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 8
year: '1987'
...