---
_id: '4086'
abstract:
- lang: eng
  text: This note proves that the maximum number of faces (of any dimension) of the
    upper envelope of a set ofn possibly intersectingd-simplices ind+1 dimensions
    is (n d (n)). This is an extension of a result of Pach and Sharir [PS] who prove
    the same bound for the number ofd-dimensional faces of the upper envelope.
acknowledgement: "This work was supported by Amoco Fnd. Fac. Dev. Comput. Sci. 1-6-44862
  and by the National Science Foundation under Grant CCR-8714565. Research on the
  presented result was partially carried out while the author worked for the IBM T.
  J. Watson Research Center at Yorktown Height, New York, USA. \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
citation:
  ama: 'Edelsbrunner H. The upper envelope of piecewise linear functions: Tight bounds
    on the number of faces . <i>Discrete &#38; Computational Geometry</i>. 1989;4(4):337-343.
    doi:<a href="https://doi.org/10.1007/BF02187734">10.1007/BF02187734</a>'
  apa: 'Edelsbrunner, H. (1989). The upper envelope of piecewise linear functions:
    Tight bounds on the number of faces . <i>Discrete &#38; Computational Geometry</i>.
    Springer. <a href="https://doi.org/10.1007/BF02187734">https://doi.org/10.1007/BF02187734</a>'
  chicago: 'Edelsbrunner, Herbert. “The Upper Envelope of Piecewise Linear Functions:
    Tight Bounds on the Number of Faces .” <i>Discrete &#38; Computational Geometry</i>.
    Springer, 1989. <a href="https://doi.org/10.1007/BF02187734">https://doi.org/10.1007/BF02187734</a>.'
  ieee: 'H. Edelsbrunner, “The upper envelope of piecewise linear functions: Tight
    bounds on the number of faces ,” <i>Discrete &#38; Computational Geometry</i>,
    vol. 4, no. 4. Springer, pp. 337–343, 1989.'
  ista: 'Edelsbrunner H. 1989. The upper envelope of piecewise linear functions: Tight
    bounds on the number of faces . Discrete &#38; Computational Geometry. 4(4), 337–343.'
  mla: 'Edelsbrunner, Herbert. “The Upper Envelope of Piecewise Linear Functions:
    Tight Bounds on the Number of Faces .” <i>Discrete &#38; Computational Geometry</i>,
    vol. 4, no. 4, Springer, 1989, pp. 337–43, doi:<a href="https://doi.org/10.1007/BF02187734">10.1007/BF02187734</a>.'
  short: H. Edelsbrunner, Discrete &#38; Computational Geometry 4 (1989) 337–343.
date_created: 2018-12-11T12:06:51Z
date_published: 1989-11-01T00:00:00Z
date_updated: 2022-02-10T11:08:12Z
day: '01'
doi: 10.1007/BF02187734
extern: '1'
intvolume: '         4'
issue: '4'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://link.springer.com/article/10.1007/BF02187734
month: '11'
oa: 1
oa_version: Published Version
page: 337 - 343
publication: Discrete & Computational Geometry
publication_identifier:
  eissn:
  - 1432-0444
  issn:
  - 0179-5376
publication_status: published
publisher: Springer
publist_id: '2034'
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'The upper envelope of piecewise linear functions: Tight bounds on the number
  of faces '
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 4
year: '1989'
...
---
_id: '4088'
abstract:
- lang: eng
  text: 'Anarrangement ofn lines (or line segments) in the plane is the partition
    of the plane defined by these objects. Such an arrangement consists ofO(n 2) regions,
    calledfaces. In this paper we study the problem of calculating and storing arrangementsimplicitly,
    using subquadratic space and preprocessing, so that, given any query pointp, we
    can calculate efficiently the face containingp. First, we consider the case of
    lines and show that with (n) space1 and (n 3/2) preprocessing time, we can answer
    face queries in (n)+O(K) time, whereK is the output size. (The query time is achieved
    with high probability.) In the process, we solve three interesting subproblems:
    (1) given a set ofn points, find a straight-edge spanning tree of these points
    such that any line intersects only a few edges of the tree, (2) given a simple
    polygonal path , form a data structure from which we can find the convex hull
    of any subpath of quickly, and (3) given a set of points, organize them so that
    the convex hull of their subset lying above a query line can be found quickly.
    Second, using random sampling, we give a tradeoff between increasing space and
    decreasing query time. Third, we extend our structure to report faces in an arrangement
    of line segments in (n 1/3)+O(K) time, given(n 4/3) space and (n 5/3) preprocessing
    time. Lastly, we note that our techniques allow us to computem faces in an arrangement
    ofn lines in time (m 2/3 n 2/3+n), which is nearly optimal.'
acknowledgement: The first author is pleased to acknowledge the support of Amoco Fnd.
  Fac. Dev. Comput. Sci. 1-6-44862 and National Science Foundation Grant CCR-8714565.
  Work on this paper by the fifth author has been supported by Office of Naval Research
  Grant N00014-87-K-0129, by National Science Foundation Grant NSF-DCR-83-20085, by
  grants from the Digital Equipment Corporation, and the IBM Corporation, and by a
  research grant from the NCRD—the Israeli National Council for Research and Development.
  The sixth author was supported in part by a National Science Foundation Graduate
  Fellowship. This work was begun while the non-DEC authors were visiting at the DEC
  Systems Research Center.
article_processing_charge: No
article_type: original
author:
- first_name: Herbert
  full_name: Edelsbrunner, Herbert
  id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
  last_name: Edelsbrunner
  orcid: 0000-0002-9823-6833
- first_name: Leonidas
  full_name: Guibas, Leonidas
  last_name: Guibas
- first_name: John
  full_name: Hershberger, John
  last_name: Hershberger
- first_name: Raimund
  full_name: Seidel, Raimund
  last_name: Seidel
- first_name: Micha
  full_name: Sharir, Micha
  last_name: Sharir
- first_name: Jack
  full_name: Snoeyink, Jack
  last_name: Snoeyink
- first_name: Emo
  full_name: Welzl, Emo
  last_name: Welzl
citation:
  ama: Edelsbrunner H, Guibas L, Hershberger J, et al. Implicitly representing arrangements
    of lines or segments. <i>Discrete &#38; Computational Geometry</i>. 1989;4(1):433-466.
    doi:<a href="https://doi.org/10.1007/BF02187742">10.1007/BF02187742</a>
  apa: Edelsbrunner, H., Guibas, L., Hershberger, J., Seidel, R., Sharir, M., Snoeyink,
    J., &#38; Welzl, E. (1989). Implicitly representing arrangements of lines or segments.
    <i>Discrete &#38; Computational Geometry</i>. Springer. <a href="https://doi.org/10.1007/BF02187742">https://doi.org/10.1007/BF02187742</a>
  chicago: Edelsbrunner, Herbert, Leonidas Guibas, John Hershberger, Raimund Seidel,
    Micha Sharir, Jack Snoeyink, and Emo Welzl. “Implicitly Representing Arrangements
    of Lines or Segments.” <i>Discrete &#38; Computational Geometry</i>. Springer,
    1989. <a href="https://doi.org/10.1007/BF02187742">https://doi.org/10.1007/BF02187742</a>.
  ieee: H. Edelsbrunner <i>et al.</i>, “Implicitly representing arrangements of lines
    or segments,” <i>Discrete &#38; Computational Geometry</i>, vol. 4, no. 1. Springer,
    pp. 433–466, 1989.
  ista: Edelsbrunner H, Guibas L, Hershberger J, Seidel R, Sharir M, Snoeyink J, Welzl
    E. 1989. Implicitly representing arrangements of lines or segments. Discrete &#38;
    Computational Geometry. 4(1), 433–466.
  mla: Edelsbrunner, Herbert, et al. “Implicitly Representing Arrangements of Lines
    or Segments.” <i>Discrete &#38; Computational Geometry</i>, vol. 4, no. 1, Springer,
    1989, pp. 433–66, doi:<a href="https://doi.org/10.1007/BF02187742">10.1007/BF02187742</a>.
  short: H. Edelsbrunner, L. Guibas, J. Hershberger, R. Seidel, M. Sharir, J. Snoeyink,
    E. Welzl, Discrete &#38; Computational Geometry 4 (1989) 433–466.
date_created: 2018-12-11T12:06:52Z
date_published: 1989-12-01T00:00:00Z
date_updated: 2022-02-10T15:03:48Z
day: '01'
doi: 10.1007/BF02187742
extern: '1'
intvolume: '         4'
issue: '1'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://link.springer.com/article/10.1007/BF02187742
month: '12'
oa: 1
oa_version: Published Version
page: 433 - 466
publication: Discrete & Computational Geometry
publication_identifier:
  eissn:
  - 1432-0444
  issn:
  - 0179-5376
publication_status: published
publisher: Springer
publist_id: '2036'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Implicitly representing arrangements of lines or segments
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 4
year: '1989'
...
---
_id: '4089'
abstract:
- lang: eng
  text: Motivated by a number of motion-planning questions, we investigate in this
    paper some general topological and combinatorial properties of the boundary of
    the union ofn regions bounded by Jordan curves in the plane. We show that, under
    some fairly weak conditions, a simply connected surface can be constructed that
    exactly covers this union and whose boundary has combinatorial complexity that
    is nearly linear, even though the covered region can have quadratic complexity.
    In the case where our regions are delimited by Jordan acrs in the upper halfplane
    starting and ending on thex-axis such that any pair of arcs intersect in at most
    three points, we prove that the total number of subarcs that appear on the boundary
    of the union is only (n(n)), where(n) is the extremely slowly growing functional
    inverse of Ackermann's function.
acknowledgement: The first author is pleased to acknowledge the support of Amoco Fnd.
  Fac. Dev. Comput. Sci. 1-6-44862 and National Science Foundation Grant CCR-8714565.
  Work on this paper by the fourth and seventh authors has been supported by Office
  of Naval Research Grant N00014-87-K-0129, by National Science Foundation Grant NSF-DCR-83-20085,
  and by grants from the Digital Equipment Corporation and the IBM Corporation. The
  seventh author in addition wishes to acknowledge support by a research grant from
  the NCRD—the Israeli National Council for Research and Development. The fifth author
  would like to acknowledge support in part by NSF grant DMS-8501947. Finally, the
  eighth author was supported in part by a National Science Foundation Graduate Fellowship.
article_processing_charge: No
article_type: original
author:
- first_name: Herbert
  full_name: Edelsbrunner, Herbert
  id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
  last_name: Edelsbrunner
  orcid: 0000-0002-9823-6833
- first_name: Leonidas
  full_name: Guibas, Leonidas
  last_name: Guibas
- first_name: John
  full_name: Hershberger, John
  last_name: Hershberger
- 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
- first_name: Jack
  full_name: Snoeyink, Jack
  last_name: Snoeyink
citation:
  ama: Edelsbrunner H, Guibas L, Hershberger J, et al. On arrangements of Jordan arcs
    with three intersections per pair. <i>Discrete &#38; Computational Geometry</i>.
    1989;4(1):523-539. doi:<a href="https://doi.org/10.1007/BF02187745">10.1007/BF02187745</a>
  apa: Edelsbrunner, H., Guibas, L., Hershberger, J., Pach, J., Pollack, R., Seidel,
    R., … Snoeyink, J. (1989). On arrangements of Jordan arcs with three intersections
    per pair. <i>Discrete &#38; Computational Geometry</i>. Springer. <a href="https://doi.org/10.1007/BF02187745">https://doi.org/10.1007/BF02187745</a>
  chicago: Edelsbrunner, Herbert, Leonidas Guibas, John Hershberger, János Pach, Richard
    Pollack, Raimund Seidel, Micha Sharir, and Jack Snoeyink. “On Arrangements of
    Jordan Arcs with Three Intersections per Pair.” <i>Discrete &#38; Computational
    Geometry</i>. Springer, 1989. <a href="https://doi.org/10.1007/BF02187745">https://doi.org/10.1007/BF02187745</a>.
  ieee: H. Edelsbrunner <i>et al.</i>, “On arrangements of Jordan arcs with three
    intersections per pair,” <i>Discrete &#38; Computational Geometry</i>, vol. 4,
    no. 1. Springer, pp. 523–539, 1989.
  ista: Edelsbrunner H, Guibas L, Hershberger J, Pach J, Pollack R, Seidel R, Sharir
    M, Snoeyink J. 1989. On arrangements of Jordan arcs with three intersections per
    pair. Discrete &#38; Computational Geometry. 4(1), 523–539.
  mla: Edelsbrunner, Herbert, et al. “On Arrangements of Jordan Arcs with Three Intersections
    per Pair.” <i>Discrete &#38; Computational Geometry</i>, vol. 4, no. 1, Springer,
    1989, pp. 523–39, doi:<a href="https://doi.org/10.1007/BF02187745">10.1007/BF02187745</a>.
  short: H. Edelsbrunner, L. Guibas, J. Hershberger, J. Pach, R. Pollack, R. Seidel,
    M. Sharir, J. Snoeyink, Discrete &#38; Computational Geometry 4 (1989) 523–539.
date_created: 2018-12-11T12:06:52Z
date_published: 1989-12-01T00:00:00Z
date_updated: 2022-02-10T15:40:04Z
day: '01'
doi: 10.1007/BF02187745
extern: '1'
intvolume: '         4'
issue: '1'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://link.springer.com/article/10.1007/BF02187745
month: '12'
oa: 1
oa_version: Published Version
page: 523 - 539
publication: Discrete & Computational Geometry
publication_identifier:
  eissn:
  - 1432-0444
  issn:
  - 0179-5376
publication_status: published
publisher: Springer
publist_id: '2037'
quality_controlled: '1'
scopus_import: '1'
status: public
title: On arrangements of Jordan arcs with three intersections per pair
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 4
year: '1989'
...
---
_id: '3655'
abstract:
- lang: eng
  text: "The structural basis and distribution of variation in the ribosomal RNA multigene
    family ( rDNA) was studied in the X0 and neo-XY races of the Alpine grasshopper
    Podisma pedestris. Restriction-enzyme sites in the gene region of the rDNA repeat
    were identical in both races and homogeneous in the rDNA family. In contrast,
    sites for Hind111 and PvuII in the intergenic spacer (IGS) region showed racial
    divergence and variation within the rDNA family and within populations. A short
    insertion in the 28s gene region was present in a minority of repeats in both
    races. The distributions of four polymorphic IGS Hind111 fragments were surveyed
    at 43 locations in and around the hybrid zone. Two of these fragments appear to
    be distributed as clines, one of which is strongly associated with the neo-X chromosome.
    The other two fragments show considerable variation in both races and show negative
    association. It is proposed that the clinally distributed variants arise from
    processes of amplification and divergence of IGS sequence variants and that such
    \r\ndivergence may contribute to hybrid inviability. "
acknowledgement: 'We thank Dr. W. Kunz for providing the clones pLm6F4 and pLm4Bll
  and Dr. D. Glover for the clone pDm238. We thank Brian Curtis for his photographic
  assistance. '
article_processing_charge: No
article_type: original
author:
- first_name: John
  full_name: Dallas, John
  last_name: Dallas
- 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: Gabriel
  full_name: Dover, Gabriel
  last_name: Dover
citation:
  ama: Dallas J, Barton NH, Dover G. Interracial rDNA variation in the grasshopper
    Podisma Pedestris. <i>Molecular Biology and Evolution</i>. 1988;5(6):660-674.
    doi:<a href="https://doi.org/10.1093/oxfordjournals.molbev.a040528">10.1093/oxfordjournals.molbev.a040528</a>
  apa: Dallas, J., Barton, N. H., &#38; Dover, G. (1988). Interracial rDNA variation
    in the grasshopper Podisma Pedestris. <i>Molecular Biology and Evolution</i>.
    Oxford University Press. <a href="https://doi.org/10.1093/oxfordjournals.molbev.a040528">https://doi.org/10.1093/oxfordjournals.molbev.a040528</a>
  chicago: Dallas, John, Nicholas H Barton, and Gabriel Dover. “Interracial RDNA Variation
    in the Grasshopper Podisma Pedestris.” <i>Molecular Biology and Evolution</i>.
    Oxford University Press, 1988. <a href="https://doi.org/10.1093/oxfordjournals.molbev.a040528">https://doi.org/10.1093/oxfordjournals.molbev.a040528</a>.
  ieee: J. Dallas, N. H. Barton, and G. Dover, “Interracial rDNA variation in the
    grasshopper Podisma Pedestris,” <i>Molecular Biology and Evolution</i>, vol. 5,
    no. 6. Oxford University Press, pp. 660–674, 1988.
  ista: Dallas J, Barton NH, Dover G. 1988. Interracial rDNA variation in the grasshopper
    Podisma Pedestris. Molecular Biology and Evolution. 5(6), 660–674.
  mla: Dallas, John, et al. “Interracial RDNA Variation in the Grasshopper Podisma
    Pedestris.” <i>Molecular Biology and Evolution</i>, vol. 5, no. 6, Oxford University
    Press, 1988, pp. 660–74, doi:<a href="https://doi.org/10.1093/oxfordjournals.molbev.a040528">10.1093/oxfordjournals.molbev.a040528</a>.
  short: J. Dallas, N.H. Barton, G. Dover, Molecular Biology and Evolution 5 (1988)
    660–674.
date_created: 2018-12-11T12:04:28Z
date_published: 1988-07-01T00:00:00Z
date_updated: 2022-02-08T13:20:51Z
day: '01'
doi: 10.1093/oxfordjournals.molbev.a040528
extern: '1'
intvolume: '         5'
issue: '6'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://academic.oup.com/mbe/article/5/6/660/1044340
month: '07'
oa: 1
oa_version: None
page: 660 - 674
publication: Molecular Biology and Evolution
publication_identifier:
  eissn:
  - 1537-1719
  issn:
  - 0737-4038
publication_status: published
publisher: Oxford University Press
publist_id: '2728'
quality_controlled: '1'
status: public
title: Interracial rDNA variation in the grasshopper Podisma Pedestris
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 5
year: '1988'
...
---
_id: '4090'
abstract:
- lang: eng
  text: In this paper we study the problem of polygonal separation in the plane, i.e.,
    finding a convex polygon with minimum number k of sides separating two given finite
    point sets (k-separator), if it exists. We show that for k = Θ(n),  is a lower
    bound to the running time of any algorithm for this problem, and exhibit two algorithms
    of distinctly different flavors. The first relies on an O(n log n)-time preprocessing
    task, which constructs the convex hull of the internal set and a nested star-shaped
    polygon determined by the external set; the k-separator is contained in the annulus
    between the boundaries of these two polygons and is constructed in additional
    linear time. The second algorithm adapts the prune-and-search approach, and constructs,
    in each iteration, one side of the separator; its running time is O(kn), but the
    separator may have one more side than the minimum.
acknowledgement: Research of the first author is supported by Amoco Fnd. Fat. Dev.
  Comput. Sci. l-6-44862; research of the second author is supported by NSF Grant
  ECS 84-10902.
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: Franco
  full_name: Preparata, Franco
  last_name: Preparata
citation:
  ama: Edelsbrunner H, Preparata F. Minimum polygonal separation. <i>Information and
    Computation</i>. 1988;77(3):218-232. doi:<a href="https://doi.org/10.1016/0890-5401(88)90049-1">10.1016/0890-5401(88)90049-1</a>
  apa: Edelsbrunner, H., &#38; Preparata, F. (1988). Minimum polygonal separation.
    <i>Information and Computation</i>. Elsevier. <a href="https://doi.org/10.1016/0890-5401(88)90049-1">https://doi.org/10.1016/0890-5401(88)90049-1</a>
  chicago: Edelsbrunner, Herbert, and Franco Preparata. “Minimum Polygonal Separation.”
    <i>Information and Computation</i>. Elsevier, 1988. <a href="https://doi.org/10.1016/0890-5401(88)90049-1">https://doi.org/10.1016/0890-5401(88)90049-1</a>.
  ieee: H. Edelsbrunner and F. Preparata, “Minimum polygonal separation,” <i>Information
    and Computation</i>, vol. 77, no. 3. Elsevier, pp. 218–232, 1988.
  ista: Edelsbrunner H, Preparata F. 1988. Minimum polygonal separation. Information
    and Computation. 77(3), 218–232.
  mla: Edelsbrunner, Herbert, and Franco Preparata. “Minimum Polygonal Separation.”
    <i>Information and Computation</i>, vol. 77, no. 3, Elsevier, 1988, pp. 218–32,
    doi:<a href="https://doi.org/10.1016/0890-5401(88)90049-1">10.1016/0890-5401(88)90049-1</a>.
  short: H. Edelsbrunner, F. Preparata, Information and Computation 77 (1988) 218–232.
date_created: 2018-12-11T12:06:53Z
date_published: 1988-06-01T00:00:00Z
date_updated: 2022-02-08T10:36:30Z
day: '01'
doi: 10.1016/0890-5401(88)90049-1
extern: '1'
intvolume: '        77'
issue: '3'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://www.sciencedirect.com/science/article/pii/0890540188900491?via%3Dihub
month: '06'
oa: 1
oa_version: None
page: 218 - 232
publication: Information and Computation
publication_identifier:
  eissn:
  - 0890-5401
publication_status: published
publisher: Elsevier
publist_id: '2029'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Minimum polygonal separation
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 77
year: '1988'
...
---
_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. <i>Heredity</i>. 1987;59(3):457-466. doi:<a href="https://doi.org/10.1038/hdy.1987.156">10.1038/hdy.1987.156</a>
  apa: Hewitt, G., Nichols, R., &#38; Barton, N. H. (1987). Homogamy in a hybrid zone
    in the alpine grasshopper Podisma pedestris. <i>Heredity</i>. Nature Publishing
    Group. <a href="https://doi.org/10.1038/hdy.1987.156">https://doi.org/10.1038/hdy.1987.156</a>
  chicago: Hewitt, Godfrey, R. Nichols, and Nicholas H Barton. “Homogamy in a Hybrid
    Zone in the Alpine Grasshopper Podisma Pedestris.” <i>Heredity</i>. Nature Publishing
    Group, 1987. <a href="https://doi.org/10.1038/hdy.1987.156">https://doi.org/10.1038/hdy.1987.156</a>.
  ieee: G. Hewitt, R. Nichols, and N. H. Barton, “Homogamy in a hybrid zone in the
    alpine grasshopper Podisma pedestris,” <i>Heredity</i>, 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.” <i>Heredity</i>, vol. 59, no. 3, Nature Publishing Group,
    1987, pp. 457–66, doi:<a href="https://doi.org/10.1038/hdy.1987.156">10.1038/hdy.1987.156</a>.
  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: '4319'
abstract:
- lang: eng
  text: The grasshopper Podisma pedestris contains two chromosomal races, which differ
    by a Robertsonian fusion between the sex chromosome and an autosome, and which
    meet in a narrow hybrid zone in the Alpes Maritimes. DNA content variation across
    this hybrid zone was investigated by optical densitometry of Feulgen stained spermatids.
    Spermatids from males with the unfused sex chromosome stain more strongly than
    those from males with the fused chromosome. The difference between the karyotypes
    is greater in the centre of the hybrid zone, suggesting that it is not a pleiotropic
    effect of the fusion itself, but is due instead to differences at closely linked
    loci.
acknowledgement: "s We would like to thank Manse East for technical assistance and
  M. et Mme Aviotti for their hospitality in France. We are grateful to Dr Michael
  Rennet, Dr Donald Fox, Professor Hubert Rees, and an anonymous referee for their
  helpful comments on earlier manuscripts. This work was supported by an S.E.R.C.
  grant to G.M.H., and by an S.E.R.C. postdoctoral fellowship to N.H.B. MW. worked
  at UEA under an Outside Studies Program.\r\n"
article_processing_charge: No
article_type: original
author:
- first_name: Michael
  full_name: Westerman, Michael
  last_name: Westerman
- 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: Westerman M, Barton NH, Hewitt G. Differences in DNA content between two chromosomal
    races of the grasshopper Podisma pedestris. <i>Heredity</i>. 1987;58:221-228.
    doi:<a href="https://doi.org/10.1038/hdy.1987.36">10.1038/hdy.1987.36</a>
  apa: Westerman, M., Barton, N. H., &#38; Hewitt, G. (1987). Differences in DNA content
    between two chromosomal races of the grasshopper Podisma pedestris. <i>Heredity</i>.
    Nature Publishing Group. <a href="https://doi.org/10.1038/hdy.1987.36">https://doi.org/10.1038/hdy.1987.36</a>
  chicago: Westerman, Michael, Nicholas H Barton, and Godfrey Hewitt. “Differences
    in DNA Content between Two Chromosomal Races of the Grasshopper Podisma Pedestris.”
    <i>Heredity</i>. Nature Publishing Group, 1987. <a href="https://doi.org/10.1038/hdy.1987.36">https://doi.org/10.1038/hdy.1987.36</a>.
  ieee: M. Westerman, N. H. Barton, and G. Hewitt, “Differences in DNA content between
    two chromosomal races of the grasshopper Podisma pedestris,” <i>Heredity</i>,
    vol. 58. Nature Publishing Group, pp. 221–228, 1987.
  ista: Westerman M, Barton NH, Hewitt G. 1987. Differences in DNA content between
    two chromosomal races of the grasshopper Podisma pedestris. Heredity. 58, 221–228.
  mla: Westerman, Michael, et al. “Differences in DNA Content between Two Chromosomal
    Races of the Grasshopper Podisma Pedestris.” <i>Heredity</i>, vol. 58, Nature
    Publishing Group, 1987, pp. 221–28, doi:<a href="https://doi.org/10.1038/hdy.1987.36">10.1038/hdy.1987.36</a>.
  short: M. Westerman, N.H. Barton, G. Hewitt, Heredity 58 (1987) 221–228.
date_created: 2018-12-11T12:08:14Z
date_published: 1987-01-01T00:00:00Z
date_updated: 2022-02-03T10:48:40Z
day: '01'
doi: 10.1038/hdy.1987.36
extern: '1'
intvolume: '        58'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://www.nature.com/articles/hdy198736
month: '01'
oa: 1
oa_version: Published Version
page: 221 - 228
publication: Heredity
publication_identifier:
  eissn:
  - 1365-2540
  issn:
  - 0018-067X
publication_status: published
publisher: Nature Publishing Group
publist_id: '1733'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Differences in DNA content between two chromosomal races of the grasshopper
  Podisma pedestris
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 58
year: '1987'
...
---
_id: '3663'
abstract:
- lang: eng
  text: The conditional average frequency of rare alleles has been shown in simulations
    to provide a simple and robust estimator of the number of individuals exchanged
    between local populations in an island model (Nm). This statistic is defined as
    the average frequency of an allele in those samples in which the allele is present.
    Here, we show that the conditional average frequency can be calculated from the
    distribution of allele frequencies. It is a measure of the spread of this distribution,
    and so is analogous to the standardised variance, FST. Analytic predictions for
    the island model of migration agree well with the corresponding simulation results.
    These predictions are based on the assumption that the rare alleles found in samples
    have reached a &quot;quasi-equilibrium&quot; distribution. As well as relating
    the conditional average frequency to the underlying allele frequency distribution,
    our results provide a more accurate method of estimating Nm from the conditional
    average frequency of private alleles in samples of different sizes.
acknowledgement: This research has been supported in part by grants from the Royal
  Society of London, S.E.R.C., and the National Science Foundation. We thank J. Felsenstein
  for helpful discussions of this problem.
article_processing_charge: No
article_type: original
author:
- first_name: Nicholas H
  full_name: Barton, Nicholas H
  id: 4880FE40-F248-11E8-B48F-1D18A9856A87
  last_name: Barton
  orcid: 0000-0002-8548-5240
- first_name: Montgomery
  full_name: Slatkin, Montgomery
  last_name: Slatkin
citation:
  ama: Barton NH, Slatkin M. A quasi-equilibrium theory of the distribution of rare
    alleles in a subdivided population. <i>Heredity</i>. 1986;56(3):409-416. doi:<a
    href="https://doi.org/10.1038/hdy.1986.63">10.1038/hdy.1986.63</a>
  apa: Barton, N. H., &#38; Slatkin, M. (1986). A quasi-equilibrium theory of the
    distribution of rare alleles in a subdivided population. <i>Heredity</i>. Nature
    Publishing Group. <a href="https://doi.org/10.1038/hdy.1986.63">https://doi.org/10.1038/hdy.1986.63</a>
  chicago: Barton, Nicholas H, and Montgomery Slatkin. “A Quasi-Equilibrium Theory
    of the Distribution of Rare Alleles in a Subdivided Population.” <i>Heredity</i>.
    Nature Publishing Group, 1986. <a href="https://doi.org/10.1038/hdy.1986.63">https://doi.org/10.1038/hdy.1986.63</a>.
  ieee: N. H. Barton and M. Slatkin, “A quasi-equilibrium theory of the distribution
    of rare alleles in a subdivided population,” <i>Heredity</i>, vol. 56, no. 3.
    Nature Publishing Group, pp. 409–416, 1986.
  ista: Barton NH, Slatkin M. 1986. A quasi-equilibrium theory of the distribution
    of rare alleles in a subdivided population. Heredity. 56(3), 409–416.
  mla: Barton, Nicholas H., and Montgomery Slatkin. “A Quasi-Equilibrium Theory of
    the Distribution of Rare Alleles in a Subdivided Population.” <i>Heredity</i>,
    vol. 56, no. 3, Nature Publishing Group, 1986, pp. 409–16, doi:<a href="https://doi.org/10.1038/hdy.1986.63">10.1038/hdy.1986.63</a>.
  short: N.H. Barton, M. Slatkin, Heredity 56 (1986) 409–416.
date_created: 2018-12-11T12:04:30Z
date_published: 1986-06-01T00:00:00Z
date_updated: 2022-02-01T15:04:01Z
day: '01'
doi: 10.1038/hdy.1986.63
extern: '1'
external_id:
  pmid:
  - '3733460 '
intvolume: '        56'
issue: '3'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://www.nature.com/articles/hdy198663
month: '06'
oa: 1
oa_version: None
page: 409 - 416
pmid: 1
publication: Heredity
publication_identifier:
  eissn:
  - 1365-2540
  issn:
  - 0018-067X
publication_status: published
publisher: Nature Publishing Group
publist_id: '2720'
quality_controlled: '1'
scopus_import: '1'
status: public
title: A quasi-equilibrium theory of the distribution of rare alleles in a subdivided
  population
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 56
year: '1986'
...
---
_id: '3664'
abstract:
- lang: eng
  text: Suppose that selection acts at one or more loci to maintain genetic differences
    between hybridising populations. Then, the flow of alleles at a neutral marker
    locus which is linked to these selected loci will be impeded. We define and calculate
    measures of the barrier to gene flow between two distinct demes, and across a
    continuous habitat. In both cases, we find that in order for gene flow to be significantly
    reduced over much of the genome, hybrids must be substantially less fit, and the
    number of genes involved in building the barrier must be so large that the majority
    of other genes become closely linked to some locus which is under selection. This
    conclusion is not greatly affected by the pattern of epistasis, or the position
    of the marker locus along the chromosome.
article_processing_charge: No
article_type: original
author:
- first_name: Nicholas H
  full_name: Barton, Nicholas H
  id: 4880FE40-F248-11E8-B48F-1D18A9856A87
  last_name: Barton
  orcid: 0000-0002-8548-5240
- first_name: Bengt
  full_name: Bengtsson, Bengt
  last_name: Bengtsson
citation:
  ama: Barton NH, Bengtsson B. The barrier to genetic exchange between hybridising
    populations. <i>Heredity</i>. 1986;57:357-376.
  apa: Barton, N. H., &#38; Bengtsson, B. (1986). The barrier to genetic exchange
    between hybridising populations. <i>Heredity</i>. Nature Publishing Group.
  chicago: Barton, Nicholas H, and Bengt Bengtsson. “The Barrier to Genetic Exchange
    between Hybridising Populations.” <i>Heredity</i>. Nature Publishing Group, 1986.
  ieee: N. H. Barton and B. Bengtsson, “The barrier to genetic exchange between hybridising
    populations,” <i>Heredity</i>, vol. 57. Nature Publishing Group, pp. 357–376,
    1986.
  ista: Barton NH, Bengtsson B. 1986. The barrier to genetic exchange between hybridising
    populations. Heredity. 57, 357–376.
  mla: Barton, Nicholas H., and Bengt Bengtsson. “The Barrier to Genetic Exchange
    between Hybridising Populations.” <i>Heredity</i>, vol. 57, Nature Publishing
    Group, 1986, pp. 357–76.
  short: N.H. Barton, B. Bengtsson, Heredity 57 (1986) 357–376.
date_created: 2018-12-11T12:04:30Z
date_published: 1986-01-01T00:00:00Z
date_updated: 2022-02-01T14:49:02Z
day: '01'
extern: '1'
intvolume: '        57'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://www.nature.com/articles/hdy1986135
month: '01'
oa: 1
oa_version: Published Version
page: 357 - 376
publication: Heredity
publication_identifier:
  eissn:
  - 1365-2540
  issn:
  - 0018-067X
publication_status: published
publisher: Nature Publishing Group
publist_id: '2719'
quality_controlled: '1'
scopus_import: '1'
status: public
title: The barrier to genetic exchange between hybridising populations
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 57
year: '1986'
...
---
_id: '3665'
abstract:
- lang: eng
  text: The rate of gene flow across a hybrid zone may be reduced by the presence
    of a physical barrier, by a reduction of population density caused by reduced
    fitness of hybrids (the “hybrid sink” effect), and by linkage. If the reduction
    in hybrid fitness is not extreme, the strength of the barrier to gene flow caused
    by these effects is. Here, w is the width of the cline; ρ* is the carrying capacity;
    W̄* is the mean fitness of the population, excluding effects of density; R is
    the strength of density-dependent regulation; and r̄ is the harmonic mean recombination
    rate between the locus whose flow is being calculated, and loci under selection.
    +, 0 denote populations outside the hybrid zone, and at its centre, respectively.
    This relation is illustrated using data from hybrid ones in Bombina and Podisma,
    and its implications for interpretation of data from nature are discussed.
acknowledgement: I would like to thank Shahin Rouhani and Richard Nichols for their
  helpful comments on the manuscript, and the latter for providing the data used in
  fig. 3. This work was supported by a grant from the Science and Engineering Research
  Council (GR/C/91529).
article_processing_charge: No
article_type: original
author:
- first_name: Nicholas H
  full_name: Barton, Nicholas H
  id: 4880FE40-F248-11E8-B48F-1D18A9856A87
  last_name: Barton
  orcid: 0000-0002-8548-5240
citation:
  ama: Barton NH. The effects of linkage and density-dependent regulation on gene
    flow. <i>Heredity</i>. 1986;57:415-426.
  apa: Barton, N. H. (1986). The effects of linkage and density-dependent regulation
    on gene flow. <i>Heredity</i>. Nature Publishing Group.
  chicago: Barton, Nicholas H. “The Effects of Linkage and Density-Dependent Regulation
    on Gene Flow.” <i>Heredity</i>. Nature Publishing Group, 1986.
  ieee: N. H. Barton, “The effects of linkage and density-dependent regulation on
    gene flow,” <i>Heredity</i>, vol. 57. Nature Publishing Group, pp. 415–426, 1986.
  ista: Barton NH. 1986. The effects of linkage and density-dependent regulation on
    gene flow. Heredity. 57, 415–426.
  mla: Barton, Nicholas H. “The Effects of Linkage and Density-Dependent Regulation
    on Gene Flow.” <i>Heredity</i>, vol. 57, Nature Publishing Group, 1986, pp. 415–26.
  short: N.H. Barton, Heredity 57 (1986) 415–426.
date_created: 2018-12-11T12:04:30Z
date_published: 1986-01-01T00:00:00Z
date_updated: 2022-02-01T14:31:29Z
day: '01'
extern: '1'
intvolume: '        57'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://www.nature.com/articles/hdy1986142
month: '01'
oa: 1
oa_version: Published Version
page: 415 - 426
publication: Heredity
publication_identifier:
  eissn:
  - 1365-2540
  issn:
  - 0018-067X
publication_status: published
publisher: Nature Publishing Group
publist_id: '2718'
quality_controlled: '1'
scopus_import: '1'
status: public
title: The effects of linkage and density-dependent regulation on gene flow
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 57
year: '1986'
...
---
_id: '4098'
abstract:
- lang: eng
  text: To points p and q of a finite set S in d-dimensional Euclidean space Ed are
    extreme if {p, q} = S ∩ h, for some open halfspace h. Let e2(d)(n) be the maximum
    number of extreme pairs realized by any n points in Ed. We give geometric proofs
    of , if n⩾4, and e2(3)(n) = 3n−6, if n⩾6. These results settle the question since
    all other cases are trivial.
article_processing_charge: No
article_type: original
author:
- first_name: Herbert
  full_name: Edelsbrunner, Herbert
  id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
  last_name: Edelsbrunner
  orcid: 0000-0002-9823-6833
- first_name: Gerd
  full_name: Stöckl, Gerd
  last_name: Stöckl
citation:
  ama: Edelsbrunner H, Stöckl G. The number of extreme pairs of finite point-sets
    in Euclidean spaces. <i>Journal of Combinatorial Theory Series A</i>. 1986;43(2):344-349.
    doi:<a href="https://doi.org/10.1016/0097-3165(86)90075-0">10.1016/0097-3165(86)90075-0</a>
  apa: Edelsbrunner, H., &#38; Stöckl, G. (1986). The number of extreme pairs of finite
    point-sets in Euclidean spaces. <i>Journal of Combinatorial Theory Series A</i>.
    Elsevier. <a href="https://doi.org/10.1016/0097-3165(86)90075-0">https://doi.org/10.1016/0097-3165(86)90075-0</a>
  chicago: Edelsbrunner, Herbert, and Gerd Stöckl. “The Number of Extreme Pairs of
    Finite Point-Sets in Euclidean Spaces.” <i>Journal of Combinatorial Theory Series
    A</i>. Elsevier, 1986. <a href="https://doi.org/10.1016/0097-3165(86)90075-0">https://doi.org/10.1016/0097-3165(86)90075-0</a>.
  ieee: H. Edelsbrunner and G. Stöckl, “The number of extreme pairs of finite point-sets
    in Euclidean spaces,” <i>Journal of Combinatorial Theory Series A</i>, vol. 43,
    no. 2. Elsevier, pp. 344–349, 1986.
  ista: Edelsbrunner H, Stöckl G. 1986. The number of extreme pairs of finite point-sets
    in Euclidean spaces. Journal of Combinatorial Theory Series A. 43(2), 344–349.
  mla: Edelsbrunner, Herbert, and Gerd Stöckl. “The Number of Extreme Pairs of Finite
    Point-Sets in Euclidean Spaces.” <i>Journal of Combinatorial Theory Series A</i>,
    vol. 43, no. 2, Elsevier, 1986, pp. 344–49, doi:<a href="https://doi.org/10.1016/0097-3165(86)90075-0">10.1016/0097-3165(86)90075-0</a>.
  short: H. Edelsbrunner, G. Stöckl, Journal of Combinatorial Theory Series A 43 (1986)
    344–349.
date_created: 2018-12-11T12:06:56Z
date_published: 1986-11-01T00:00:00Z
date_updated: 2022-02-01T14:02:41Z
day: '01'
doi: 10.1016/0097-3165(86)90075-0
extern: '1'
intvolume: '        43'
issue: '2'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://www.sciencedirect.com/science/article/pii/0097316586900750?via%3Dihub
month: '11'
oa: 1
oa_version: None
page: 344 - 349
publication: Journal of Combinatorial Theory Series A
publication_identifier:
  eissn:
  - 1096-0899
  issn:
  - 0097-3165
publication_status: published
publisher: Elsevier
publist_id: '2020'
quality_controlled: '1'
scopus_import: '1'
status: public
title: The number of extreme pairs of finite point-sets in Euclidean spaces
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 43
year: '1986'
...
---
_id: '4103'
abstract:
- lang: eng
  text: Let A be an arrangement of n lines in the plane. Suppose F1,…, Fk are faces
    in the dissection induced by A and that Fi is a t(Fi)-gon. We give asymptotic
    bounds on the maximal sum ∑i=1kt(Fi) which can be realized by k different faces
    in an arrangement of n lines. The results improve known bounds for k of higher
    order than n(1/2).
acknowledgement: The second author thanks Gan Gusfield for useful discussion.
article_processing_charge: No
author:
- first_name: Herbert
  full_name: Edelsbrunner, Herbert
  id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
  last_name: Edelsbrunner
  orcid: 0000-0002-9823-6833
- first_name: Emo
  full_name: Welzl, Emo
  last_name: Welzl
citation:
  ama: Edelsbrunner H, Welzl E. On the maximal number of edges of many faces in an
    arrangement. <i>Journal of Combinatorial Theory Series A</i>. 1986;41(2):159-166.
    doi:<a href="https://doi.org/10.1016/0097-3165(86)90078-6">10.1016/0097-3165(86)90078-6</a>
  apa: Edelsbrunner, H., &#38; Welzl, E. (1986). On the maximal number of edges of
    many faces in an arrangement. <i>Journal of Combinatorial Theory Series A</i>.
    Elsevier. <a href="https://doi.org/10.1016/0097-3165(86)90078-6">https://doi.org/10.1016/0097-3165(86)90078-6</a>
  chicago: Edelsbrunner, Herbert, and Emo Welzl. “On the Maximal Number of Edges of
    Many Faces in an Arrangement.” <i>Journal of Combinatorial Theory Series A</i>.
    Elsevier, 1986. <a href="https://doi.org/10.1016/0097-3165(86)90078-6">https://doi.org/10.1016/0097-3165(86)90078-6</a>.
  ieee: H. Edelsbrunner and E. Welzl, “On the maximal number of edges of many faces
    in an arrangement,” <i>Journal of Combinatorial Theory Series A</i>, vol. 41,
    no. 2. Elsevier, pp. 159–166, 1986.
  ista: Edelsbrunner H, Welzl E. 1986. On the maximal number of edges of many faces
    in an arrangement. Journal of Combinatorial Theory Series A. 41(2), 159–166.
  mla: Edelsbrunner, Herbert, and Emo Welzl. “On the Maximal Number of Edges of Many
    Faces in an Arrangement.” <i>Journal of Combinatorial Theory Series A</i>, vol.
    41, no. 2, Elsevier, 1986, pp. 159–66, doi:<a href="https://doi.org/10.1016/0097-3165(86)90078-6">10.1016/0097-3165(86)90078-6</a>.
  short: H. Edelsbrunner, E. Welzl, Journal of Combinatorial Theory Series A 41 (1986)
    159–166.
date_created: 2018-12-11T12:06:57Z
date_published: 1986-11-01T00:00:00Z
date_updated: 2022-02-01T09:46:55Z
day: '01'
doi: 10.1016/0097-3165(86)90078-6
extern: '1'
intvolume: '        41'
issue: '2'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://www.sciencedirect.com/science/article/pii/0097316586900786?via%3Dihub
month: '11'
oa: 1
oa_version: Published Version
page: 159 - 166
publication: Journal of Combinatorial Theory Series A
publication_identifier:
  eissn:
  - 1096-0899
  issn:
  - 0097-3165
publication_status: published
publisher: Elsevier
publist_id: '2015'
quality_controlled: '1'
scopus_import: '1'
status: public
title: On the maximal number of edges of many faces in an arrangement
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 41
year: '1986'
...
---
_id: '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.
    <i>Theoretical Computer Science</i>. 1985;35(1):55-69. doi:<a href="https://doi.org/10.1016/0304-3975(85)90005-2">10.1016/0304-3975(85)90005-2</a>
  apa: Edelsbrunner, H. (1985). Finding Transversals for Sets of Simple Geometric-Figures.
    <i>Theoretical Computer Science</i>. Elsevier. <a href="https://doi.org/10.1016/0304-3975(85)90005-2">https://doi.org/10.1016/0304-3975(85)90005-2</a>
  chicago: Edelsbrunner, Herbert. “Finding Transversals for Sets of Simple Geometric-Figures.”
    <i>Theoretical Computer Science</i>. Elsevier, 1985. <a href="https://doi.org/10.1016/0304-3975(85)90005-2">https://doi.org/10.1016/0304-3975(85)90005-2</a>.
  ieee: H. Edelsbrunner, “Finding Transversals for Sets of Simple Geometric-Figures,”
    <i>Theoretical Computer Science</i>, 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.”
    <i>Theoretical Computer Science</i>, vol. 35, no. 1, Elsevier, 1985, pp. 55–69,
    doi:<a href="https://doi.org/10.1016/0304-3975(85)90005-2">10.1016/0304-3975(85)90005-2</a>.
  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. <i>Journal of Symbolic Computation</i>. 1985;1(1):47-56. doi:<a href="https://doi.org/10.1016/S0747-7171(85)80028-6">10.1016/S0747-7171(85)80028-6</a>
  apa: Chazelle, B., &#38; Edelsbrunner, H. (1985). Optimal solutions for a class
    of point retrieval problems. <i>Journal of Symbolic Computation</i>. Elsevier.
    <a href="https://doi.org/10.1016/S0747-7171(85)80028-6">https://doi.org/10.1016/S0747-7171(85)80028-6</a>
  chicago: Chazelle, Bernard, and Herbert Edelsbrunner. “Optimal Solutions for a Class
    of Point Retrieval Problems.” <i>Journal of Symbolic Computation</i>. Elsevier,
    1985. <a href="https://doi.org/10.1016/S0747-7171(85)80028-6">https://doi.org/10.1016/S0747-7171(85)80028-6</a>.
  ieee: B. Chazelle and H. Edelsbrunner, “Optimal solutions for a class of point retrieval
    problems,” <i>Journal of Symbolic Computation</i>, 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.” <i>Journal of Symbolic Computation</i>, vol. 1,
    no. 1, Elsevier, 1985, pp. 47–56, doi:<a href="https://doi.org/10.1016/S0747-7171(85)80028-6">10.1016/S0747-7171(85)80028-6</a>.
  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: '3667'
abstract:
- lang: eng
  text: Populations of the grasshopper Podisma pedestris were collected from two ends
    of a zone of hybridization between two chromosome races, at Seyne and Tende in
    southern France. 21 enzyme and protein loci were detected by gel electrophoresis.
    Six of these loci showed widespread polymorphism, and a further eleven had very
    little or no variation. Two loci (Idh, 6Pgd) had rare alleles in different frequencies
    in the two areas surveyed. The remaining two loci (Mdh-1, Mdh-2) showed a marked
    increase in the frequency of rare variants, from 1 per cent outside the hybrid
    zone, up to 5 per cent at its centre. This region of increased electrophoretic
    variation coincided with the chromosomal cline between the two races, and with
    a region of decreased viability. It was spread over about the same width as the
    chromosomal cline. Possible explanations for this extra variation include intragenic
    recombination and elevated mutation rates.
acknowledgement: We would like to thank Manse East, Lynda Flegg, and Sim Webb for
  their excellent technical assistance, and Prof. J. M. Thoday for helpful comments.
  Financial support was provided by a NERC Studentship to NHB, and a SRC grant to
  GMH.
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: Bruce
  full_name: Halliday, Bruce
  last_name: Halliday
- first_name: Godfrey
  full_name: Hewitt, Godfrey
  last_name: Hewitt
citation:
  ama: Barton NH, Halliday B, Hewitt G. Rare electrophoretic variants in a hybrid
    zone. <i>Heredity</i>. 1983;50(2):139-146. doi:<a href="https://doi.org/10.1038/hdy.1983.15">10.1038/hdy.1983.15</a>
  apa: Barton, N. H., Halliday, B., &#38; Hewitt, G. (1983). Rare electrophoretic
    variants in a hybrid zone. <i>Heredity</i>. Nature Publishing Group. <a href="https://doi.org/10.1038/hdy.1983.15">https://doi.org/10.1038/hdy.1983.15</a>
  chicago: Barton, Nicholas H, Bruce Halliday, and Godfrey Hewitt. “Rare Electrophoretic
    Variants in a Hybrid Zone.” <i>Heredity</i>. Nature Publishing Group, 1983. <a
    href="https://doi.org/10.1038/hdy.1983.15">https://doi.org/10.1038/hdy.1983.15</a>.
  ieee: N. H. Barton, B. Halliday, and G. Hewitt, “Rare electrophoretic variants in
    a hybrid zone,” <i>Heredity</i>, vol. 50, no. 2. Nature Publishing Group, pp.
    139–146, 1983.
  ista: Barton NH, Halliday B, Hewitt G. 1983. Rare electrophoretic variants in a
    hybrid zone. Heredity. 50(2), 139–146.
  mla: Barton, Nicholas H., et al. “Rare Electrophoretic Variants in a Hybrid Zone.”
    <i>Heredity</i>, vol. 50, no. 2, Nature Publishing Group, 1983, pp. 139–46, doi:<a
    href="https://doi.org/10.1038/hdy.1983.15">10.1038/hdy.1983.15</a>.
  short: N.H. Barton, B. Halliday, G. Hewitt, Heredity 50 (1983) 139–146.
date_created: 2018-12-11T12:04:31Z
date_published: 1983-04-01T00:00:00Z
date_updated: 2022-01-25T14:07:12Z
day: '01'
doi: 10.1038/hdy.1983.15
extern: '1'
intvolume: '        50'
issue: '2'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://www.nature.com/articles/hdy198315
month: '04'
oa: 1
oa_version: Published Version
page: 139 - 146
publication: Heredity
publication_identifier:
  eissn:
  - 1365-2540
  issn:
  - 0018-067X
publication_status: published
publisher: Nature Publishing Group
publist_id: '2716'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Rare electrophoretic variants in a hybrid zone
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 50
year: '1983'
...
---
_id: '4330'
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. Gene flow and speciation (abstract). <i>Heredity</i>. 1983;50:213-213.
    doi:<a href="https://doi.org/10.1038/hdy.1983.24">10.1038/hdy.1983.24</a>
  apa: 'Barton, N. H. (1983). Gene flow and speciation (abstract). <i>Heredity</i>.
    University College of London: Springer Nature. <a href="https://doi.org/10.1038/hdy.1983.24">https://doi.org/10.1038/hdy.1983.24</a>'
  chicago: 'Barton, Nicholas H. “Gene Flow and Speciation (Abstract).” <i>Heredity</i>.
    University College of London: Springer Nature, 1983. <a href="https://doi.org/10.1038/hdy.1983.24">https://doi.org/10.1038/hdy.1983.24</a>.'
  ieee: N. H. Barton, “Gene flow and speciation (abstract),” <i>Heredity</i>, vol.
    50. Springer Nature, University College of London, pp. 213–213, 1983.
  ista: Barton NH. 1983. Gene flow and speciation (abstract). Heredity. 50, 213–213.
  mla: Barton, Nicholas H. “Gene Flow and Speciation (Abstract).” <i>Heredity</i>,
    vol. 50, Springer Nature, 1983, pp. 213–213, doi:<a href="https://doi.org/10.1038/hdy.1983.24">10.1038/hdy.1983.24</a>.
  short: N.H. Barton, Heredity 50 (1983) 213–213.
date_created: 2018-12-11T12:08:17Z
date_published: 1983-04-01T00:00:00Z
date_updated: 2022-01-21T12:38:10Z
day: '01'
doi: 10.1038/hdy.1983.24
extern: '1'
intvolume: '        50'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://www.nature.com/articles/hdy198324
month: '04'
oa: 1
oa_version: Published Version
page: 213 - 213
place: University College of London
publication: Heredity
publication_identifier:
  eissn:
  - 1365-2540
  issn:
  - 0018-067X
publication_status: published
publisher: Springer Nature
publist_id: '1704'
quality_controlled: '1'
status: public
title: Gene flow and speciation (abstract)
type: review
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 50
year: '1983'
...
---
_id: '3669'
abstract:
- lang: eng
  text: The dispersal rate of the grasshopper Podisma pedestris has been measured,
    with the aim of interpreting the width of a chromosomal cline. 171 adults were
    marked individually, and released within the cline. 169 movements were seen over
    three subsequent scorings; the distribution of distances, after correction for
    the loss of long distance dispersants, was close to a normal curve, but there
    was an initial shift of ten metres, perhaps towards a better habitat. The linear
    variance increased at about 214 m2 day- 1, which corresponds to a standard deviation
    of 207 m gen- 1/2 over a 20 day life span. Statistical uncertainty in this estimate
    can be expressed using a distribution-free maximum likelihood method, which gives
    support limits of 186- 270 m gen- 1/2. However, the main errors come from extrapolating
    from this experiment to the cline as a whole.
acknowledgement: "We are grateful for the help in the field of Bruce and Helen Halliday,
  James, Matthew, Daniel and Elizabeth Hewitt, and for the hospitality of M et Mme
  Aviotti. This work was supported by an N.E.R.C. Studentship to the first author,
  and an S.R.C. research grant to the second.\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: Godfrey
  full_name: Hewitt, Godfrey
  last_name: Hewitt
citation:
  ama: 'Barton NH, Hewitt G. A measurement of dispersal in the grasshopper Podisma
    pedestris (Orthoptera: Acrididae). <i>Heredity</i>. 1982;48(2):237-249. doi:<a
    href="https://doi.org/10.1038/hdy.1982.29">10.1038/hdy.1982.29</a>'
  apa: 'Barton, N. H., &#38; Hewitt, G. (1982). A measurement of dispersal in the
    grasshopper Podisma pedestris (Orthoptera: Acrididae). <i>Heredity</i>. Springer
    Nature. <a href="https://doi.org/10.1038/hdy.1982.29">https://doi.org/10.1038/hdy.1982.29</a>'
  chicago: 'Barton, Nicholas H, and Godfrey Hewitt. “A Measurement of Dispersal in
    the Grasshopper Podisma Pedestris (Orthoptera: Acrididae).” <i>Heredity</i>. Springer
    Nature, 1982. <a href="https://doi.org/10.1038/hdy.1982.29">https://doi.org/10.1038/hdy.1982.29</a>.'
  ieee: 'N. H. Barton and G. Hewitt, “A measurement of dispersal in the grasshopper
    Podisma pedestris (Orthoptera: Acrididae),” <i>Heredity</i>, vol. 48, no. 2. Springer
    Nature, pp. 237–249, 1982.'
  ista: 'Barton NH, Hewitt G. 1982. A measurement of dispersal in the grasshopper
    Podisma pedestris (Orthoptera: Acrididae). Heredity. 48(2), 237–249.'
  mla: 'Barton, Nicholas H., and Godfrey Hewitt. “A Measurement of Dispersal in the
    Grasshopper Podisma Pedestris (Orthoptera: Acrididae).” <i>Heredity</i>, vol.
    48, no. 2, Springer Nature, 1982, pp. 237–49, doi:<a href="https://doi.org/10.1038/hdy.1982.29">10.1038/hdy.1982.29</a>.'
  short: N.H. Barton, G. Hewitt, Heredity 48 (1982) 237–249.
date_created: 2018-12-11T12:04:32Z
date_published: 1982-04-01T00:00:00Z
date_updated: 2022-01-21T12:31:06Z
day: '01'
doi: 10.1038/hdy.1982.29
extern: '1'
intvolume: '        48'
issue: '2'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://www.nature.com/articles/hdy198229
month: '04'
oa: 1
oa_version: Published Version
page: 237 - 249
publication: Heredity
publication_identifier:
  eissn:
  - 1365-2540
  issn:
  - 0018-067X
publication_status: published
publisher: Springer Nature
publist_id: '2714'
quality_controlled: '1'
status: public
title: 'A measurement of dispersal in the grasshopper Podisma pedestris (Orthoptera:
  Acrididae)'
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 48
year: '1982'
...
---
OA_place: publisher
OA_type: hybrid
_id: '3671'
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 width of the hybrid zone in Caledia captiva. <i>Heredity</i>.
    1981;47:279-282. doi:<a href="https://doi.org/10.1038/hdy.1981.86">10.1038/hdy.1981.86</a>
  apa: Barton, N. H. (1981). The width of the hybrid zone in Caledia captiva. <i>Heredity</i>.
    Nature Publishing Group. <a href="https://doi.org/10.1038/hdy.1981.86">https://doi.org/10.1038/hdy.1981.86</a>
  chicago: Barton, Nicholas H. “The Width of the Hybrid Zone in Caledia Captiva.”
    <i>Heredity</i>. Nature Publishing Group, 1981. <a href="https://doi.org/10.1038/hdy.1981.86">https://doi.org/10.1038/hdy.1981.86</a>.
  ieee: N. H. Barton, “The width of the hybrid zone in Caledia captiva,” <i>Heredity</i>,
    vol. 47. Nature Publishing Group, pp. 279–282, 1981.
  ista: Barton NH. 1981. The width of the hybrid zone in Caledia captiva. Heredity.
    47, 279–282.
  mla: Barton, Nicholas H. “The Width of the Hybrid Zone in Caledia Captiva.” <i>Heredity</i>,
    vol. 47, Nature Publishing Group, 1981, pp. 279–82, doi:<a href="https://doi.org/10.1038/hdy.1981.86">10.1038/hdy.1981.86</a>.
  short: N.H. Barton, Heredity 47 (1981) 279–282.
date_created: 2018-12-11T12:04:32Z
date_published: 1981-10-01T00:00:00Z
date_updated: 2024-10-16T14:41:36Z
day: '01'
doi: 10.1038/hdy.1981.86
extern: '1'
intvolume: '        47'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://www.nature.com/articles/hdy198186
month: '10'
oa: 1
oa_version: Published Version
page: 279 - 282
publication: Heredity
publication_identifier:
  eissn:
  - 1365-2540
  issn:
  - 0018-067X
publication_status: published
publisher: Nature Publishing Group
publist_id: '2712'
quality_controlled: '1'
scopus_import: '1'
status: public
title: The width of the hybrid zone in Caledia captiva
type: journal_article
user_id: 0043cee0-e5fc-11ee-9736-f83bc23afbf0
volume: 47
year: '1981'
...
---
OA_place: publisher
OA_type: hybrid
_id: '4132'
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. On the intersection of Orthogonal objects. <i>Information
    Processing Letters</i>. 1981;13(4-5):177-181. doi:<a href="https://doi.org/10.1016/0020-0190(81)90053-3">10.1016/0020-0190(81)90053-3</a>
  apa: Edelsbrunner, H., &#38; Maurer, H. (1981). On the intersection of Orthogonal
    objects. <i>Information Processing Letters</i>. Elsevier. <a href="https://doi.org/10.1016/0020-0190(81)90053-3">https://doi.org/10.1016/0020-0190(81)90053-3</a>
  chicago: Edelsbrunner, Herbert, and Hermann Maurer. “On the Intersection of Orthogonal
    Objects.” <i>Information Processing Letters</i>. Elsevier, 1981. <a href="https://doi.org/10.1016/0020-0190(81)90053-3">https://doi.org/10.1016/0020-0190(81)90053-3</a>.
  ieee: H. Edelsbrunner and H. Maurer, “On the intersection of Orthogonal objects,”
    <i>Information Processing Letters</i>, vol. 13, no. 4–5. Elsevier, pp. 177–181,
    1981.
  ista: Edelsbrunner H, Maurer H. 1981. On the intersection of Orthogonal objects.
    Information Processing Letters. 13(4–5), 177–181.
  mla: Edelsbrunner, Herbert, and Hermann Maurer. “On the Intersection of Orthogonal
    Objects.” <i>Information Processing Letters</i>, vol. 13, no. 4–5, Elsevier, 1981,
    pp. 177–81, doi:<a href="https://doi.org/10.1016/0020-0190(81)90053-3">10.1016/0020-0190(81)90053-3</a>.
  short: H. Edelsbrunner, H. Maurer, Information Processing Letters 13 (1981) 177–181.
date_created: 2018-12-11T12:07:08Z
date_published: 1981-01-01T00:00:00Z
date_updated: 2024-10-30T14:40:02Z
day: '01'
doi: 10.1016/0020-0190(81)90053-3
extern: '1'
intvolume: '        13'
issue: 4-5
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://www.sciencedirect.com/science/article/pii/0020019081900533
month: '01'
oa: 1
oa_version: Published Version
page: 177 - 181
publication: Information Processing Letters
publication_identifier:
  issn:
  - 0020-0190
publication_status: published
publisher: Elsevier
publist_id: '1988'
quality_controlled: '1'
scopus_import: '1'
status: public
title: On the intersection of Orthogonal objects
type: journal_article
user_id: 0043cee0-e5fc-11ee-9736-f83bc23afbf0
volume: 13
year: '1981'
...
---
OA_place: publisher
OA_type: hybrid
_id: '4133'
abstract:
- lang: eng
  text: In 1979 Kirpatrick obtained a practically feasible algorithm for planar regionlocation
    working in linear space and logarithmic time, provided the regions are bounded
    by straight line segments. No algorithm requiring only linear space and log-polynomial
    time was known, so far, for general planar regionlocation, i.e. for the case where
    regions are bounded by curves more complicated than straight line segments. As
    main result of this paper such an algorithm is presented.
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. A space-optimal solution of general region location.
    <i>Theoretical Computer Science</i>. 1981;16(3):329-336. doi:<a href="https://doi.org/10.1016/0304-3975(81)90103-1">10.1016/0304-3975(81)90103-1</a>
  apa: Edelsbrunner, H., &#38; Maurer, H. (1981). A space-optimal solution of general
    region location. <i>Theoretical Computer Science</i>. Elsevier. <a href="https://doi.org/10.1016/0304-3975(81)90103-1">https://doi.org/10.1016/0304-3975(81)90103-1</a>
  chicago: Edelsbrunner, Herbert, and Hermann Maurer. “A Space-Optimal Solution of
    General Region Location.” <i>Theoretical Computer Science</i>. Elsevier, 1981.
    <a href="https://doi.org/10.1016/0304-3975(81)90103-1">https://doi.org/10.1016/0304-3975(81)90103-1</a>.
  ieee: H. Edelsbrunner and H. Maurer, “A space-optimal solution of general region
    location,” <i>Theoretical Computer Science</i>, vol. 16, no. 3. Elsevier, pp.
    329–336, 1981.
  ista: Edelsbrunner H, Maurer H. 1981. A space-optimal solution of general region
    location. Theoretical Computer Science. 16(3), 329–336.
  mla: Edelsbrunner, Herbert, and Hermann Maurer. “A Space-Optimal Solution of General
    Region Location.” <i>Theoretical Computer Science</i>, vol. 16, no. 3, Elsevier,
    1981, pp. 329–36, doi:<a href="https://doi.org/10.1016/0304-3975(81)90103-1">10.1016/0304-3975(81)90103-1</a>.
  short: H. Edelsbrunner, H. Maurer, Theoretical Computer Science 16 (1981) 329–336.
date_created: 2018-12-11T12:07:08Z
date_published: 1981-01-01T00:00:00Z
date_updated: 2024-10-16T14:45:11Z
day: '01'
doi: 10.1016/0304-3975(81)90103-1
extern: '1'
intvolume: '        16'
issue: '3'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://www.sciencedirect.com/science/article/pii/0304397581901031
month: '01'
oa: 1
oa_version: Published Version
page: 329 - 336
publication: Theoretical Computer Science
publication_identifier:
  issn:
  - 0304-3975
publication_status: published
publisher: Elsevier
publist_id: '1989'
quality_controlled: '1'
scopus_import: '1'
status: public
title: A space-optimal solution of general region location
type: journal_article
user_id: 0043cee0-e5fc-11ee-9736-f83bc23afbf0
volume: 16
year: '1981'
...