[{"quality_controlled":"1","scopus_import":"1","article_processing_charge":"No","date_updated":"2022-02-23T10:41:43Z","doi":"10.1093/genetics/124.3.773 ","author":[{"full_name":"Barton, Nicholas H","id":"4880FE40-F248-11E8-B48F-1D18A9856A87","first_name":"Nicholas H","last_name":"Barton","orcid":"0000-0002-8548-5240"}],"date_published":"1990-03-01T00:00:00Z","publication_status":"published","main_file_link":[{"open_access":"1","url":"https://academic.oup.com/genetics/article/124/3/773/5999956?login=true"}],"intvolume":"       124","month":"03","language":[{"iso":"eng"}],"day":"01","pmid":1,"publist_id":"2732","date_created":"2018-12-11T12:04:26Z","oa_version":"Published Version","publisher":"Genetics Society of America","publication":"Genetics","title":"Pleiotropic models of quantitative variation","extern":"1","abstract":[{"lang":"eng","text":"It is widely held that each gene typically affects many characters, and that each character is affected by many genes. Moreover, strong stabilizing selection cannot act on an indefinitely large number of independent traits. This makes it likely that heritable variation in any one trait is maintained as a side effect of polymorphisms which have nothing to do with selection on that trait. This paper examines the idea that variation is maintained as the pleiotropic side effect of either deleterious mutation, or balancing selection. If mutation is responsible, it must produce alleles which are only mildly deleterious (s &amp; 10(-3)), but nevertheless have significant effects on the trait. Balancing selection can readily maintain high heritabilities; however, selection must be spread over many weakly selected polymorphisms if large responses to artificial selection are to be possible. In both classes of pleiotropic model, extreme phenotypes are less fit, giving the appearance of stabilizing selection on the trait. However, it is shown that this effect is weak (of the same order as the selection on each gene): the strong stabilizing selection which is often observed is likely to be caused by correlations with a limited number of directly selected traits. Possible experiments for distinguishing the alternatives are discussed."}],"year":"1990","_id":"3651","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","type":"journal_article","volume":124,"page":"773 - 782","publication_identifier":{"issn":["0016-6731"]},"citation":{"chicago":"Barton, Nicholas H. “Pleiotropic Models of Quantitative Variation.” <i>Genetics</i>. Genetics Society of America, 1990. <a href=\"https://doi.org/10.1093/genetics/124.3.773 \">https://doi.org/10.1093/genetics/124.3.773 </a>.","ieee":"N. H. Barton, “Pleiotropic models of quantitative variation,” <i>Genetics</i>, vol. 124, no. 3. Genetics Society of America, pp. 773–782, 1990.","apa":"Barton, N. H. (1990). Pleiotropic models of quantitative variation. <i>Genetics</i>. Genetics Society of America. <a href=\"https://doi.org/10.1093/genetics/124.3.773 \">https://doi.org/10.1093/genetics/124.3.773 </a>","ama":"Barton NH. Pleiotropic models of quantitative variation. <i>Genetics</i>. 1990;124(3):773-782. doi:<a href=\"https://doi.org/10.1093/genetics/124.3.773 \">10.1093/genetics/124.3.773 </a>","short":"N.H. Barton, Genetics 124 (1990) 773–782.","mla":"Barton, Nicholas H. “Pleiotropic Models of Quantitative Variation.” <i>Genetics</i>, vol. 124, no. 3, Genetics Society of America, 1990, pp. 773–82, doi:<a href=\"https://doi.org/10.1093/genetics/124.3.773 \">10.1093/genetics/124.3.773 </a>.","ista":"Barton NH. 1990. Pleiotropic models of quantitative variation. Genetics. 124(3), 773–782."},"issue":"3","article_type":"original","external_id":{"pmid":["2311921"]},"status":"public","acknowledgement":"Thanks to JERRY COYNE, BILL HILL, LINDA PARTRIDGE, MICHAEL TURELLI, and two anonymous reviewers for their critical comments. This work was supported by grants from the National Science Foundation (BSR-8866548) the Science and Engineering Research Council (GR/E/08507), and by the Institute of Theoretical Dynamics, University of California, Davis.","oa":1},{"publist_id":"2061","oa_version":"Published Version","date_created":"2018-12-11T12:06:42Z","publisher":"Elsevier","title":"Tetrahedrizing point sets in three dimensions","publication":"Journal of Symbolic Computation","extern":"1","abstract":[{"text":"This paper offers combinatorial results on extremum problems concerning the number of tetrahedra in a tetrahedrization of n points in general position in three dimensions, i.e. such that no four points are co-planar, It also presents an algorithm that in O(n log n) time constructs a tetrahedrization of a set of n points consisting of at most 3n-11 tetrahedra.","lang":"eng"}],"year":"1990","_id":"4060","type":"journal_article","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","page":"335 - 347","volume":10,"publication_identifier":{"issn":["0747-7171"],"eissn":["1095-855X"]},"citation":{"chicago":"Edelsbrunner, Herbert, Franco Preparata, and Douglas West. “Tetrahedrizing Point Sets in Three Dimensions.” <i>Journal of Symbolic Computation</i>. Elsevier, 1990. <a href=\"https://doi.org/10.1016/S0747-7171(08)80068-5\">https://doi.org/10.1016/S0747-7171(08)80068-5</a>.","ieee":"H. Edelsbrunner, F. Preparata, and D. West, “Tetrahedrizing point sets in three dimensions,” <i>Journal of Symbolic Computation</i>, vol. 10, no. 3–4. Elsevier, pp. 335–347, 1990.","apa":"Edelsbrunner, H., Preparata, F., &#38; West, D. (1990). Tetrahedrizing point sets in three dimensions. <i>Journal of Symbolic Computation</i>. Elsevier. <a href=\"https://doi.org/10.1016/S0747-7171(08)80068-5\">https://doi.org/10.1016/S0747-7171(08)80068-5</a>","ama":"Edelsbrunner H, Preparata F, West D. Tetrahedrizing point sets in three dimensions. <i>Journal of Symbolic Computation</i>. 1990;10(3-4):335-347. doi:<a href=\"https://doi.org/10.1016/S0747-7171(08)80068-5\">10.1016/S0747-7171(08)80068-5</a>","mla":"Edelsbrunner, Herbert, et al. “Tetrahedrizing Point Sets in Three Dimensions.” <i>Journal of Symbolic Computation</i>, vol. 10, no. 3–4, Elsevier, 1990, pp. 335–47, doi:<a href=\"https://doi.org/10.1016/S0747-7171(08)80068-5\">10.1016/S0747-7171(08)80068-5</a>.","short":"H. Edelsbrunner, F. Preparata, D. West, Journal of Symbolic Computation 10 (1990) 335–347.","ista":"Edelsbrunner H, Preparata F, West D. 1990. Tetrahedrizing point sets in three dimensions. Journal of Symbolic Computation. 10(3–4), 335–347."},"article_type":"original","issue":"3-4","status":"public","oa":1,"acknowledgement":"Research of the first author is supported by Amoco Fnd. Fac. Dec. Comput. Sci. 1-6-44862, the second author is supported by NSF Grant ECS 84-10902, and research of the third author is supported in part by ONR Grant N00014-85K0570 and by NSF Grant DMS 8504322.","quality_controlled":"1","scopus_import":"1","doi":"10.1016/S0747-7171(08)80068-5","date_updated":"2022-02-23T10:10:35Z","article_processing_charge":"No","author":[{"orcid":"0000-0002-9823-6833","last_name":"Edelsbrunner","first_name":"Herbert","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","full_name":"Edelsbrunner, Herbert"},{"full_name":"Preparata, Franco","last_name":"Preparata","first_name":"Franco"},{"first_name":"Douglas","last_name":"West","full_name":"West, Douglas"}],"date_published":"1990-01-01T00:00:00Z","publication_status":"published","main_file_link":[{"url":"https://www.sciencedirect.com/science/article/pii/S0747717108800685?via%3Dihub","open_access":"1"}],"intvolume":"        10","language":[{"iso":"eng"}],"month":"01","day":"01"},{"page":"17649 - 17652","volume":264,"type":"journal_article","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","_id":"2525","year":"1989","status":"public","oa":1,"acknowledgement":"This work was supported in part by research grants from the Ministry of Education, Science and Culture of Japan, the Institute of Physical and Chemical Research, and the Science and Technology Agency of Japan. The costs of publication of this article were defrayed in part by the payment of page charges. This article must therefore be hereby marked “advertisement” in accordance with 18 U.S.C. Section 1734 solely to indicate this fact. ","external_id":{"pmid":["2478537"]},"article_type":"original","issue":"30","citation":{"ama":"Yokota Y, Sasai Y, Tanaka K, et al. Molecular characterization of a functional cDNA for rat substance P receptor. <i>Journal of Biological Chemistry</i>. 1989;264(30):17649-17652. doi:<a href=\"https://doi.org/doi.org/10.1016/S0021-9258(19)84619-7\">doi.org/10.1016/S0021-9258(19)84619-7</a>","mla":"Yokota, Yoshifumi, et al. “Molecular Characterization of a Functional CDNA for Rat Substance P Receptor.” <i>Journal of Biological Chemistry</i>, vol. 264, no. 30, American Society for Biochemistry and Molecular Biology, 1989, pp. 17649–52, doi:<a href=\"https://doi.org/doi.org/10.1016/S0021-9258(19)84619-7\">doi.org/10.1016/S0021-9258(19)84619-7</a>.","ista":"Yokota Y, Sasai Y, Tanaka K, Fujiwara T, Tsuchida K, Shigemoto R, Kakizuka A, Ohkubo H, Nakanishi S. 1989. Molecular characterization of a functional cDNA for rat substance P receptor. Journal of Biological Chemistry. 264(30), 17649–17652.","short":"Y. Yokota, Y. Sasai, K. Tanaka, T. Fujiwara, K. Tsuchida, R. Shigemoto, A. Kakizuka, H. Ohkubo, S. Nakanishi, Journal of Biological Chemistry 264 (1989) 17649–17652.","ieee":"Y. Yokota <i>et al.</i>, “Molecular characterization of a functional cDNA for rat substance P receptor,” <i>Journal of Biological Chemistry</i>, vol. 264, no. 30. American Society for Biochemistry and Molecular Biology, pp. 17649–17652, 1989.","chicago":"Yokota, Yoshifumi, Yoshiki Sasai, Kohichi Tanaka, Tsutomu Fujiwara, Kunihiro Tsuchida, Ryuichi Shigemoto, Akira Kakizuka, Hiroaki Ohkubo, and Shigetada Nakanishi. “Molecular Characterization of a Functional CDNA for Rat Substance P Receptor.” <i>Journal of Biological Chemistry</i>. American Society for Biochemistry and Molecular Biology, 1989. <a href=\"https://doi.org/doi.org/10.1016/S0021-9258(19)84619-7\">https://doi.org/doi.org/10.1016/S0021-9258(19)84619-7</a>.","apa":"Yokota, Y., Sasai, Y., Tanaka, K., Fujiwara, T., Tsuchida, K., Shigemoto, R., … Nakanishi, S. (1989). Molecular characterization of a functional cDNA for rat substance P receptor. <i>Journal of Biological Chemistry</i>. American Society for Biochemistry and Molecular Biology. <a href=\"https://doi.org/doi.org/10.1016/S0021-9258(19)84619-7\">https://doi.org/doi.org/10.1016/S0021-9258(19)84619-7</a>"},"publication_identifier":{"issn":["0021-9258"],"eissn":["1083-351X"]},"title":"Molecular characterization of a functional cDNA for rat substance P receptor","publication":"Journal of Biological Chemistry","publisher":"American Society for Biochemistry and Molecular Biology","oa_version":"Published Version","date_created":"2018-12-11T11:58:11Z","publist_id":"4374","abstract":[{"lang":"eng","text":"This paper describes the amino acid sequence of the rat substance P receptor and its comparison with that of the rat substance K receptor on the basis of molecular cloning and sequence analysis. From a rat brain cDNA library constructed with an RNA expression vector, we identified a cDNA mixture containing a functional substance P receptor cDNA by examining electrophysiologically a receptor expression following injection of the mRNAs synthesized in vitro into Xenopus oocytes. A receptor cDNA clone was then isolated by cross-hybridization with the bovine substance K receptor DNA. The clone was confirmed by selective binding of substance P to the cloned receptor expressed in mammalian COS cells. The deduced amino acid sequence (407 amino acid residues) possesses seven putative membrane spanning domains and shows a sequence similarity to the members of G-protein-coupled receptors. The rat substance P and substance K receptor are very similar in both size and amino acid sequences, particularly in the putative transmembrane similarity is in marked contrast to the sequence divergence in the amino- and carboxyl-terminal regions and the third cytoplasmic loop. The observed sequence similarytity and divergence would thus contribute to the expression of similar but pharmacological regions and the first and second cytoplasmic loops. This distinguishable activities of the two tachykinin receptors."}],"extern":"1","main_file_link":[{"open_access":"1","url":"https://www.sciencedirect.com/science/article/pii/S0021925819846197"}],"intvolume":"       264","publication_status":"published","pmid":1,"day":"25","language":[{"iso":"eng"}],"month":"10","date_published":"1989-10-25T00:00:00Z","author":[{"full_name":"Yokota, Yoshifumi","last_name":"Yokota","first_name":"Yoshifumi"},{"first_name":"Yoshiki","last_name":"Sasai","full_name":"Sasai, Yoshiki"},{"first_name":"Kohichi","last_name":"Tanaka","full_name":"Tanaka, Kohichi"},{"first_name":"Tsutomu","last_name":"Fujiwara","full_name":"Fujiwara, Tsutomu"},{"first_name":"Kunihiro","last_name":"Tsuchida","full_name":"Tsuchida, Kunihiro"},{"full_name":"Shigemoto, Ryuichi","id":"499F3ABC-F248-11E8-B48F-1D18A9856A87","first_name":"Ryuichi","last_name":"Shigemoto","orcid":"0000-0001-8761-9444"},{"full_name":"Kakizuka, Akira","last_name":"Kakizuka","first_name":"Akira"},{"full_name":"Ohkubo, Hiroaki","last_name":"Ohkubo","first_name":"Hiroaki"},{"last_name":"Nakanishi","first_name":"Shigetada","full_name":"Nakanishi, Shigetada"}],"doi":"doi.org/10.1016/S0021-9258(19)84619-7","date_updated":"2022-02-15T09:29:36Z","article_processing_charge":"No","scopus_import":"1","quality_controlled":"1"},{"main_file_link":[{"open_access":"1","url":"http://www.ncbi.nlm.nih.gov/pmc/articles/PMC298032/?tool=pubmed"}],"intvolume":"        86","publication_status":"published","pmid":1,"day":"01","language":[{"iso":"eng"}],"month":"09","date_published":"1989-09-01T00:00:00Z","author":[{"full_name":"Jonas, Peter M","id":"353C1B58-F248-11E8-B48F-1D18A9856A87","first_name":"Peter M","last_name":"Jonas","orcid":"0000-0001-5001-4804"},{"last_name":"Bräu","first_name":"Michael","full_name":"Bräu, Michael"},{"first_name":"Markus","last_name":"Hermsteiner","full_name":"Hermsteiner, Markus"},{"full_name":"Vogel, Werner","first_name":"Werner","last_name":"Vogel"}],"date_updated":"2022-02-14T16:12:33Z","doi":"10.1073/pnas.86.18.7238","article_processing_charge":"No","quality_controlled":"1","page":"7238 - 7242","volume":86,"type":"journal_article","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","_id":"3466","year":"1989","acknowledgement":"We thank Drs. C. Baumann, D. Siemen, and W. Stuhmer for reading the manuscript and Dr. F. Dreyer for the generous gift of DTX. The study was supported by the Deutsche Forschungsgemeinschaft.","status":"public","oa":1,"article_type":"original","external_id":{"pmid":["2550937 "]},"issue":"18","citation":{"apa":"Jonas, P. M., Bräu, M., Hermsteiner, M., &#38; Vogel, W. (1989). Single-channel recording in myelinated nerve fibers reveals one type of Na channel but different K channels. <i>PNAS</i>. National Academy of Sciences. <a href=\"https://doi.org/10.1073/pnas.86.18.7238\">https://doi.org/10.1073/pnas.86.18.7238</a>","chicago":"Jonas, Peter M, Michael Bräu, Markus Hermsteiner, and Werner Vogel. “Single-Channel Recording in Myelinated Nerve Fibers Reveals One Type of Na Channel but Different K Channels.” <i>PNAS</i>. National Academy of Sciences, 1989. <a href=\"https://doi.org/10.1073/pnas.86.18.7238\">https://doi.org/10.1073/pnas.86.18.7238</a>.","ieee":"P. M. Jonas, M. Bräu, M. Hermsteiner, and W. Vogel, “Single-channel recording in myelinated nerve fibers reveals one type of Na channel but different K channels,” <i>PNAS</i>, vol. 86, no. 18. National Academy of Sciences, pp. 7238–7242, 1989.","mla":"Jonas, Peter M., et al. “Single-Channel Recording in Myelinated Nerve Fibers Reveals One Type of Na Channel but Different K Channels.” <i>PNAS</i>, vol. 86, no. 18, National Academy of Sciences, 1989, pp. 7238–42, doi:<a href=\"https://doi.org/10.1073/pnas.86.18.7238\">10.1073/pnas.86.18.7238</a>.","short":"P.M. Jonas, M. Bräu, M. Hermsteiner, W. Vogel, PNAS 86 (1989) 7238–7242.","ista":"Jonas PM, Bräu M, Hermsteiner M, Vogel W. 1989. Single-channel recording in myelinated nerve fibers reveals one type of Na channel but different K channels. PNAS. 86(18), 7238–7242.","ama":"Jonas PM, Bräu M, Hermsteiner M, Vogel W. Single-channel recording in myelinated nerve fibers reveals one type of Na channel but different K channels. <i>PNAS</i>. 1989;86(18):7238-7242. doi:<a href=\"https://doi.org/10.1073/pnas.86.18.7238\">10.1073/pnas.86.18.7238</a>"},"publication_identifier":{"eissn":["1091-6490"],"issn":["0027-8424"]},"title":"Single-channel recording in myelinated nerve fibers reveals one type of Na channel but different K channels","publication":"PNAS","publisher":"National Academy of Sciences","oa_version":"Published Version","date_created":"2018-12-11T12:03:28Z","publist_id":"2921","abstract":[{"lang":"eng","text":"Amphibian myelinated nerve fibers were treated with collagenase and protease. Axons with retraction of the myelin sheath were patch-clamped in the nodal and paranodal region. One type of Na channel was found. It has a single-channel conductance of 11 pS (15 degrees C) and is blocked by tetrodotoxin. Averaged events show the typical activation and inactivation kinetics of macroscopic Na current. Three potential-dependent K channels were identified (I, F, and S channel). The I channel, being the most frequent type, has a single-channel conductance of 23 pS (inward current, 105 mM K on both sides of the membrane), activates between -60 and -30 mV, deactivates with intermediate kinetics, and is sensitive to dendrotoxin. The F channel has a conductance of 30 pS, activates between -40 and 60 mV, and deactivates with fast kinetics. The former inactivates within tens of seconds; the latter inactivates within seconds. The third type, the S channel, has a conductance of 7 pS and deactivates slowly. All three channels can be blocked by external tetraethylammonium chloride. We suggest that these distinct K channel types form the basis for the different components of macroscopic K current described previously."}],"extern":"1"},{"publication_status":"published","intvolume":"       122","main_file_link":[{"open_access":"1","url":"http://www.ncbi.nlm.nih.gov/pmc/articles/PMC1203771"}],"day":"01","pmid":1,"month":"08","language":[{"iso":"eng"}],"article_processing_charge":"No","doi":"10.1093/genetics/122.4.967","date_updated":"2022-02-14T14:07:12Z","date_published":"1989-08-01T00:00:00Z","author":[{"full_name":"Mallet, James","first_name":"James","last_name":"Mallet"},{"first_name":"Nicholas H","orcid":"0000-0002-8548-5240","last_name":"Barton","full_name":"Barton, Nicholas H","id":"4880FE40-F248-11E8-B48F-1D18A9856A87"}],"quality_controlled":"1","scopus_import":"1","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","type":"journal_article","volume":122,"page":"967 - 976","year":"1989","_id":"3652","issue":"4","article_type":"original","external_id":{"pmid":["2759433"]},"oa":1,"acknowledgement":"The publication costs of this article were partly defrayed by the payment of page charges. This article must therefore be hereby marked “advertisment” in accordance with 18 U.S.C. §1734 solely to indicate this fact. \r\n\r\nWe thank the Natural Environmental Research Council for financial support, and N. SANDERSON, M. SLATKIN and an anonymous reviewer for comments on the manuscript.","status":"public","publication_identifier":{"issn":["0016-6731"]},"citation":{"short":"J. Mallet, N.H. Barton, Genetics 122 (1989) 967–976.","mla":"Mallet, James, and Nicholas H. Barton. “Inference from Clines Stabilized by Frequency-Dependent Selection.” <i>Genetics</i>, vol. 122, no. 4, Genetics Society of America, 1989, pp. 967–76, doi:<a href=\"https://doi.org/10.1093/genetics/122.4.967\">10.1093/genetics/122.4.967</a>.","ista":"Mallet J, Barton NH. 1989. Inference from clines stabilized by frequency-dependent selection. Genetics. 122(4), 967–976.","ama":"Mallet J, Barton NH. Inference from clines stabilized by frequency-dependent selection. <i>Genetics</i>. 1989;122(4):967-976. doi:<a href=\"https://doi.org/10.1093/genetics/122.4.967\">10.1093/genetics/122.4.967</a>","apa":"Mallet, J., &#38; Barton, N. H. (1989). Inference from clines stabilized by frequency-dependent selection. <i>Genetics</i>. Genetics Society of America. <a href=\"https://doi.org/10.1093/genetics/122.4.967\">https://doi.org/10.1093/genetics/122.4.967</a>","ieee":"J. Mallet and N. H. Barton, “Inference from clines stabilized by frequency-dependent selection,” <i>Genetics</i>, vol. 122, no. 4. Genetics Society of America, pp. 967–976, 1989.","chicago":"Mallet, James, and Nicholas H Barton. “Inference from Clines Stabilized by Frequency-Dependent Selection.” <i>Genetics</i>. Genetics Society of America, 1989. <a href=\"https://doi.org/10.1093/genetics/122.4.967\">https://doi.org/10.1093/genetics/122.4.967</a>."},"publisher":"Genetics Society of America","publication":"Genetics","title":"Inference from clines stabilized by frequency-dependent selection","publist_id":"2731","date_created":"2018-12-11T12:04:27Z","oa_version":"None","extern":"1","abstract":[{"text":"Frequency-dependent selection against rare forms can maintain clines. For weak selection, s, in simple linear models of frequency-dependence, single locus clines are stabilized with a maximum slope of between square root of s/square root of 8 sigma and square root of s/square root of 12 delta, where sigma is the dispersal distance. These clines are similar to those maintained by heterozygote disadvantage. Using computer simulations, the weak-selection analytical results are extended to higher selection pressures with up to three unlinked genes. Graphs are used to display the effect of selection, migration, dominance, and number of loci on cline widths, speeds of cline movements, two-way gametic correlations (\"linkage disequilibria\"), and heterozygote deficits. The effects of changing the order of reproduction, migration, and selection, are also briefly explored. Epistasis can also maintain tension zones. We show that epistatic selection is similar in its effects to frequency-dependent selection, except that the disequilibria produced in the zone will be higher for a given level of selection. If selection consists of a mixture of frequency-dependence and epistasis, as is likely in nature, the error made in estimating selection is usually less than twofold. From the graphs, selection and migration can be estimated using knowledge of the dominance and number of genes, of gene frequencies and of gametic correlations from a hybrid zone.","lang":"eng"}]},{"author":[{"last_name":"Edelsbrunner","orcid":"0000-0002-9823-6833","first_name":"Herbert","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","full_name":"Edelsbrunner, Herbert"},{"full_name":"Guibas, Leonidas","last_name":"Guibas","first_name":"Leonidas"},{"last_name":"Sharir","first_name":"Micha","full_name":"Sharir, Micha"}],"date_published":"1989-12-01T00:00:00Z","doi":"10.1007/BF02187733","date_updated":"2022-02-10T15:53:48Z","article_processing_charge":"No","quality_controlled":"1","intvolume":"         4","main_file_link":[{"open_access":"1","url":"https://link.springer.com/article/10.1007/BF02187733"}],"publication_status":"published","day":"01","language":[{"iso":"eng"}],"month":"12","title":"The upper envelope of piecewise linear functions: Algorithms and applications","publication":"Discrete & Computational Geometry","publisher":"Springer","oa_version":"Published Version","date_created":"2018-12-11T12:06:50Z","publist_id":"2038","abstract":[{"text":"This paper studies applications of envelopes of piecewise linear functions to problems in computational geometry. Among these applications we find problems involving hidden line/surface elimination, motion planning, transversals of polytopes, and a new type of Voronoi diagram for clusters of points. All results are either combinatorial or computational in nature. They are based on the combinatorial analysis in two companion papers [PS] and [E2] and a divide-and-conquer algorithm for computing envelopes described in this paper.","lang":"eng"}],"extern":"1","page":"311 - 336","volume":4,"type":"journal_article","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","_id":"4081","year":"1989","oa":1,"acknowledgement":"Work on this paper by the first author has been supported by Amoco Fnd. Fac. Dev. Comput. Sci. 1-6-44862. Work by the third author has been supported by the Office of Naval Research Grant N00014-82-K-0381, National Science Foundation Grant No. NSF-DCR-83-20085, by grants from the Digital Equipment Corporation and the IBM Corporation, and by a research grant from NCRD, the Israeli National Council for Research and Development.","status":"public","article_type":"original","issue":"1","citation":{"apa":"Edelsbrunner, H., Guibas, L., &#38; Sharir, M. (1989). The upper envelope of piecewise linear functions: Algorithms and applications. <i>Discrete &#38; Computational Geometry</i>. Springer. <a href=\"https://doi.org/10.1007/BF02187733\">https://doi.org/10.1007/BF02187733</a>","chicago":"Edelsbrunner, Herbert, Leonidas Guibas, and Micha Sharir. “The Upper Envelope of Piecewise Linear Functions: Algorithms and Applications.” <i>Discrete &#38; Computational Geometry</i>. Springer, 1989. <a href=\"https://doi.org/10.1007/BF02187733\">https://doi.org/10.1007/BF02187733</a>.","ieee":"H. Edelsbrunner, L. Guibas, and M. Sharir, “The upper envelope of piecewise linear functions: Algorithms and applications,” <i>Discrete &#38; Computational Geometry</i>, vol. 4, no. 1. Springer, pp. 311–336, 1989.","ista":"Edelsbrunner H, Guibas L, Sharir M. 1989. The upper envelope of piecewise linear functions: Algorithms and applications. Discrete &#38; Computational Geometry. 4(1), 311–336.","short":"H. Edelsbrunner, L. Guibas, M. Sharir, Discrete &#38; Computational Geometry 4 (1989) 311–336.","mla":"Edelsbrunner, Herbert, et al. “The Upper Envelope of Piecewise Linear Functions: Algorithms and Applications.” <i>Discrete &#38; Computational Geometry</i>, vol. 4, no. 1, Springer, 1989, pp. 311–36, doi:<a href=\"https://doi.org/10.1007/BF02187733\">10.1007/BF02187733</a>.","ama":"Edelsbrunner H, Guibas L, Sharir M. The upper envelope of piecewise linear functions: Algorithms and applications. <i>Discrete &#38; Computational Geometry</i>. 1989;4(1):311-336. doi:<a href=\"https://doi.org/10.1007/BF02187733\">10.1007/BF02187733</a>"},"publication_identifier":{"eissn":["1432-0444"],"issn":["0179-5376"]}},{"scopus_import":"1","quality_controlled":"1","author":[{"last_name":"Edelsbrunner","orcid":"0000-0002-9823-6833","first_name":"Herbert","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","full_name":"Edelsbrunner, Herbert"},{"full_name":"Guibas, Leonidas","first_name":"Leonidas","last_name":"Guibas"}],"date_published":"1989-02-01T00:00:00Z","article_processing_charge":"No","date_updated":"2022-02-10T16:06:05Z","doi":"10.1016/0022-0000(89)90038-X","main_file_link":[{"open_access":"1","url":"https://www.sciencedirect.com/science/article/pii/002200008990038X?via%3Dihub"}],"intvolume":"        38","publication_status":"published","month":"02","language":[{"iso":"eng"}],"day":"01","date_created":"2018-12-11T12:06:50Z","oa_version":"Published Version","publist_id":"2039","publication":"Journal of Computer and System Sciences","title":"Topologically sweeping an arrangement","publisher":"Elsevier","abstract":[{"text":"Sweeping a collection of figures in the Euclidean plane with a straight line is one of the novel algorithmic paradigms that have emerged in the field of computational geometry. In this paper we demonstrate the advantages of sweeping with a topological line that is not necessarily straight. We show how an arrangement of n lines in the plane can be swept over in O(n2) time and O(n) space by a such a line. In the process each element, i.e., vertex, edge, or region, is visited once in a consistent ordering. Our technique makes use of novel data structures which exhibit interesting amortized complexity behavior; the result is an algorithm that improves upon all its predecessors either in the space or the time bounds, as well as being eminently practical. Numerous applications of the technique to problems in computational geometry are given—many through the use of duality transforms. Examples include solving visibility problems, detecting degeneracies in configurations, computing the extremal shadows of convex polytopes, and others. Even though our basic technique solves a planar problem, its applications include several problems in higher dimensions.","lang":"eng"}],"extern":"1","_id":"4082","year":"1989","volume":38,"page":"165 - 194","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","type":"journal_article","citation":{"ieee":"H. Edelsbrunner and L. Guibas, “Topologically sweeping an arrangement,” <i>Journal of Computer and System Sciences</i>, vol. 38, no. 1. Elsevier, pp. 165–194, 1989.","chicago":"Edelsbrunner, Herbert, and Leonidas Guibas. “Topologically Sweeping an Arrangement.” <i>Journal of Computer and System Sciences</i>. Elsevier, 1989. <a href=\"https://doi.org/10.1016/0022-0000(89)90038-X\">https://doi.org/10.1016/0022-0000(89)90038-X</a>.","apa":"Edelsbrunner, H., &#38; Guibas, L. (1989). Topologically sweeping an arrangement. <i>Journal of Computer and System Sciences</i>. Elsevier. <a href=\"https://doi.org/10.1016/0022-0000(89)90038-X\">https://doi.org/10.1016/0022-0000(89)90038-X</a>","ama":"Edelsbrunner H, Guibas L. Topologically sweeping an arrangement. <i>Journal of Computer and System Sciences</i>. 1989;38(1):165-194. doi:<a href=\"https://doi.org/10.1016/0022-0000(89)90038-X\">10.1016/0022-0000(89)90038-X</a>","mla":"Edelsbrunner, Herbert, and Leonidas Guibas. “Topologically Sweeping an Arrangement.” <i>Journal of Computer and System Sciences</i>, vol. 38, no. 1, Elsevier, 1989, pp. 165–94, doi:<a href=\"https://doi.org/10.1016/0022-0000(89)90038-X\">10.1016/0022-0000(89)90038-X</a>.","ista":"Edelsbrunner H, Guibas L. 1989. Topologically sweeping an arrangement. Journal of Computer and System Sciences. 38(1), 165–194.","short":"H. Edelsbrunner, L. Guibas, Journal of Computer and System Sciences 38 (1989) 165–194."},"publication_identifier":{"eissn":["1090-2724"],"issn":["0022-0000"]},"status":"public","acknowledgement":"he authors wish to thank Raimund Seidel for suggesting the argument that we used to prove Theorem 3.1, Harald Rosenberger who implemented the topological sweep and compared it with a straight line sweep, the students who took the Stanford 1985 analysis of algorithms qualifying examination and suffered through a version of this problem, and finally Lyle Ramshaw and Cynthia Hibbard for their detailed reading and comments on the manuscript. The constructive criticism of an anonymous referee is also appreciated.","oa":1,"issue":"1","article_type":"original"},{"publication_identifier":{"issn":["0097-5397"],"eissn":["1095-7111"]},"citation":{"apa":"Yao, F., Dobkin, D., Edelsbrunner, H., &#38; Paterson, M. (1989). Partitioning space for range queries. <i>SIAM Journal on Computing</i>. SIAM. <a href=\"https://doi.org/10.1137/0218025\">https://doi.org/10.1137/0218025</a>","chicago":"Yao, F., David Dobkin, Herbert Edelsbrunner, and Michael Paterson. “Partitioning Space for Range Queries.” <i>SIAM Journal on Computing</i>. SIAM, 1989. <a href=\"https://doi.org/10.1137/0218025\">https://doi.org/10.1137/0218025</a>.","ieee":"F. Yao, D. Dobkin, H. Edelsbrunner, and M. Paterson, “Partitioning space for range queries,” <i>SIAM Journal on Computing</i>, vol. 18, no. 2. SIAM, pp. 371–384, 1989.","ista":"Yao F, Dobkin D, Edelsbrunner H, Paterson M. 1989. Partitioning space for range queries. SIAM Journal on Computing. 18(2), 371–384.","mla":"Yao, F., et al. “Partitioning Space for Range Queries.” <i>SIAM Journal on Computing</i>, vol. 18, no. 2, SIAM, 1989, pp. 371–84, doi:<a href=\"https://doi.org/10.1137/0218025\">10.1137/0218025</a>.","short":"F. Yao, D. Dobkin, H. Edelsbrunner, M. Paterson, SIAM Journal on Computing 18 (1989) 371–384.","ama":"Yao F, Dobkin D, Edelsbrunner H, Paterson M. Partitioning space for range queries. <i>SIAM Journal on Computing</i>. 1989;18(2):371-384. doi:<a href=\"https://doi.org/10.1137/0218025\">10.1137/0218025</a>"},"issue":"2","article_type":"original","status":"public","oa":1,"year":"1989","_id":"4083","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","type":"journal_article","volume":18,"page":"371 - 384","extern":"1","abstract":[{"text":"It is shown that, given a set S of n points in $R^3 $, one can always find three planes that form an eight-partition of S, that is, a partition where at most ${n / 8}$ points of S lie in each of the eight open regions. This theorem is used to define a data structure, called an octant tree, for representing any point set in $R^3 $. An octant tree for n points occupies $O(n)$ space and can be constructed in polynomial time. With this data structure and its refinements, efficient solutions to various range query problems in two and three dimensions can be obtained, including (1) half-space queries: find all points of S that lie to one side of any given plane; (2) polyhedron queries: find all points that lie inside (outside) any given polyhedron; and (3) circle queries in $R^2 $: for a planar set S, find all points that lie inside (outside) any given circle. The retrieval time for all these queries is $T(n) = O(n^\\alpha + m)$, where $\\alpha = 0.8988$ (or 0.8471 in case (3)), and m is the size of the output. This performance is the best currently known for linear-space data structures that can be deterministically constructed in polynomial time.","lang":"eng"}],"publist_id":"2040","date_created":"2018-12-11T12:06:50Z","oa_version":"Published Version","publisher":"SIAM","publication":"SIAM Journal on Computing","title":"Partitioning space for range queries","month":"04","language":[{"iso":"eng"}],"day":"01","publication_status":"published","main_file_link":[{"open_access":"1","url":"https://epubs.siam.org/doi/10.1137/0218025"}],"intvolume":"        18","quality_controlled":"1","scopus_import":"1","article_processing_charge":"No","date_updated":"2022-02-11T07:55:48Z","doi":"10.1137/0218025","date_published":"1989-04-01T00:00:00Z","author":[{"full_name":"Yao, F.","last_name":"Yao","first_name":"F."},{"first_name":"David","last_name":"Dobkin","full_name":"Dobkin, David"},{"first_name":"Herbert","orcid":"0000-0002-9823-6833","last_name":"Edelsbrunner","full_name":"Edelsbrunner, Herbert","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Michael","last_name":"Paterson","full_name":"Paterson, Michael"}]},{"author":[{"first_name":"Herbert","last_name":"Edelsbrunner","orcid":"0000-0002-9823-6833","full_name":"Edelsbrunner, Herbert","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Rote, Günter","first_name":"Günter","last_name":"Rote"},{"last_name":"Welzl","first_name":"Emo","full_name":"Welzl, Emo"}],"date_published":"1989-08-01T00:00:00Z","article_processing_charge":"No","doi":"10.1016/0304-3975(89)90133-3","date_updated":"2022-02-11T11:15:43Z","scopus_import":"1","quality_controlled":"1","intvolume":"        66","main_file_link":[{"url":"https://www.sciencedirect.com/science/article/pii/0304397589901333?via%3Dihub","open_access":"1"}],"publication_status":"published","day":"01","month":"08","language":[{"iso":"eng"}],"publication":"Theoretical Computer Science","title":"Testing the necklace condition for shortest tours and optimal factors in the plane","publisher":"Elsevier","date_created":"2018-12-11T12:06:51Z","oa_version":"Published Version","publist_id":"2041","abstract":[{"text":"A tour  of a finite set P of points is a necklace-tour if there are disks with the points in P as centers such that two disks intersect if and only if their centers are adjacent in . It has been observed by Sanders that a necklace-tour is an optimal traveling salesman tour.\r\n\r\nIn this paper, we present an algorithm that either reports that no necklace-tour exists or outputs a necklace-tour of a given set of n points in O(n2 log n) time. If a tour is given, then we can test in O(n2) time whether or not this tour is a necklace-tour. Both algorithms can be generalized to ƒ-factors of point sets in the plane. The complexity results rely on a combinatorial analysis of certain intersection graphs of disks defined for finite sets of points in the plane.","lang":"eng"}],"extern":"1","volume":66,"page":"157 - 180","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","type":"journal_article","_id":"4084","year":"1989","status":"public","oa":1,"issue":"2","article_type":"original","citation":{"ieee":"H. Edelsbrunner, G. Rote, and E. Welzl, “Testing the necklace condition for shortest tours and optimal factors in the plane,” <i>Theoretical Computer Science</i>, vol. 66, no. 2. Elsevier, pp. 157–180, 1989.","chicago":"Edelsbrunner, Herbert, Günter Rote, and Emo Welzl. “Testing the Necklace Condition for Shortest Tours and Optimal Factors in the Plane.” <i>Theoretical Computer Science</i>. Elsevier, 1989. <a href=\"https://doi.org/10.1016/0304-3975(89)90133-3\">https://doi.org/10.1016/0304-3975(89)90133-3</a>.","apa":"Edelsbrunner, H., Rote, G., &#38; Welzl, E. (1989). Testing the necklace condition for shortest tours and optimal factors in the plane. <i>Theoretical Computer Science</i>. Elsevier. <a href=\"https://doi.org/10.1016/0304-3975(89)90133-3\">https://doi.org/10.1016/0304-3975(89)90133-3</a>","ama":"Edelsbrunner H, Rote G, Welzl E. Testing the necklace condition for shortest tours and optimal factors in the plane. <i>Theoretical Computer Science</i>. 1989;66(2):157-180. doi:<a href=\"https://doi.org/10.1016/0304-3975(89)90133-3\">10.1016/0304-3975(89)90133-3</a>","ista":"Edelsbrunner H, Rote G, Welzl E. 1989. Testing the necklace condition for shortest tours and optimal factors in the plane. Theoretical Computer Science. 66(2), 157–180.","mla":"Edelsbrunner, Herbert, et al. “Testing the Necklace Condition for Shortest Tours and Optimal Factors in the Plane.” <i>Theoretical Computer Science</i>, vol. 66, no. 2, Elsevier, 1989, pp. 157–80, doi:<a href=\"https://doi.org/10.1016/0304-3975(89)90133-3\">10.1016/0304-3975(89)90133-3</a>.","short":"H. Edelsbrunner, G. Rote, E. Welzl, Theoretical Computer Science 66 (1989) 157–180."},"publication_identifier":{"issn":["0304-3975"],"eissn":["1879-2294"]}},{"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."}],"extern":"1","date_created":"2018-12-11T12:06:51Z","oa_version":"Published Version","publist_id":"2034","publication":"Discrete & Computational Geometry","title":"The upper envelope of piecewise linear functions: Tight bounds on the number of faces ","publisher":"Springer","citation":{"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.","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>","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>","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."},"publication_identifier":{"issn":["0179-5376"],"eissn":["1432-0444"]},"status":"public","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","oa":1,"issue":"4","article_type":"original","_id":"4086","year":"1989","volume":4,"page":"337 - 343","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","type":"journal_article","scopus_import":"1","quality_controlled":"1","date_published":"1989-11-01T00:00:00Z","author":[{"id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","full_name":"Edelsbrunner, Herbert","orcid":"0000-0002-9823-6833","last_name":"Edelsbrunner","first_name":"Herbert"}],"article_processing_charge":"No","date_updated":"2022-02-10T11:08:12Z","doi":"10.1007/BF02187734","month":"11","language":[{"iso":"eng"}],"day":"01","intvolume":"         4","main_file_link":[{"url":"https://link.springer.com/article/10.1007/BF02187734","open_access":"1"}],"publication_status":"published"},{"date_published":"1989-12-01T00:00:00Z","author":[{"id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","full_name":"Edelsbrunner, Herbert","last_name":"Edelsbrunner","orcid":"0000-0002-9823-6833","first_name":"Herbert"},{"last_name":"Guibas","first_name":"Leonidas","full_name":"Guibas, Leonidas"},{"full_name":"Hershberger, John","first_name":"John","last_name":"Hershberger"},{"last_name":"Seidel","first_name":"Raimund","full_name":"Seidel, Raimund"},{"full_name":"Sharir, Micha","last_name":"Sharir","first_name":"Micha"},{"last_name":"Snoeyink","first_name":"Jack","full_name":"Snoeyink, Jack"},{"full_name":"Welzl, Emo","last_name":"Welzl","first_name":"Emo"}],"date_updated":"2022-02-10T15:03:48Z","doi":"10.1007/BF02187742","article_processing_charge":"No","scopus_import":"1","quality_controlled":"1","main_file_link":[{"url":"https://link.springer.com/article/10.1007/BF02187742","open_access":"1"}],"intvolume":"         4","publication_status":"published","day":"01","language":[{"iso":"eng"}],"month":"12","title":"Implicitly representing arrangements of lines or segments","publication":"Discrete & Computational Geometry","publisher":"Springer","oa_version":"Published Version","date_created":"2018-12-11T12:06:52Z","publist_id":"2036","abstract":[{"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.","lang":"eng"}],"extern":"1","page":"433 - 466","volume":4,"type":"journal_article","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","_id":"4088","year":"1989","oa":1,"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.","status":"public","article_type":"original","issue":"1","citation":{"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.","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>","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>","short":"H. Edelsbrunner, L. Guibas, J. Hershberger, R. Seidel, M. Sharir, J. Snoeyink, E. Welzl, Discrete &#38; Computational Geometry 4 (1989) 433–466.","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>."},"publication_identifier":{"issn":["0179-5376"],"eissn":["1432-0444"]}},{"quality_controlled":"1","scopus_import":"1","article_processing_charge":"No","doi":"10.1007/BF02187745","date_updated":"2022-02-10T15:40:04Z","date_published":"1989-12-01T00:00:00Z","author":[{"orcid":"0000-0002-9823-6833","last_name":"Edelsbrunner","first_name":"Herbert","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","full_name":"Edelsbrunner, Herbert"},{"full_name":"Guibas, Leonidas","last_name":"Guibas","first_name":"Leonidas"},{"full_name":"Hershberger, John","first_name":"John","last_name":"Hershberger"},{"full_name":"Pach, János","last_name":"Pach","first_name":"János"},{"full_name":"Pollack, Richard","last_name":"Pollack","first_name":"Richard"},{"first_name":"Raimund","last_name":"Seidel","full_name":"Seidel, Raimund"},{"full_name":"Sharir, Micha","first_name":"Micha","last_name":"Sharir"},{"first_name":"Jack","last_name":"Snoeyink","full_name":"Snoeyink, Jack"}],"month":"12","language":[{"iso":"eng"}],"day":"01","publication_status":"published","intvolume":"         4","main_file_link":[{"url":"https://link.springer.com/article/10.1007/BF02187745","open_access":"1"}],"extern":"1","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."}],"publist_id":"2037","date_created":"2018-12-11T12:06:52Z","oa_version":"Published Version","publisher":"Springer","publication":"Discrete & Computational Geometry","title":"On arrangements of Jordan arcs with three intersections per pair","publication_identifier":{"issn":["0179-5376"],"eissn":["1432-0444"]},"citation":{"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.","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.","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.","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>"},"issue":"1","article_type":"original","oa":1,"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.","status":"public","year":"1989","_id":"4089","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","type":"journal_article","volume":4,"page":"523 - 539"},{"date_published":"1988-07-01T00:00:00Z","author":[{"first_name":"John","last_name":"Dallas","full_name":"Dallas, John"},{"first_name":"Nicholas H","orcid":"0000-0002-8548-5240","last_name":"Barton","full_name":"Barton, Nicholas H","id":"4880FE40-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Dover","first_name":"Gabriel","full_name":"Dover, Gabriel"}],"article_processing_charge":"No","doi":"10.1093/oxfordjournals.molbev.a040528","date_updated":"2022-02-08T13:20:51Z","quality_controlled":"1","main_file_link":[{"open_access":"1","url":"https://academic.oup.com/mbe/article/5/6/660/1044340"}],"intvolume":"         5","publication_status":"published","day":"01","month":"07","language":[{"iso":"eng"}],"publication":"Molecular Biology and Evolution","title":"Interracial rDNA variation in the grasshopper Podisma Pedestris","publisher":"Oxford University Press","date_created":"2018-12-11T12:04:28Z","oa_version":"None","publist_id":"2728","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. "}],"extern":"1","volume":5,"page":"660 - 674","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","type":"journal_article","_id":"3655","year":"1988","status":"public","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. ","oa":1,"issue":"6","article_type":"original","citation":{"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.","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>.","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>","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>","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.","ista":"Dallas J, Barton NH, Dover G. 1988. Interracial rDNA variation in the grasshopper Podisma Pedestris. Molecular Biology and Evolution. 5(6), 660–674."},"publication_identifier":{"eissn":["1537-1719"],"issn":["0737-4038"]}},{"date_updated":"2022-02-08T10:36:30Z","doi":"10.1016/0890-5401(88)90049-1","article_processing_charge":"No","author":[{"orcid":"0000-0002-9823-6833","last_name":"Edelsbrunner","first_name":"Herbert","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","full_name":"Edelsbrunner, Herbert"},{"last_name":"Preparata","first_name":"Franco","full_name":"Preparata, Franco"}],"date_published":"1988-06-01T00:00:00Z","quality_controlled":"1","scopus_import":"1","publication_status":"published","main_file_link":[{"url":"https://www.sciencedirect.com/science/article/pii/0890540188900491?via%3Dihub","open_access":"1"}],"intvolume":"        77","day":"01","language":[{"iso":"eng"}],"month":"06","publisher":"Elsevier","title":"Minimum polygonal separation","publication":"Information and Computation","publist_id":"2029","oa_version":"None","date_created":"2018-12-11T12:06:53Z","extern":"1","abstract":[{"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.","lang":"eng"}],"type":"journal_article","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","page":"218 - 232","volume":77,"year":"1988","_id":"4090","article_type":"original","issue":"3","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.","oa":1,"status":"public","publication_identifier":{"eissn":["0890-5401"]},"citation":{"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.","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>","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>","ista":"Edelsbrunner H, Preparata F. 1988. Minimum polygonal separation. Information and Computation. 77(3), 218–232.","short":"H. Edelsbrunner, F. Preparata, Information and Computation 77 (1988) 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>."}},{"publication_identifier":{"issn":["0018-067X"],"eissn":["1365-2540"]},"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>","short":"G. Hewitt, R. Nichols, N.H. Barton, Heredity 59 (1987) 457–466.","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>.","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.","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>.","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>"},"issue":"3","article_type":"original","status":"public","oa":1,"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","year":"1987","_id":"3658","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","type":"journal_article","volume":59,"page":"457 - 466","extern":"1","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."}],"publist_id":"2725","date_created":"2018-12-11T12:04:28Z","oa_version":"Published Version","publisher":"Nature Publishing Group","publication":"Heredity","title":"Homogamy in a hybrid zone in the alpine grasshopper Podisma pedestris","month":"12","language":[{"iso":"eng"}],"day":"01","publication_status":"published","main_file_link":[{"open_access":"1","url":"https://www.nature.com/articles/hdy1987156"}],"intvolume":"        59","quality_controlled":"1","scopus_import":"1","article_processing_charge":"No","date_updated":"2022-02-04T12:20:46Z","doi":"10.1038/hdy.1987.156","author":[{"full_name":"Hewitt, Godfrey","last_name":"Hewitt","first_name":"Godfrey"},{"full_name":"Nichols, R.","first_name":"R.","last_name":"Nichols"},{"first_name":"Nicholas H","orcid":"0000-0002-8548-5240","last_name":"Barton","full_name":"Barton, Nicholas H","id":"4880FE40-F248-11E8-B48F-1D18A9856A87"}],"date_published":"1987-12-01T00:00:00Z"},{"intvolume":"        58","main_file_link":[{"open_access":"1","url":"https://www.nature.com/articles/hdy198736"}],"publication_status":"published","month":"01","language":[{"iso":"eng"}],"day":"01","scopus_import":"1","quality_controlled":"1","date_published":"1987-01-01T00:00:00Z","author":[{"full_name":"Westerman, Michael","first_name":"Michael","last_name":"Westerman"},{"first_name":"Nicholas H","last_name":"Barton","orcid":"0000-0002-8548-5240","full_name":"Barton, Nicholas H","id":"4880FE40-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Godfrey","last_name":"Hewitt","full_name":"Hewitt, Godfrey"}],"article_processing_charge":"No","doi":"10.1038/hdy.1987.36","date_updated":"2022-02-03T10:48:40Z","_id":"4319","year":"1987","volume":58,"page":"221 - 228","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","type":"journal_article","citation":{"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>","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.","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>.","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>.","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.","short":"M. Westerman, N.H. Barton, G. Hewitt, Heredity 58 (1987) 221–228.","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>"},"publication_identifier":{"issn":["0018-067X"],"eissn":["1365-2540"]},"oa":1,"status":"public","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_type":"original","date_created":"2018-12-11T12:08:14Z","oa_version":"Published Version","publist_id":"1733","publication":"Heredity","title":"Differences in DNA content between two chromosomal races of the grasshopper Podisma pedestris","publisher":"Nature Publishing Group","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."}],"extern":"1"},{"language":[{"iso":"eng"}],"month":"06","pmid":1,"day":"01","main_file_link":[{"url":"https://www.nature.com/articles/hdy198663","open_access":"1"}],"intvolume":"        56","publication_status":"published","scopus_import":"1","quality_controlled":"1","author":[{"id":"4880FE40-F248-11E8-B48F-1D18A9856A87","full_name":"Barton, Nicholas H","orcid":"0000-0002-8548-5240","last_name":"Barton","first_name":"Nicholas H"},{"full_name":"Slatkin, Montgomery","first_name":"Montgomery","last_name":"Slatkin"}],"date_published":"1986-06-01T00:00:00Z","doi":"10.1038/hdy.1986.63","date_updated":"2022-02-01T15:04:01Z","article_processing_charge":"No","citation":{"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.","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>","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.","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>."},"publication_identifier":{"eissn":["1365-2540"],"issn":["0018-067X"]},"status":"public","oa":1,"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_type":"original","external_id":{"pmid":["3733460 "]},"issue":"3","_id":"3663","year":"1986","page":"409 - 416","volume":56,"type":"journal_article","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","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."}],"extern":"1","oa_version":"None","date_created":"2018-12-11T12:04:30Z","publist_id":"2720","title":"A quasi-equilibrium theory of the distribution of rare alleles in a subdivided population","publication":"Heredity","publisher":"Nature Publishing Group"},{"citation":{"ama":"Barton NH, Bengtsson B. The barrier to genetic exchange between hybridising populations. <i>Heredity</i>. 1986;57:357-376.","short":"N.H. Barton, B. Bengtsson, Heredity 57 (1986) 357–376.","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.","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.","chicago":"Barton, Nicholas H, and Bengt Bengtsson. “The Barrier to Genetic Exchange between Hybridising Populations.” <i>Heredity</i>. Nature Publishing Group, 1986.","apa":"Barton, N. H., &#38; Bengtsson, B. (1986). The barrier to genetic exchange between hybridising populations. <i>Heredity</i>. Nature Publishing Group."},"publication_identifier":{"eissn":["1365-2540"],"issn":["0018-067X"]},"oa":1,"status":"public","article_type":"original","_id":"3664","year":"1986","page":"357 - 376","volume":57,"type":"journal_article","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","abstract":[{"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.","lang":"eng"}],"extern":"1","oa_version":"Published Version","date_created":"2018-12-11T12:04:30Z","publist_id":"2719","title":"The barrier to genetic exchange between hybridising populations","publication":"Heredity","publisher":"Nature Publishing Group","language":[{"iso":"eng"}],"month":"01","day":"01","intvolume":"        57","main_file_link":[{"url":"https://www.nature.com/articles/hdy1986135","open_access":"1"}],"publication_status":"published","scopus_import":"1","quality_controlled":"1","author":[{"full_name":"Barton, Nicholas H","id":"4880FE40-F248-11E8-B48F-1D18A9856A87","first_name":"Nicholas H","orcid":"0000-0002-8548-5240","last_name":"Barton"},{"full_name":"Bengtsson, Bengt","first_name":"Bengt","last_name":"Bengtsson"}],"date_published":"1986-01-01T00:00:00Z","date_updated":"2022-02-01T14:49:02Z","article_processing_charge":"No"},{"date_published":"1986-01-01T00:00:00Z","author":[{"full_name":"Barton, Nicholas H","id":"4880FE40-F248-11E8-B48F-1D18A9856A87","first_name":"Nicholas H","orcid":"0000-0002-8548-5240","last_name":"Barton"}],"article_processing_charge":"No","date_updated":"2022-02-01T14:31:29Z","scopus_import":"1","quality_controlled":"1","day":"01","month":"01","language":[{"iso":"eng"}],"main_file_link":[{"url":"https://www.nature.com/articles/hdy1986142","open_access":"1"}],"intvolume":"        57","publication_status":"published","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."}],"extern":"1","publication":"Heredity","title":"The effects of linkage and density-dependent regulation on gene flow","publisher":"Nature Publishing Group","date_created":"2018-12-11T12:04:30Z","oa_version":"Published Version","publist_id":"2718","status":"public","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).","oa":1,"article_type":"original","citation":{"ama":"Barton NH. The effects of linkage and density-dependent regulation on gene flow. <i>Heredity</i>. 1986;57:415-426.","ista":"Barton NH. 1986. The effects of linkage and density-dependent regulation on gene flow. Heredity. 57, 415–426.","short":"N.H. Barton, Heredity 57 (1986) 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.","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.","apa":"Barton, N. H. (1986). The effects of linkage and density-dependent regulation on gene flow. <i>Heredity</i>. Nature Publishing Group."},"publication_identifier":{"issn":["0018-067X"],"eissn":["1365-2540"]},"volume":57,"page":"415 - 426","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","type":"journal_article","_id":"3665","year":"1986"},{"year":"1986","_id":"4098","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","type":"journal_article","volume":43,"page":"344 - 349","publication_identifier":{"eissn":["1096-0899"],"issn":["0097-3165"]},"citation":{"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>.","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.","short":"H. Edelsbrunner, G. Stöckl, Journal of Combinatorial Theory Series A 43 (1986) 344–349.","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."},"issue":"2","article_type":"original","status":"public","oa":1,"publist_id":"2020","date_created":"2018-12-11T12:06:56Z","oa_version":"None","publisher":"Elsevier","publication":"Journal of Combinatorial Theory Series A","title":"The number of extreme pairs of finite point-sets in Euclidean spaces","extern":"1","abstract":[{"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.","lang":"eng"}],"publication_status":"published","main_file_link":[{"url":"https://www.sciencedirect.com/science/article/pii/0097316586900750?via%3Dihub","open_access":"1"}],"intvolume":"        43","month":"11","language":[{"iso":"eng"}],"day":"01","quality_controlled":"1","scopus_import":"1","article_processing_charge":"No","date_updated":"2022-02-01T14:02:41Z","doi":"10.1016/0097-3165(86)90075-0","date_published":"1986-11-01T00:00:00Z","author":[{"orcid":"0000-0002-9823-6833","last_name":"Edelsbrunner","first_name":"Herbert","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","full_name":"Edelsbrunner, Herbert"},{"full_name":"Stöckl, Gerd","last_name":"Stöckl","first_name":"Gerd"}]}]