---
_id: '3565'
abstract:
- lang: eng
  text: We investigate the complexity of determining the shape and presentation (i.e.
    position with orientation) of convex polytopes in multi-dimensional Euclidean
    space using a variety of probe models.
acknowledgement: "NSF Grant MCS-83-03926 and DCR-85-05517\r\nAmoco Foundation Faculty
  Development in Computer Science\r\nNSF Grant DCR-84-01633 and DCR-84-01898"
article_processing_charge: No
author:
- first_name: David
  full_name: Dobkin, David
  last_name: Dobkin
- first_name: Herbert
  full_name: Edelsbrunner, Herbert
  id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
  last_name: Edelsbrunner
  orcid: 0000-0002-9823-6833
- first_name: Chee
  full_name: Yap, Chee
  last_name: Yap
citation:
  ama: 'Dobkin D, Edelsbrunner H, Yap C. Probing convex polytopes. In: Cox I, Wilfong
    G, eds. <i>Autonomous Robot Vehicles</i>. Springer; 1990:328-341. doi:<a href="https://doi.org/10.1007/978-1-4613-8997-2_25">10.1007/978-1-4613-8997-2_25</a>'
  apa: Dobkin, D., Edelsbrunner, H., &#38; Yap, C. (1990). Probing convex polytopes.
    In I. Cox &#38; G. Wilfong (Eds.), <i>Autonomous Robot Vehicles</i> (pp. 328–341).
    Springer. <a href="https://doi.org/10.1007/978-1-4613-8997-2_25">https://doi.org/10.1007/978-1-4613-8997-2_25</a>
  chicago: Dobkin, David, Herbert Edelsbrunner, and Chee Yap. “Probing Convex Polytopes.”
    In <i>Autonomous Robot Vehicles</i>, edited by Ingemar Cox and Gordon Wilfong,
    328–41. Springer, 1990. <a href="https://doi.org/10.1007/978-1-4613-8997-2_25">https://doi.org/10.1007/978-1-4613-8997-2_25</a>.
  ieee: D. Dobkin, H. Edelsbrunner, and C. Yap, “Probing convex polytopes,” in <i>Autonomous
    Robot Vehicles</i>, I. Cox and G. Wilfong, Eds. Springer, 1990, pp. 328–341.
  ista: 'Dobkin D, Edelsbrunner H, Yap C. 1990.Probing convex polytopes. In: Autonomous
    Robot Vehicles. , 328–341.'
  mla: Dobkin, David, et al. “Probing Convex Polytopes.” <i>Autonomous Robot Vehicles</i>,
    edited by Ingemar Cox and Gordon Wilfong, Springer, 1990, pp. 328–41, doi:<a href="https://doi.org/10.1007/978-1-4613-8997-2_25">10.1007/978-1-4613-8997-2_25</a>.
  short: D. Dobkin, H. Edelsbrunner, C. Yap, in:, I. Cox, G. Wilfong (Eds.), Autonomous
    Robot Vehicles, Springer, 1990, pp. 328–341.
date_created: 2018-12-11T12:03:59Z
date_published: 1990-01-01T00:00:00Z
date_updated: 2022-02-23T15:41:07Z
day: '01'
doi: 10.1007/978-1-4613-8997-2_25
editor:
- first_name: Ingemar
  full_name: Cox, Ingemar
  last_name: Cox
- first_name: Gordon
  full_name: Wilfong, Gordon
  last_name: Wilfong
extern: '1'
language:
- iso: eng
main_file_link:
- url: https://link.springer.com/chapter/10.1007/978-1-4613-8997-2_25
month: '01'
oa_version: None
page: 328 - 341
publication: Autonomous Robot Vehicles
publication_identifier:
  isbn:
  - 978-1-4613-8997-2
publication_status: published
publisher: Springer
publist_id: '2820'
quality_controlled: '1'
status: public
title: Probing convex polytopes
type: book_chapter
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
year: '1990'
...
---
_id: '3649'
abstract:
- lang: eng
  text: Selection on polygenic characters is generally analyzed by statistical methods
    that assume a Gaussian (normal) distribution of breeding values. We present an
    alternative analysis based on multilocus population genetics. We use a general
    representation of selection, recombination, and drift to analyze an idealized
    polygenic system in which all genetic effects are additive (i.e., both dominance
    and epistasis are absent), but no assumptions are made about the distribution
    of breeding values or the numbers of loci or alleles. Our analysis produces three
    results. First, our equations reproduce the standard recursions for the mean and
    additive variance if breeding values are Gaussian; but they also reveal how non-Gaussian
    distributions of breeding values will alter these dynamics. Second, an approximation
    valid for weak selection shows that even if genetic variance is attributable to
    an effectively infinite number of loci with only additive effects, selection will
    generally drive the distribution of breeding values away from a Gaussian distribution
    by creating multilocus linkage disequilibria. Long-term dynamics of means can
    depart substantially from the predictions of the standard selection recursions,
    but the discrepancy may often be negligible for short-term selection. Third, by
    including mutation, we show that, for realistic parameter values, linkage disequilibrium
    has little effect on the amount of additive variance maintained at an equilibrium
    between stabilizing selection and mutation. Each of these analytical results is
    supported by numerical calculations.
acknowledgement: 'We thank R. Burger, J. A. Coyne, W. G. Hill, A. A. Hoffmann, J.
  H. Gillespie, M. Slatkin, T. Nagylaki and Z.-B. Zeng for helpful discussions and
  comments on earlier drafts. Our research is supported by grants from the National
  Science Foundation (BSR-8866548), the Science and Engineering Research Council,
  and the Institute of Theoretical Dynamics at UCD. '
article_processing_charge: No
article_type: original
author:
- first_name: Michael
  full_name: Turelli, Michael
  last_name: Turelli
- 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: Turelli M, Barton NH. Dynamics of polygenic characters under selection. <i>Theoretical
    Population Biology</i>. 1990;38(1):1-57. doi:<a href="https://doi.org/10.1016/0040-5809(90)90002-D">10.1016/0040-5809(90)90002-D</a>
  apa: Turelli, M., &#38; Barton, N. H. (1990). Dynamics of polygenic characters under
    selection. <i>Theoretical Population Biology</i>. Academic Press. <a href="https://doi.org/10.1016/0040-5809(90)90002-D">https://doi.org/10.1016/0040-5809(90)90002-D</a>
  chicago: Turelli, Michael, and Nicholas H Barton. “Dynamics of Polygenic Characters
    under Selection.” <i>Theoretical Population Biology</i>. Academic Press, 1990.
    <a href="https://doi.org/10.1016/0040-5809(90)90002-D">https://doi.org/10.1016/0040-5809(90)90002-D</a>.
  ieee: M. Turelli and N. H. Barton, “Dynamics of polygenic characters under selection,”
    <i>Theoretical Population Biology</i>, vol. 38, no. 1. Academic Press, pp. 1–57,
    1990.
  ista: Turelli M, Barton NH. 1990. Dynamics of polygenic characters under selection.
    Theoretical Population Biology. 38(1), 1–57.
  mla: Turelli, Michael, and Nicholas H. Barton. “Dynamics of Polygenic Characters
    under Selection.” <i>Theoretical Population Biology</i>, vol. 38, no. 1, Academic
    Press, 1990, pp. 1–57, doi:<a href="https://doi.org/10.1016/0040-5809(90)90002-D">10.1016/0040-5809(90)90002-D</a>.
  short: M. Turelli, N.H. Barton, Theoretical Population Biology 38 (1990) 1–57.
date_created: 2018-12-11T12:04:26Z
date_published: 1990-01-01T00:00:00Z
date_updated: 2022-02-23T14:48:49Z
day: '01'
doi: 10.1016/0040-5809(90)90002-D
extern: '1'
intvolume: '        38'
issue: '1'
language:
- iso: eng
main_file_link:
- url: https://www.sciencedirect.com/science/article/pii/004058099090002D?via%3Dihub
month: '01'
oa_version: None
page: 1 - 57
publication: Theoretical Population Biology
publication_identifier:
  issn:
  - 0040-5809
publication_status: published
publisher: Academic Press
publist_id: '2734'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Dynamics of polygenic characters under selection
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 38
year: '1990'
...
---
_id: '3650'
abstract:
- lang: eng
  text: Hybrid zones can yield estimates of natural selection and gene flow. The width
    of a cline in gene frequency is approximately proportional to gene flow (σ) divided
    by the square root of per-locus selection ( &amp;s). Gene flow also causes gametic
    correlations (linkage disequilibria) between genes that differ across hybrid zones.
    Correlations are stronger when the hybrid zone is narrow, and rise to a maximum
    roughly equal to s. Thus cline width and gametic correlations combine to give
    estimates of gene flow and selection. These indirect measures of σ and s are especially
    useful because they can be made from collections, and require no field experiments.
    The method was applied to hybrid zones between color pattern races in a pair of
    Peruvian Heliconius butterfly species. The species are Mullerian mimics of one
    another, and both show the same changes in warning color pattern across their
    respective hybrid zones. The expectations of cline width and gametic correlation
    were generated using simulations of clines stabilized by strong frequency-dependent
    selection. In the hybrid zone in Heliconius erato, clines at three major color
    pattern loci were between 8.5 and 10.2 km wide, and the pairwise gametic correlations
    peaked at R &amp; 0.35. These measures suggest that s &amp; 0.23 per locus, and
    that σ &amp; 2.6 km. In erato, the shapes of the clines agreed with that expected
    on the basis of dominance. Heliconius melpomene has a nearly coincident hybrid
    zone. In this species, cline widths at four major color pattern loci varied between
    11.7 and 13.4 km. Pairwise gametic correlations peaked near R &amp; 1.00 for tightly
    linked genes, and at R &amp; 0.40 for unlinked genes, giving s &amp; 0.25 per
    locus and σ &amp; 3.7 km. In melpomene, cline shapes did not perfectly fit theoretical
    shapes based on dominance; this deviation might be explained by long-distance
    migration and/or strong epistasis. Compared with erato, sample sizes in melpomene
    are lower and the genetics of its color patterns are less well understood. In
    spite of these problems, selection and gene flow are clearly of the same order
    of magnitude in the two species. The relatively high per locus selection coefficients
    agree with ``major gene'' theories for the evolution of Mullerian mimicry, but
    the genetic architecture of the color patterns does not. These results show that
    the genetics and evolution of mimicry are still only sketchily understood.
acknowledgement: 'We thank the Natural Environmental Research Council, the Royal Society,
  the Nuffield Foundation, CONCYTEC, and Mrs. G. W. BORLASE for financial support,
  and the people of San Martin for their generous hospitality. We are very grateful
  to S. D. KNAPP, who helped by maintaining our sanity and rearing larvae. We are
  also grateful to an anonymous reviewer, A. W. PORTER, J. C. SCHNEIDER, M. TURELLI
  and C. E. WATSON for helpful comments on the manuscript. This paper was approved
  for publication as journal article no. 5-7255 of the Mississippi Agricultural and
  Forestry Experiment Station, Mississippi State University, project no. MIS-2 122. '
article_processing_charge: No
article_type: original
author:
- first_name: James
  full_name: Mallet, James
  last_name: Mallet
- 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: Gerado
  full_name: Lamas, Gerado
  last_name: Lamas
- first_name: José
  full_name: Santisteban, José
  last_name: Santisteban
- first_name: Manuel
  full_name: Muedas, Manuel
  last_name: Muedas
- first_name: Harriet
  full_name: Eeley, Harriet
  last_name: Eeley
citation:
  ama: Mallet J, Barton NH, Lamas G, Santisteban J, Muedas M, Eeley H. Estimates of
    selection and gene flow from measures of cline width and linkage disequilibrium
    in Heliconius hybrid zones. <i>Genetics</i>. 1990;124(4):921-936. doi:<a href="https://doi.org/10.1093/genetics/124.4.921">10.1093/genetics/124.4.921</a>
  apa: Mallet, J., Barton, N. H., Lamas, G., Santisteban, J., Muedas, M., &#38; Eeley,
    H. (1990). Estimates of selection and gene flow from measures of cline width and
    linkage disequilibrium in Heliconius hybrid zones. <i>Genetics</i>. Genetics Society
    of America. <a href="https://doi.org/10.1093/genetics/124.4.921">https://doi.org/10.1093/genetics/124.4.921</a>
  chicago: Mallet, James, Nicholas H Barton, Gerado Lamas, José Santisteban, Manuel
    Muedas, and Harriet Eeley. “Estimates of Selection and Gene Flow from Measures
    of Cline Width and Linkage Disequilibrium in Heliconius Hybrid Zones.” <i>Genetics</i>.
    Genetics Society of America, 1990. <a href="https://doi.org/10.1093/genetics/124.4.921">https://doi.org/10.1093/genetics/124.4.921</a>.
  ieee: J. Mallet, N. H. Barton, G. Lamas, J. Santisteban, M. Muedas, and H. Eeley,
    “Estimates of selection and gene flow from measures of cline width and linkage
    disequilibrium in Heliconius hybrid zones,” <i>Genetics</i>, vol. 124, no. 4.
    Genetics Society of America, pp. 921–936, 1990.
  ista: Mallet J, Barton NH, Lamas G, Santisteban J, Muedas M, Eeley H. 1990. Estimates
    of selection and gene flow from measures of cline width and linkage disequilibrium
    in Heliconius hybrid zones. Genetics. 124(4), 921–936.
  mla: Mallet, James, et al. “Estimates of Selection and Gene Flow from Measures of
    Cline Width and Linkage Disequilibrium in Heliconius Hybrid Zones.” <i>Genetics</i>,
    vol. 124, no. 4, Genetics Society of America, 1990, pp. 921–36, doi:<a href="https://doi.org/10.1093/genetics/124.4.921">10.1093/genetics/124.4.921</a>.
  short: J. Mallet, N.H. Barton, G. Lamas, J. Santisteban, M. Muedas, H. Eeley, Genetics
    124 (1990) 921–936.
date_created: 2018-12-11T12:04:26Z
date_published: 1990-04-01T00:00:00Z
date_updated: 2022-02-23T11:04:17Z
day: '01'
doi: 10.1093/genetics/124.4.921
extern: '1'
external_id:
  pmid:
  - '2323556'
intvolume: '       124'
issue: '4'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://www.ncbi.nlm.nih.gov/pmc/articles/PMC1203983/
month: '04'
oa: 1
oa_version: Published Version
page: 921 - 936
pmid: 1
publication: Genetics
publication_identifier:
  issn:
  - 0016-6731
publication_status: published
publisher: Genetics Society of America
publist_id: '2733'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Estimates of selection and gene flow from measures of cline width and linkage
  disequilibrium in Heliconius hybrid zones
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 124
year: '1990'
...
---
_id: '3651'
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.'
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.
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. 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>
  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>
  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.
  ista: Barton NH. 1990. Pleiotropic models of quantitative variation. Genetics. 124(3),
    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>.
  short: N.H. Barton, Genetics 124 (1990) 773–782.
date_created: 2018-12-11T12:04:26Z
date_published: 1990-03-01T00:00:00Z
date_updated: 2022-02-23T10:41:43Z
day: '01'
doi: '10.1093/genetics/124.3.773 '
extern: '1'
external_id:
  pmid:
  - '2311921'
intvolume: '       124'
issue: '3'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://academic.oup.com/genetics/article/124/3/773/5999956?login=true
month: '03'
oa: 1
oa_version: Published Version
page: 773 - 782
pmid: 1
publication: Genetics
publication_identifier:
  issn:
  - 0016-6731
publication_status: published
publisher: Genetics Society of America
publist_id: '2732'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Pleiotropic models of quantitative variation
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 124
year: '1990'
...
---
_id: '4060'
abstract:
- lang: eng
  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.
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.
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
- first_name: Douglas
  full_name: West, Douglas
  last_name: West
citation:
  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>
  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>
  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.
  ista: Edelsbrunner H, Preparata F, West D. 1990. Tetrahedrizing point sets in three
    dimensions. Journal of Symbolic Computation. 10(3–4), 335–347.
  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.
date_created: 2018-12-11T12:06:42Z
date_published: 1990-01-01T00:00:00Z
date_updated: 2022-02-23T10:10:35Z
day: '01'
doi: 10.1016/S0747-7171(08)80068-5
extern: '1'
intvolume: '        10'
issue: 3-4
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://www.sciencedirect.com/science/article/pii/S0747717108800685?via%3Dihub
month: '01'
oa: 1
oa_version: Published Version
page: 335 - 347
publication: Journal of Symbolic Computation
publication_identifier:
  eissn:
  - 1095-855X
  issn:
  - 0747-7171
publication_status: published
publisher: Elsevier
publist_id: '2061'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Tetrahedrizing point sets in three dimensions
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 10
year: '1990'
...
---
_id: '4063'
abstract:
- lang: eng
  text: This paper describes a general-purpose programming technique, called Simulation
    of Simplicity, that can be used to cope with degenerate input data for geometric
    algorithms. It relieves the programmer from the task of providing a consistent
    treatment for every single special case that can occur. The programs that use
    the technique tend to be considerably smaller and more robust than those that
    do not use it. We believe that this technique will become a standard tool in writing
    geometric software.
acknowledgement: 'Research of both authors was supported by Amoco Foundation Faculty
  Development grant CS 1-6-44862. It was partially carried out while both authors
  were with the Institutes for Information Processing at the Technical University
  of Graz, Austria. The first author also acknowledges support by the National Science
  Foundation under grant CCR-8714565. '
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: Ernst
  full_name: Mücke, Ernst
  last_name: Mücke
citation:
  ama: 'Edelsbrunner H, Mücke E. Simulation of simplicity: A technique to cope with
    degenerate cases in geometric algorithms. <i>ACM Transactions on Graphics</i>.
    1990;9(1):66-104. doi:<a href="https://doi.org/10.1145/77635.77639">10.1145/77635.77639</a>'
  apa: 'Edelsbrunner, H., &#38; Mücke, E. (1990). Simulation of simplicity: A technique
    to cope with degenerate cases in geometric algorithms. <i>ACM Transactions on
    Graphics</i>. ACM. <a href="https://doi.org/10.1145/77635.77639">https://doi.org/10.1145/77635.77639</a>'
  chicago: 'Edelsbrunner, Herbert, and Ernst Mücke. “Simulation of Simplicity: A Technique
    to Cope with Degenerate Cases in Geometric Algorithms.” <i>ACM Transactions on
    Graphics</i>. ACM, 1990. <a href="https://doi.org/10.1145/77635.77639">https://doi.org/10.1145/77635.77639</a>.'
  ieee: 'H. Edelsbrunner and E. Mücke, “Simulation of simplicity: A technique to cope
    with degenerate cases in geometric algorithms,” <i>ACM Transactions on Graphics</i>,
    vol. 9, no. 1. ACM, pp. 66–104, 1990.'
  ista: 'Edelsbrunner H, Mücke E. 1990. Simulation of simplicity: A technique to cope
    with degenerate cases in geometric algorithms. ACM Transactions on Graphics. 9(1),
    66–104.'
  mla: 'Edelsbrunner, Herbert, and Ernst Mücke. “Simulation of Simplicity: A Technique
    to Cope with Degenerate Cases in Geometric Algorithms.” <i>ACM Transactions on
    Graphics</i>, vol. 9, no. 1, ACM, 1990, pp. 66–104, doi:<a href="https://doi.org/10.1145/77635.77639">10.1145/77635.77639</a>.'
  short: H. Edelsbrunner, E. Mücke, ACM Transactions on Graphics 9 (1990) 66–104.
date_created: 2018-12-11T12:06:43Z
date_published: 1990-01-01T00:00:00Z
date_updated: 2022-02-22T14:58:39Z
day: '01'
doi: 10.1145/77635.77639
extern: '1'
intvolume: '         9'
issue: '1'
language:
- iso: eng
main_file_link:
- url: https://dl.acm.org/doi/10.1145/77635.77639
month: '01'
oa_version: None
page: 66 - 104
publication: ACM Transactions on Graphics
publication_identifier:
  eissn:
  - 1557-7368
  issn:
  - 0730-0301
publication_status: published
publisher: ACM
publist_id: '2058'
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Simulation of simplicity: A technique to cope with degenerate cases in geometric
  algorithms'
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 9
year: '1990'
...
---
_id: '4064'
abstract:
- lang: eng
  text: Given a set of data points pi = (xi, yi ) for 1 ≤ i ≤ n, the least median
    of squares regression line is a line y = ax + b for which the median of the squared
    residuals is a minimum over all choices of a and b. An algorithm is described
    that computes such a line in O(n 2) time and O(n) memory space, thus improving
    previous upper bounds on the problem. This algorithm is an application of a general
    method built on top of the topological sweep of line arrangements.
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: Diane
  full_name: Souvaine, Diane
  last_name: Souvaine
citation:
  ama: Edelsbrunner H, Souvaine D. Computing least median of squares regression lines
    and guided topological sweep. <i>Journal of the American Statistical Association</i>.
    1990;85(409):115-119. doi:<a href="https://doi.org/10.1080/01621459.1990.10475313">10.1080/01621459.1990.10475313</a>
  apa: Edelsbrunner, H., &#38; Souvaine, D. (1990). Computing least median of squares
    regression lines and guided topological sweep. <i>Journal of the American Statistical
    Association</i>. American Statistical Association. <a href="https://doi.org/10.1080/01621459.1990.10475313">https://doi.org/10.1080/01621459.1990.10475313</a>
  chicago: Edelsbrunner, Herbert, and Diane Souvaine. “Computing Least Median of Squares
    Regression Lines and Guided Topological Sweep.” <i>Journal of the American Statistical
    Association</i>. American Statistical Association, 1990. <a href="https://doi.org/10.1080/01621459.1990.10475313">https://doi.org/10.1080/01621459.1990.10475313</a>.
  ieee: H. Edelsbrunner and D. Souvaine, “Computing least median of squares regression
    lines and guided topological sweep,” <i>Journal of the American Statistical Association</i>,
    vol. 85, no. 409. American Statistical Association, pp. 115–119, 1990.
  ista: Edelsbrunner H, Souvaine D. 1990. Computing least median of squares regression
    lines and guided topological sweep. Journal of the American Statistical Association.
    85(409), 115–119.
  mla: Edelsbrunner, Herbert, and Diane Souvaine. “Computing Least Median of Squares
    Regression Lines and Guided Topological Sweep.” <i>Journal of the American Statistical
    Association</i>, vol. 85, no. 409, American Statistical Association, 1990, pp.
    115–19, doi:<a href="https://doi.org/10.1080/01621459.1990.10475313">10.1080/01621459.1990.10475313</a>.
  short: H. Edelsbrunner, D. Souvaine, Journal of the American Statistical Association
    85 (1990) 115–119.
date_created: 2018-12-11T12:06:43Z
date_published: 1990-01-01T00:00:00Z
date_updated: 2022-02-22T15:10:54Z
day: '01'
doi: 10.1080/01621459.1990.10475313
extern: '1'
intvolume: '        85'
issue: '409'
language:
- iso: eng
main_file_link:
- url: https://www.tandfonline.com/doi/abs/10.1080/01621459.1990.10475313
month: '01'
oa_version: None
page: 115 - 119
publication: Journal of the American Statistical Association
publication_identifier:
  eissn:
  - 1537-274X
  issn:
  - 0003-1291
publication_status: published
publisher: American Statistical Association
publist_id: '2059'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Computing least median of squares regression lines and guided topological sweep
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 85
year: '1990'
...
---
_id: '4065'
abstract:
- lang: eng
  text: We prove that given n⩾3 convex, compact, and pairwise disjoint sets in the
    plane, they may be covered with n non-overlapping convex polygons with a total
    of not more than 6n−9 sides, and with not more than 3n−6 distinct slopes. Furthermore,
    we construct sets that require 6n−9 sides and 3n−6 slopes for n⩾3. The upper bound
    on the number of slopes implies a new bound on a recently studied transversal
    problem.
acknowledgement: 'The first author acknowledges the support by Amoco Fnd. Fat. Dev.
  Comput. Sci. l-6-44862. Work on this paper by the second author was supported by
  a Shell Fellowship in Computer Science. The third author as supported by the office
  of Naval Research under grant NOOO14-86K-0416. '
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: Arch
  full_name: Robison, Arch
  last_name: Robison
- first_name: Xiao
  full_name: Shen, Xiao
  last_name: Shen
citation:
  ama: Edelsbrunner H, Robison A, Shen X. Covering convex sets with non-overlapping
    polygons. <i>Discrete Mathematics</i>. 1990;81(2):153-164. doi:<a href="https://doi.org/10.1016/0012-365X(90)90147-A">10.1016/0012-365X(90)90147-A</a>
  apa: Edelsbrunner, H., Robison, A., &#38; Shen, X. (1990). Covering convex sets
    with non-overlapping polygons. <i>Discrete Mathematics</i>. Elsevier. <a href="https://doi.org/10.1016/0012-365X(90)90147-A">https://doi.org/10.1016/0012-365X(90)90147-A</a>
  chicago: Edelsbrunner, Herbert, Arch Robison, and Xiao Shen. “Covering Convex Sets
    with Non-Overlapping Polygons.” <i>Discrete Mathematics</i>. Elsevier, 1990. <a
    href="https://doi.org/10.1016/0012-365X(90)90147-A">https://doi.org/10.1016/0012-365X(90)90147-A</a>.
  ieee: H. Edelsbrunner, A. Robison, and X. Shen, “Covering convex sets with non-overlapping
    polygons,” <i>Discrete Mathematics</i>, vol. 81, no. 2. Elsevier, pp. 153–164,
    1990.
  ista: Edelsbrunner H, Robison A, Shen X. 1990. Covering convex sets with non-overlapping
    polygons. Discrete Mathematics. 81(2), 153–164.
  mla: Edelsbrunner, Herbert, et al. “Covering Convex Sets with Non-Overlapping Polygons.”
    <i>Discrete Mathematics</i>, vol. 81, no. 2, Elsevier, 1990, pp. 153–64, doi:<a
    href="https://doi.org/10.1016/0012-365X(90)90147-A">10.1016/0012-365X(90)90147-A</a>.
  short: H. Edelsbrunner, A. Robison, X. Shen, Discrete Mathematics 81 (1990) 153–164.
date_created: 2018-12-11T12:06:44Z
date_published: 1990-04-15T00:00:00Z
date_updated: 2022-02-22T15:45:55Z
day: '15'
doi: 10.1016/0012-365X(90)90147-A
extern: '1'
intvolume: '        81'
issue: '2'
language:
- iso: eng
main_file_link:
- url: https://www.sciencedirect.com/science/article/pii/0012365X9090147A?via%3Dihub
month: '04'
oa_version: None
page: 153 - 164
publication: Discrete Mathematics
publication_identifier:
  eissn:
  - 1872-681X
  issn:
  - 0012-365X
publication_status: published
publisher: Elsevier
publist_id: '2060'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Covering convex sets with non-overlapping polygons
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 81
year: '1990'
...
---
_id: '4066'
abstract:
- lang: eng
  text: 'We consider several problems involving points and planes in three dimensions.
    Our main results are: (i) The maximum number of faces boundingm distinct cells
    in an arrangement ofn planes isO(m 2/3 n logn +n 2); we can calculatem such cells
    specified by a point in each, in worst-case timeO(m 2/3 n log3 n+n 2 logn). (ii)
    The maximum number of incidences betweenn planes andm vertices of their arrangement
    isO(m 2/3 n logn+n 2), but this number is onlyO(m 3/5– n 4/5+2 +m+n logm), for
    any&gt;0, for any collection of points no three of which are collinear. (iii)
    For an arbitrary collection ofm points, we can calculate the number of incidences
    between them andn planes by a randomized algorithm whose expected time complexity
    isO((m 3/4– n 3/4+3 +m) log2 n+n logn logm) for any&gt;0. (iv) Givenm points andn
    planes, we can find the plane lying immediately below each point in randomized
    expected timeO([m 3/4– n 3/4+3 +m] log2 n+n logn logm) for any&gt;0. (v) The maximum
    number of facets (i.e., (d–1)-dimensional faces) boundingm distinct cells in an
    arrangement ofn hyperplanes ind dimensions,d&gt;3, isO(m 2/3 n d/3 logn+n d–1).
    This is also an upper bound for the number of incidences betweenn hyperplanes
    ind dimensions andm vertices of their arrangement. The combinatorial bounds in
    (i) and (v) and the general bound in (ii) are almost tight.'
acknowledgement: "Supported by Amoco Fnd. Fac. Dev. Comput. Sci. 1-6-44862 and by
  NSF Grant CCR-8714565. Work on this paper by the first author has been supported
  by Amoco Fnd. Fac. Dev. Comput. Sci. I-6-44862 and by NSF Grant CCR-87t4565. Work
  by the third author has been supported by Office of Naval Research Grant N00014-87-K-0129,
  by National Science Foundation Grant DCR-82-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. An abstract of this\r\npaper
  has appeared in the Proceedings of the 13th International Mathematical Programming
  Symposium, Tokyo, 1988, p. 147"
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: Micha
  full_name: Sharir, Micha
  last_name: Sharir
citation:
  ama: Edelsbrunner H, Guibas L, Sharir M. The complexity of many cells in arrangements
    of planes and related problems. <i>Discrete &#38; Computational Geometry</i>.
    1990;5(1):197-216. doi:<a href="https://doi.org/10.1007/BF02187785">10.1007/BF02187785</a>
  apa: Edelsbrunner, H., Guibas, L., &#38; Sharir, M. (1990). The complexity of many
    cells in arrangements of planes and related problems. <i>Discrete &#38; Computational
    Geometry</i>. Springer. <a href="https://doi.org/10.1007/BF02187785">https://doi.org/10.1007/BF02187785</a>
  chicago: Edelsbrunner, Herbert, Leonidas Guibas, and Micha Sharir. “The Complexity
    of Many Cells in Arrangements of Planes and Related Problems.” <i>Discrete &#38;
    Computational Geometry</i>. Springer, 1990. <a href="https://doi.org/10.1007/BF02187785">https://doi.org/10.1007/BF02187785</a>.
  ieee: H. Edelsbrunner, L. Guibas, and M. Sharir, “The complexity of many cells in
    arrangements of planes and related problems,” <i>Discrete &#38; Computational
    Geometry</i>, vol. 5, no. 1. Springer, pp. 197–216, 1990.
  ista: Edelsbrunner H, Guibas L, Sharir M. 1990. The complexity of many cells in
    arrangements of planes and related problems. Discrete &#38; Computational Geometry.
    5(1), 197–216.
  mla: Edelsbrunner, Herbert, et al. “The Complexity of Many Cells in Arrangements
    of Planes and Related Problems.” <i>Discrete &#38; Computational Geometry</i>,
    vol. 5, no. 1, Springer, 1990, pp. 197–216, doi:<a href="https://doi.org/10.1007/BF02187785">10.1007/BF02187785</a>.
  short: H. Edelsbrunner, L. Guibas, M. Sharir, Discrete &#38; Computational Geometry
    5 (1990) 197–216.
date_created: 2018-12-11T12:06:44Z
date_published: 1990-03-01T00:00:00Z
date_updated: 2022-02-22T11:02:41Z
day: '01'
doi: 10.1007/BF02187785
extern: '1'
intvolume: '         5'
issue: '1'
language:
- iso: eng
main_file_link:
- url: https://link.springer.com/article/10.1007/BF02187785
month: '03'
oa_version: None
page: 197 - 216
publication: Discrete & Computational Geometry
publication_identifier:
  eissn:
  - 1432-0444
  issn:
  - 0179-5376
publication_status: published
publisher: Springer
publist_id: '2054'
quality_controlled: '1'
scopus_import: '1'
status: public
title: The complexity of many cells in arrangements of planes and related problems
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 5
year: '1990'
...
---
_id: '4067'
abstract:
- lang: eng
  text: This paper proves an O(m 2/3 n 2/3+m+n) upper bound on the number of incidences
    between m points and n hyperplanes in four dimensions, assuming all points lie
    on one side of each hyperplane and the points and hyperplanes satisfy certain
    natural general position conditions. This result has application to various three-dimensional
    combinatorial distance problems. For example, it implies the same upper bound
    for the number of bichromatic minimum distance pairs in a set of m blue and n
    red points in three-dimensional space. This improves the best previous bound for
    this problem.
acknowledgement: Research of the first author was supported by the National Science
  Foundation under grant CCR-8714565. Work of the second author was supported by Office
  of Naval Research Grants DCR-83-20085 and CCR-89-01484, and by grants from the U.S.-Israeli
  Binational Science Foundation, the NCRD — the Israeli National Council for Research
  and Development, and the Fund for Basic Research in Electronics, Computers and Communication
  administered by the Israeli Academy of Sciences.
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Herbert
  full_name: Edelsbrunner, Herbert
  id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
  last_name: Edelsbrunner
  orcid: 0000-0002-9823-6833
- first_name: Micha
  full_name: Sharir, Micha
  last_name: Sharir
citation:
  ama: 'Edelsbrunner H, Sharir M. A hyperplane Incidence problem with applications
    to counting distances. In: <i>Proceedings of the International Symposium on Algorithms</i>.
    Vol 450. Springer; 1990:419-428. doi:<a href="https://doi.org/10.1007/3-540-52921-7_91">10.1007/3-540-52921-7_91</a>'
  apa: 'Edelsbrunner, H., &#38; Sharir, M. (1990). A hyperplane Incidence problem
    with applications to counting distances. In <i>Proceedings of the International
    Symposium on Algorithms</i> (Vol. 450, pp. 419–428). Tokyo, Japan: Springer. <a
    href="https://doi.org/10.1007/3-540-52921-7_91">https://doi.org/10.1007/3-540-52921-7_91</a>'
  chicago: Edelsbrunner, Herbert, and Micha Sharir. “A Hyperplane Incidence Problem
    with Applications to Counting Distances.” In <i>Proceedings of the International
    Symposium on Algorithms</i>, 450:419–28. Springer, 1990. <a href="https://doi.org/10.1007/3-540-52921-7_91">https://doi.org/10.1007/3-540-52921-7_91</a>.
  ieee: H. Edelsbrunner and M. Sharir, “A hyperplane Incidence problem with applications
    to counting distances,” in <i>Proceedings of the International Symposium on Algorithms</i>,
    Tokyo, Japan, 1990, vol. 450, pp. 419–428.
  ista: Edelsbrunner H, Sharir M. 1990. A hyperplane Incidence problem with applications
    to counting distances. Proceedings of the International Symposium on Algorithms.
    SIGAL:  Special Interest Group on Algorithms, International Symposium on Algorithms 
    , LNCS, vol. 450, 419–428.
  mla: Edelsbrunner, Herbert, and Micha Sharir. “A Hyperplane Incidence Problem with
    Applications to Counting Distances.” <i>Proceedings of the International Symposium
    on Algorithms</i>, vol. 450, Springer, 1990, pp. 419–28, doi:<a href="https://doi.org/10.1007/3-540-52921-7_91">10.1007/3-540-52921-7_91</a>.
  short: H. Edelsbrunner, M. Sharir, in:, Proceedings of the International Symposium
    on Algorithms, Springer, 1990, pp. 419–428.
conference:
  end_date: 1990-08-18
  location: Tokyo, Japan
  name: 'SIGAL:  Special Interest Group on Algorithms, International Symposium on
    Algorithms  '
  start_date: 1990-08-16
date_created: 2018-12-11T12:06:45Z
date_published: 1990-01-01T00:00:00Z
date_updated: 2022-02-22T14:31:26Z
day: '01'
doi: 10.1007/3-540-52921-7_91
extern: '1'
intvolume: '       450'
language:
- iso: eng
main_file_link:
- url: https://link.springer.com/chapter/10.1007/3-540-52921-7_91
month: '01'
oa_version: None
page: 419 - 428
publication: Proceedings of the International Symposium on Algorithms
publication_identifier:
  isbn:
  - 978-3-540-52921-7
publication_status: published
publisher: Springer
publist_id: '2056'
quality_controlled: '1'
scopus_import: '1'
status: public
title: A hyperplane Incidence problem with applications to counting distances
type: conference
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 450
year: '1990'
...
---
_id: '4068'
abstract:
- lang: eng
  text: "LetS be a collection ofn convex, closed, and pairwise nonintersecting sets
    in the Euclidean plane labeled from 1 ton. A pair of permutations\r\n(i1i2in−1in)(inin−1i2i1)
    \r\nis called ageometric permutation of S if there is a line that intersects all
    sets ofS in this order. We prove thatS can realize at most 2n–2 geometric permutations.
    This upper bound is tight."
acknowledgement: Research of the first author was supported by Amoco Foundation for
  Faculty Development in Computer Science Grant No. 1-6-44862. Work on this paper
  by the second author was supported by Office of Naval Research Grant No. N00014-82-K-0381,
  National Science Foundation Grant No. NSF-DCR-83-20085, and by grants from the Digital
  Equipment Corporation and the IBM Corporation.
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: Micha
  full_name: Sharir, Micha
  last_name: Sharir
citation:
  ama: Edelsbrunner H, Sharir M. The maximum number of ways to stabn convex nonintersecting
    sets in the plane is 2n−2. <i>Discrete &#38; Computational Geometry</i>. 1990;5(1):35-42.
    doi:<a href="https://doi.org/10.1007/BF02187778">10.1007/BF02187778</a>
  apa: Edelsbrunner, H., &#38; Sharir, M. (1990). The maximum number of ways to stabn
    convex nonintersecting sets in the plane is 2n−2. <i>Discrete &#38; Computational
    Geometry</i>. Springer. <a href="https://doi.org/10.1007/BF02187778">https://doi.org/10.1007/BF02187778</a>
  chicago: Edelsbrunner, Herbert, and Micha Sharir. “The Maximum Number of Ways to
    Stabn Convex Nonintersecting Sets in the Plane Is 2n−2.” <i>Discrete &#38; Computational
    Geometry</i>. Springer, 1990. <a href="https://doi.org/10.1007/BF02187778">https://doi.org/10.1007/BF02187778</a>.
  ieee: H. Edelsbrunner and M. Sharir, “The maximum number of ways to stabn convex
    nonintersecting sets in the plane is 2n−2,” <i>Discrete &#38; Computational Geometry</i>,
    vol. 5, no. 1. Springer, pp. 35–42, 1990.
  ista: Edelsbrunner H, Sharir M. 1990. The maximum number of ways to stabn convex
    nonintersecting sets in the plane is 2n−2. Discrete &#38; Computational Geometry.
    5(1), 35–42.
  mla: Edelsbrunner, Herbert, and Micha Sharir. “The Maximum Number of Ways to Stabn
    Convex Nonintersecting Sets in the Plane Is 2n−2.” <i>Discrete &#38; Computational
    Geometry</i>, vol. 5, no. 1, Springer, 1990, pp. 35–42, doi:<a href="https://doi.org/10.1007/BF02187778">10.1007/BF02187778</a>.
  short: H. Edelsbrunner, M. Sharir, Discrete &#38; Computational Geometry 5 (1990)
    35–42.
date_created: 2018-12-11T12:06:45Z
date_published: 1990-01-01T00:00:00Z
date_updated: 2022-02-22T14:50:34Z
day: '01'
doi: 10.1007/BF02187778
extern: '1'
intvolume: '         5'
issue: '1'
language:
- iso: eng
main_file_link:
- url: https://link.springer.com/article/10.1007/BF02187778
month: '01'
oa_version: None
page: 35 - 42
publication: Discrete & Computational Geometry
publication_identifier:
  eissn:
  - 1432-0444
  issn:
  - 0179-5376
publication_status: published
publisher: Springer
publist_id: '2057'
quality_controlled: '1'
status: public
title: The maximum number of ways to stabn convex nonintersecting sets in the plane
  is 2n−2
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 5
year: '1990'
...
---
_id: '4069'
abstract:
- lang: eng
  text: Let C be a cell complex in d-dimensional Euclidean space whose faces are obtained
    by orthogonal projection of the faces of a convex polytope in d + 1 dimensions.
    For example, the Delaunay triangulation of a finite point set is such a cell complex.
    This paper shows that the in front/behind relation defined for the faces of C
    with respect to any fixed viewpoint x is acyclic. This result has applications
    to hidden line/surface removal and other problems in computational geometry.
acknowledgement: Research reported in this paper was supported by the National Science
  Foundation under grant CCR-8714565.
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. An acyclicity theorem for cell complexes in d dimension. <i>Combinatorica</i>.
    1990;10(3):251-260. doi:<a href="https://doi.org/10.1007/BF02122779">10.1007/BF02122779</a>
  apa: Edelsbrunner, H. (1990). An acyclicity theorem for cell complexes in d dimension.
    <i>Combinatorica</i>. Springer. <a href="https://doi.org/10.1007/BF02122779">https://doi.org/10.1007/BF02122779</a>
  chicago: Edelsbrunner, Herbert. “An Acyclicity Theorem for Cell Complexes in d Dimension.”
    <i>Combinatorica</i>. Springer, 1990. <a href="https://doi.org/10.1007/BF02122779">https://doi.org/10.1007/BF02122779</a>.
  ieee: H. Edelsbrunner, “An acyclicity theorem for cell complexes in d dimension,”
    <i>Combinatorica</i>, vol. 10, no. 3. Springer, pp. 251–260, 1990.
  ista: Edelsbrunner H. 1990. An acyclicity theorem for cell complexes in d dimension.
    Combinatorica. 10(3), 251–260.
  mla: Edelsbrunner, Herbert. “An Acyclicity Theorem for Cell Complexes in d Dimension.”
    <i>Combinatorica</i>, vol. 10, no. 3, Springer, 1990, pp. 251–60, doi:<a href="https://doi.org/10.1007/BF02122779">10.1007/BF02122779</a>.
  short: H. Edelsbrunner, Combinatorica 10 (1990) 251–260.
date_created: 2018-12-11T12:06:45Z
date_published: 1990-09-01T00:00:00Z
date_updated: 2022-02-21T11:08:30Z
day: '01'
doi: 10.1007/BF02122779
extern: '1'
intvolume: '        10'
issue: '3'
language:
- iso: eng
main_file_link:
- url: https://link.springer.com/article/10.1007/BF02122779
month: '09'
oa_version: None
page: 251 - 260
publication: Combinatorica
publication_identifier:
  eissn:
  - 1439-6912
  issn:
  - 0209-9683
publication_status: published
publisher: Springer
publist_id: '2050'
quality_controlled: '1'
scopus_import: '1'
status: public
title: An acyclicity theorem for cell complexes in d dimension
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 10
year: '1990'
...
---
_id: '4070'
abstract:
- lang: eng
  text: Let S be a set of n closed intervals on the x-axis. A ranking assigns to each
    interval, s, a distinct rank, p(s)∊ [1, 2,…,n]. We say that s can see t if p(s)<p(t)
    and there is a point p∊s∩t so that p∉u for all u with p(s)<p(u)<p(t). It is shown
    that a ranking can be found in time O(n log n) such that each interval sees at
    most three other intervals. It is also shown that a ranking that minimizes the
    average number of endpoints visible from an interval can be computed in time O(n
    5/2). The results have applications to intersection problems for intervals, as
    well as to channel routing problems which arise in layouts of VLSI circuits.
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: Mark
  full_name: Overmars, Mark
  last_name: Overmars
- first_name: Emo
  full_name: Welzl, Emo
  last_name: Welzl
- first_name: Irith
  full_name: Hartman, Irith
  last_name: Hartman
- first_name: Jack
  full_name: Feldman, Jack
  last_name: Feldman
citation:
  ama: Edelsbrunner H, Overmars M, Welzl E, Hartman I, Feldman J. Ranking intervals
    under visibility constraints. <i>International Journal of Computer Mathematics</i>.
    1990;34(3-4):129-144. doi:<a href="https://doi.org/10.1080/00207169008803871">10.1080/00207169008803871</a>
  apa: Edelsbrunner, H., Overmars, M., Welzl, E., Hartman, I., &#38; Feldman, J. (1990).
    Ranking intervals under visibility constraints. <i>International Journal of Computer
    Mathematics</i>. Taylor &#38; Francis. <a href="https://doi.org/10.1080/00207169008803871">https://doi.org/10.1080/00207169008803871</a>
  chicago: Edelsbrunner, Herbert, Mark Overmars, Emo Welzl, Irith Hartman, and Jack
    Feldman. “Ranking Intervals under Visibility Constraints.” <i>International Journal
    of Computer Mathematics</i>. Taylor &#38; Francis, 1990. <a href="https://doi.org/10.1080/00207169008803871">https://doi.org/10.1080/00207169008803871</a>.
  ieee: H. Edelsbrunner, M. Overmars, E. Welzl, I. Hartman, and J. Feldman, “Ranking
    intervals under visibility constraints,” <i>International Journal of Computer
    Mathematics</i>, vol. 34, no. 3–4. Taylor &#38; Francis, pp. 129–144, 1990.
  ista: Edelsbrunner H, Overmars M, Welzl E, Hartman I, Feldman J. 1990. Ranking intervals
    under visibility constraints. International Journal of Computer Mathematics. 34(3–4),
    129–144.
  mla: Edelsbrunner, Herbert, et al. “Ranking Intervals under Visibility Constraints.”
    <i>International Journal of Computer Mathematics</i>, vol. 34, no. 3–4, Taylor
    &#38; Francis, 1990, pp. 129–44, doi:<a href="https://doi.org/10.1080/00207169008803871">10.1080/00207169008803871</a>.
  short: H. Edelsbrunner, M. Overmars, E. Welzl, I. Hartman, J. Feldman, International
    Journal of Computer Mathematics 34 (1990) 129–144.
date_created: 2018-12-11T12:06:46Z
date_published: 1990-01-01T00:00:00Z
date_updated: 2022-02-21T13:19:52Z
day: '01'
doi: 10.1080/00207169008803871
extern: '1'
intvolume: '        34'
issue: 3-4
language:
- iso: eng
main_file_link:
- url: https://www.tandfonline.com/doi/abs/10.1080/00207169008803871
month: '01'
oa_version: None
page: 129 - 144
publication: International Journal of Computer Mathematics
publication_identifier:
  eissn:
  - 1029-0265
  issn:
  - 0020-7160
publication_status: published
publisher: Taylor & Francis
publist_id: '2051'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Ranking intervals under visibility constraints
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 34
year: '1990'
...
---
_id: '4071'
abstract:
- lang: eng
  text: We show that a triangulation of a set of n points in the plane that minimizes
    the maximum angle can be computed in time O(n2 log n) and space O(n). In the same
    amount of time and space we can also handle the constrained case where edges are
    prescribed. The algorithm iteratively improves an arbitrary initial triangulation
    and is fairly easy to implement.
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: Tiow
  full_name: Tan, Tiow
  last_name: Tan
- first_name: Roman
  full_name: Waupotitsch, Roman
  last_name: Waupotitsch
citation:
  ama: 'Edelsbrunner H, Tan T, Waupotitsch R. An O(n^2log n) time algorithm for the
    MinMax angle triangulation. In: <i>Proceedings of the 6th Annual Symposium on
    Computational Geometry</i>. ACM; 1990:44-52. doi:<a href="https://doi.org/10.1145/98524.98535">10.1145/98524.98535</a>'
  apa: 'Edelsbrunner, H., Tan, T., &#38; Waupotitsch, R. (1990). An O(n^2log n) time
    algorithm for the MinMax angle triangulation. In <i>Proceedings of the 6th annual
    symposium on Computational geometry</i> (pp. 44–52). Berkley, CA, United States:
    ACM. <a href="https://doi.org/10.1145/98524.98535">https://doi.org/10.1145/98524.98535</a>'
  chicago: Edelsbrunner, Herbert, Tiow Tan, and Roman Waupotitsch. “An O(N^2log n)
    Time Algorithm for the MinMax Angle Triangulation.” In <i>Proceedings of the 6th
    Annual Symposium on Computational Geometry</i>, 44–52. ACM, 1990. <a href="https://doi.org/10.1145/98524.98535">https://doi.org/10.1145/98524.98535</a>.
  ieee: H. Edelsbrunner, T. Tan, and R. Waupotitsch, “An O(n^2log n) time algorithm
    for the MinMax angle triangulation,” in <i>Proceedings of the 6th annual symposium
    on Computational geometry</i>, Berkley, CA, United States, 1990, pp. 44–52.
  ista: 'Edelsbrunner H, Tan T, Waupotitsch R. 1990. An O(n^2log n) time algorithm
    for the MinMax angle triangulation. Proceedings of the 6th annual symposium on
    Computational geometry. SCG: Symposium on Computational Geometry, 44–52.'
  mla: Edelsbrunner, Herbert, et al. “An O(N^2log n) Time Algorithm for the MinMax
    Angle Triangulation.” <i>Proceedings of the 6th Annual Symposium on Computational
    Geometry</i>, ACM, 1990, pp. 44–52, doi:<a href="https://doi.org/10.1145/98524.98535">10.1145/98524.98535</a>.
  short: H. Edelsbrunner, T. Tan, R. Waupotitsch, in:, Proceedings of the 6th Annual
    Symposium on Computational Geometry, ACM, 1990, pp. 44–52.
conference:
  end_date: 1990-06-09
  location: Berkley, CA, United States
  name: 'SCG: Symposium on Computational Geometry'
  start_date: 1990-06-07
date_created: 2018-12-11T12:06:46Z
date_published: 1990-01-01T00:00:00Z
date_updated: 2022-02-22T08:56:42Z
day: '01'
doi: 10.1145/98524.98535
extern: '1'
language:
- iso: eng
main_file_link:
- url: https://dl.acm.org/doi/10.1145/98524.98535
month: '01'
oa_version: None
page: 44 - 52
publication: Proceedings of the 6th annual symposium on Computational geometry
publication_identifier:
  isbn:
  - 978-0-89791-362-1
publication_status: published
publisher: ACM
publist_id: '2052'
quality_controlled: '1'
status: public
title: An O(n^2log n) time algorithm for the MinMax angle triangulation
type: conference
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
year: '1990'
...
---
_id: '4072'
abstract:
- lang: eng
  text: We show that the total number of edges ofm faces of an arrangement ofn lines
    in the plane isO(m 2/3– n 2/3+2 +n) for any&gt;0. The proof takes an algorithmic
    approach, that is, we describe an algorithm for the calculation of thesem faces
    and derive the upper bound from the analysis of the algorithm. The algorithm uses
    randomization and its expected time complexity isO(m 2/3– n 2/3+2 logn+n logn
    logm). If instead of lines we have an arrangement ofn line segments, then the
    maximum number of edges ofm faces isO(m 2/3– n 2/3+2 +n (n) logm) for any&gt;0,
    where(n) is the functional inverse of Ackermann's function. We give a (randomized)
    algorithm that produces these faces and takes expected timeO(m 2/3– n 2/3+2 log+n(n)
    log2 n logm).
acknowledgement: The first author is pleased to acknowledge partial support by the
  Amoco Fnd. Fac. Dev. Comput. Sci. 1-6-44862 and the National Science Foundation
  under Grant CCR-8714565. Work on this paper by the third author has been supported
  by Office of Naval Research Grant N00014-82-K-0381, by National Science Foundation
  Grant 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. A preliminary version of this paper has appeared in
  theProceedings of the 4th ACM Symposium on Computational Geometry, 1988, pp. 44–55.
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: Micha
  full_name: Sharir, Micha
  last_name: Sharir
citation:
  ama: Edelsbrunner H, Guibas L, Sharir M. The complexity and construction of many
    faces in arrangements of lines and of segments. <i>Discrete &#38; Computational
    Geometry</i>. 1990;5(1):161-196. doi:<a href="https://doi.org/10.1007/BF02187784">10.1007/BF02187784</a>
  apa: Edelsbrunner, H., Guibas, L., &#38; Sharir, M. (1990). The complexity and construction
    of many faces in arrangements of lines and of segments. <i>Discrete &#38; Computational
    Geometry</i>. Springer. <a href="https://doi.org/10.1007/BF02187784">https://doi.org/10.1007/BF02187784</a>
  chicago: Edelsbrunner, Herbert, Leonidas Guibas, and Micha Sharir. “The Complexity
    and Construction of Many Faces in Arrangements of Lines and of Segments.” <i>Discrete
    &#38; Computational Geometry</i>. Springer, 1990. <a href="https://doi.org/10.1007/BF02187784">https://doi.org/10.1007/BF02187784</a>.
  ieee: H. Edelsbrunner, L. Guibas, and M. Sharir, “The complexity and construction
    of many faces in arrangements of lines and of segments,” <i>Discrete &#38; Computational
    Geometry</i>, vol. 5, no. 1. Springer, pp. 161–196, 1990.
  ista: Edelsbrunner H, Guibas L, Sharir M. 1990. The complexity and construction
    of many faces in arrangements of lines and of segments. Discrete &#38; Computational
    Geometry. 5(1), 161–196.
  mla: Edelsbrunner, Herbert, et al. “The Complexity and Construction of Many Faces
    in Arrangements of Lines and of Segments.” <i>Discrete &#38; Computational Geometry</i>,
    vol. 5, no. 1, Springer, 1990, pp. 161–96, doi:<a href="https://doi.org/10.1007/BF02187784">10.1007/BF02187784</a>.
  short: H. Edelsbrunner, L. Guibas, M. Sharir, Discrete &#38; Computational Geometry
    5 (1990) 161–196.
date_created: 2018-12-11T12:06:46Z
date_published: 1990-01-01T00:00:00Z
date_updated: 2022-02-22T09:27:30Z
day: '01'
doi: 10.1007/BF02187784
extern: '1'
intvolume: '         5'
issue: '1'
language:
- iso: eng
main_file_link:
- url: https://link.springer.com/article/10.1007/BF02187784
month: '01'
oa_version: None
page: 161 - 196
publication: Discrete & Computational Geometry
publication_identifier:
  eissn:
  - 1432-0444
  issn:
  - 0179-5376
publication_status: published
publisher: Springer
publist_id: '2053'
quality_controlled: '1'
scopus_import: '1'
status: public
title: The complexity and construction of many faces in arrangements of lines and
  of segments
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 5
year: '1990'
...
---
_id: '4073'
abstract:
- lang: eng
  text: A number of rendering algorithms in computer graphics sort three-dimensional
    objects by depth and assume that there is no cycle that makes the sorting impossible.
    One way to resolve the problem caused by cycles is to cut the objects into smaller
    pieces. The problem of estimating how many such cuts are always sufficient is
    addressed. A few related algorithmic and combinatorial geometry problems are considered.
article_processing_charge: No
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
- first_name: Leonidas
  full_name: Guibas, Leonidas
  last_name: Guibas
- 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: 'Chazelle B, Edelsbrunner H, Guibas L, et al. Counting and cutting cycles of
    lines and rods in space. In: <i>31st Annual Symposium on Foundations of Computer
    Science</i>. IEEE; 1990:242-251. doi:<a href="https://doi.org/10.1109/FSCS.1990.89543">10.1109/FSCS.1990.89543</a>'
  apa: 'Chazelle, B., Edelsbrunner, H., Guibas, L., Pollack, R., Seidel, R., Sharir,
    M., &#38; Snoeyink, J. (1990). Counting and cutting cycles of lines and rods in
    space. In <i>31st Annual Symposium on Foundations of Computer Science</i> (pp.
    242–251). St. Louis, MO, United States of America: IEEE. <a href="https://doi.org/10.1109/FSCS.1990.89543">https://doi.org/10.1109/FSCS.1990.89543</a>'
  chicago: Chazelle, Bernard, Herbert Edelsbrunner, Leonidas Guibas, Richard Pollack,
    Raimund Seidel, Micha Sharir, and Jack Snoeyink. “Counting and Cutting Cycles
    of Lines and Rods in Space.” In <i>31st Annual Symposium on Foundations of Computer
    Science</i>, 242–51. IEEE, 1990. <a href="https://doi.org/10.1109/FSCS.1990.89543">https://doi.org/10.1109/FSCS.1990.89543</a>.
  ieee: B. Chazelle <i>et al.</i>, “Counting and cutting cycles of lines and rods
    in space,” in <i>31st Annual Symposium on Foundations of Computer Science</i>,
    St. Louis, MO, United States of America, 1990, pp. 242–251.
  ista: 'Chazelle B, Edelsbrunner H, Guibas L, Pollack R, Seidel R, Sharir M, Snoeyink
    J. 1990. Counting and cutting cycles of lines and rods in space. 31st Annual Symposium
    on Foundations of Computer Science. FOCS: Foundations of Computer Science, 242–251.'
  mla: Chazelle, Bernard, et al. “Counting and Cutting Cycles of Lines and Rods in
    Space.” <i>31st Annual Symposium on Foundations of Computer Science</i>, IEEE,
    1990, pp. 242–51, doi:<a href="https://doi.org/10.1109/FSCS.1990.89543">10.1109/FSCS.1990.89543</a>.
  short: B. Chazelle, H. Edelsbrunner, L. Guibas, R. Pollack, R. Seidel, M. Sharir,
    J. Snoeyink, in:, 31st Annual Symposium on Foundations of Computer Science, IEEE,
    1990, pp. 242–251.
conference:
  end_date: 1990-10-24
  location: St. Louis, MO, United States of America
  name: 'FOCS: Foundations of Computer Science'
  start_date: 1990-10-22
date_created: 2018-12-11T12:06:47Z
date_published: 1990-01-01T00:00:00Z
date_updated: 2022-02-17T11:07:07Z
day: '01'
doi: 10.1109/FSCS.1990.89543
extern: '1'
language:
- iso: eng
main_file_link:
- url: https://ieeexplore.ieee.org/document/89543
month: '01'
oa_version: None
page: 242 - 251
publication: 31st Annual Symposium on Foundations of Computer Science
publication_identifier:
  isbn:
  - 0-8186-2082-X
publication_status: published
publisher: IEEE
publist_id: '2047'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Counting and cutting cycles of lines and rods in space
type: conference
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
year: '1990'
...
---
_id: '4074'
abstract:
- lang: eng
  text: We present upper and lower bounds for extremal problems defined for arrangements
    of lines, circles, spheres, and alike. For example, we prove that the maximum
    number of edges boundingm cells in an arrangement ofn lines is Θ(m 2/3 n 2/3 +n),
    and that it isO(m 2/3 n 2/3 β(n) +n) forn unit-circles, whereβ(n) (and laterβ(m,
    n)) is a function that depends on the inverse of Ackermann's function and grows
    extremely slowly. If we replace unit-circles by circles of arbitrary radii the
    upper bound goes up toO(m 3/5 n 4/5 β(n) +n). The same bounds (without theβ(n)-terms)
    hold for the maximum sum of degrees ofm vertices. In the case of vertex degrees
    in arrangements of lines and of unit-circles our bounds match previous results,
    but our proofs are considerably simpler than the previous ones. The maximum sum
    of degrees ofm vertices in an arrangement ofn spheres in three dimensions isO(m
    4/7 n 9/7 β(m, n) +n 2), in general, andO(m 3/4 n 3/4 β(m, n) +n) if no three
    spheres intersect in a common circle. The latter bound implies that the maximum
    number of unit-distances amongm points in three dimensions isO(m 3/2 β(m)) which
    improves the best previous upper bound on this problem. Applications of our results
    to other distance problems are also given.
acknowledgement: The research of the second author was supported by the National Science
  Foundation under Grant CCR-8714565. Work by the fourth author has been supported
  by Office of Naval Research Grant N00014-87-K-0129, by 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 the NCRD, the Israeli National
  Council for Research and Development. A preliminary version of this paper has appeared
  in theProceedings of the 29th IEEE Symposium on Foundations of Computer Science,
  1988.
article_processing_charge: No
article_type: original
author:
- first_name: Kenneth
  full_name: Clarkson, Kenneth
  last_name: Clarkson
- 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: Micha
  full_name: Sharir, Micha
  last_name: Sharir
- first_name: Emo
  full_name: Welzl, Emo
  last_name: Welzl
citation:
  ama: Clarkson K, Edelsbrunner H, Guibas L, Sharir M, Welzl E. Combinatorial complexity
    bounds for arrangements of curves and spheres. <i>Discrete &#38; Computational
    Geometry</i>. 1990;5(1):99-160. doi:<a href="https://doi.org/10.1007/BF02187783">10.1007/BF02187783</a>
  apa: Clarkson, K., Edelsbrunner, H., Guibas, L., Sharir, M., &#38; Welzl, E. (1990).
    Combinatorial complexity bounds for arrangements of curves and spheres. <i>Discrete
    &#38; Computational Geometry</i>. Springer. <a href="https://doi.org/10.1007/BF02187783">https://doi.org/10.1007/BF02187783</a>
  chicago: Clarkson, Kenneth, Herbert Edelsbrunner, Leonidas Guibas, Micha Sharir,
    and Emo Welzl. “Combinatorial Complexity Bounds for Arrangements of Curves and
    Spheres.” <i>Discrete &#38; Computational Geometry</i>. Springer, 1990. <a href="https://doi.org/10.1007/BF02187783">https://doi.org/10.1007/BF02187783</a>.
  ieee: K. Clarkson, H. Edelsbrunner, L. Guibas, M. Sharir, and E. Welzl, “Combinatorial
    complexity bounds for arrangements of curves and spheres,” <i>Discrete &#38; Computational
    Geometry</i>, vol. 5, no. 1. Springer, pp. 99–160, 1990.
  ista: Clarkson K, Edelsbrunner H, Guibas L, Sharir M, Welzl E. 1990. Combinatorial
    complexity bounds for arrangements of curves and spheres. Discrete &#38; Computational
    Geometry. 5(1), 99–160.
  mla: Clarkson, Kenneth, et al. “Combinatorial Complexity Bounds for Arrangements
    of Curves and Spheres.” <i>Discrete &#38; Computational Geometry</i>, vol. 5,
    no. 1, Springer, 1990, pp. 99–160, doi:<a href="https://doi.org/10.1007/BF02187783">10.1007/BF02187783</a>.
  short: K. Clarkson, H. Edelsbrunner, L. Guibas, M. Sharir, E. Welzl, Discrete &#38;
    Computational Geometry 5 (1990) 99–160.
date_created: 2018-12-11T12:06:47Z
date_published: 1990-03-01T00:00:00Z
date_updated: 2022-02-17T15:41:04Z
day: '01'
doi: 10.1007/BF02187783
extern: '1'
intvolume: '         5'
issue: '1'
language:
- iso: eng
main_file_link:
- url: https://link.springer.com/article/10.1007/BF02187783
month: '03'
oa_version: None
page: 99 - 160
publication: Discrete & Computational Geometry
publication_identifier:
  eissn:
  - 1432-0444
  issn:
  - 0179-5376
publication_status: published
publisher: Springer
publist_id: '2048'
quality_controlled: '1'
status: public
title: Combinatorial complexity bounds for arrangements of curves and spheres
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 5
year: '1990'
...
---
_id: '4075'
abstract:
- lang: eng
  text: A key problem in computational geometry is the identification of subsets of
    a point set having particular properties. We study this problem for the properties
    of convexity and emptiness. We show that finding empty triangles is related to
    the problem of determining pairs of vertices that see each other in a star-shaped
    polygon. A linear-time algorithm for this problem which is of independent interest
    yields an optimal algorithm for finding all empty triangles. This result is then
    extended to an algorithm for finding empty convex r-gons (r&gt; 3) and for determining
    a largest empty convex subset. Finally, extensions to higher dimensions are mentioned.
acknowledgement: The first author is pleased to acknowledge support by the National
  Science Foundation under Grant CCR-8700917. The research of the second author was
  supported by Amoco Foundation Faculty Development Grant CS 1-6-44862 and by the
  National Science Foundatio
article_processing_charge: No
article_type: original
author:
- first_name: David
  full_name: Dobkin, David
  last_name: Dobkin
- first_name: Herbert
  full_name: Edelsbrunner, Herbert
  id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
  last_name: Edelsbrunner
  orcid: 0000-0002-9823-6833
- first_name: Mark
  full_name: Overmars, Mark
  last_name: Overmars
citation:
  ama: Dobkin D, Edelsbrunner H, Overmars M. Searching for empty convex polygons.
    <i>Algorithmica</i>. 1990;5(4):561-571. doi:<a href="https://doi.org/10.1007/BF01840404">10.1007/BF01840404</a>
  apa: Dobkin, D., Edelsbrunner, H., &#38; Overmars, M. (1990). Searching for empty
    convex polygons. <i>Algorithmica</i>. Springer. <a href="https://doi.org/10.1007/BF01840404">https://doi.org/10.1007/BF01840404</a>
  chicago: Dobkin, David, Herbert Edelsbrunner, and Mark Overmars. “Searching for
    Empty Convex Polygons.” <i>Algorithmica</i>. Springer, 1990. <a href="https://doi.org/10.1007/BF01840404">https://doi.org/10.1007/BF01840404</a>.
  ieee: D. Dobkin, H. Edelsbrunner, and M. Overmars, “Searching for empty convex polygons,”
    <i>Algorithmica</i>, vol. 5, no. 4. Springer, pp. 561–571, 1990.
  ista: Dobkin D, Edelsbrunner H, Overmars M. 1990. Searching for empty convex polygons.
    Algorithmica. 5(4), 561–571.
  mla: Dobkin, David, et al. “Searching for Empty Convex Polygons.” <i>Algorithmica</i>,
    vol. 5, no. 4, Springer, 1990, pp. 561–71, doi:<a href="https://doi.org/10.1007/BF01840404">10.1007/BF01840404</a>.
  short: D. Dobkin, H. Edelsbrunner, M. Overmars, Algorithmica 5 (1990) 561–571.
date_created: 2018-12-11T12:06:47Z
date_published: 1990-06-01T00:00:00Z
date_updated: 2022-02-21T10:55:13Z
day: '01'
doi: 10.1007/BF01840404
extern: '1'
intvolume: '         5'
issue: '4'
language:
- iso: eng
main_file_link:
- url: https://link.springer.com/article/10.1007/BF01840404
month: '06'
oa_version: None
page: 561 - 571
publication: Algorithmica
publication_identifier:
  eissn:
  - 1432-0541
  issn:
  - 0178-4617
publication_status: published
publisher: Springer
publist_id: '2049'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Searching for empty convex polygons
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 5
year: '1990'
...
---
_id: '4076'
abstract:
- lang: eng
  text: We present an algorithm to compute a Euclidean minimum spanning tree of a
    given set S of n points in Ed in time O(Td(N, N) logd N), where Td(n, m) is the
    time required to compute a bichromatic closest pair among n red and m blue points
    in Ed. If Td(N, N) = Ω(N1+ε), for some fixed ε &gt; 0, then the running time improves
    to O(Td(N, N)). Furthermore, we describe a randomized algorithm to compute a bichromatic
    closets pair in expected time O((nm log n log m)2/3+m log2 n + n log2 m) in E3,
    which yields an O(N4/3log4/3 N) expected time algorithm for computing a Euclidean
    minimum spanning tree of N points in E3.
article_processing_charge: No
author:
- first_name: Pankaj
  full_name: Agarwal, Pankaj
  last_name: Agarwal
- first_name: Herbert
  full_name: Edelsbrunner, Herbert
  id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
  last_name: Edelsbrunner
  orcid: 0000-0002-9823-6833
- first_name: Otfried
  full_name: Schwarzkopf, Otfried
  last_name: Schwarzkopf
- first_name: Emo
  full_name: Welzl, Emo
  last_name: Welzl
citation:
  ama: 'Agarwal P, Edelsbrunner H, Schwarzkopf O, Welzl E.  Euclidean minimum spanning
    trees and bichromatic closest pairs. In: <i>Proceedings of the 6th Annual Symposium
    on Computational Geometry</i>. ACM; 1990:203-210. doi:<a href="https://doi.org/10.1145/98524.98567">10.1145/98524.98567</a>'
  apa: 'Agarwal, P., Edelsbrunner, H., Schwarzkopf, O., &#38; Welzl, E. (1990).  Euclidean
    minimum spanning trees and bichromatic closest pairs. In <i>Proceedings of the
    6th annual symposium on Computational geometry</i> (pp. 203–210). Berkeley, CA,
    United States: ACM. <a href="https://doi.org/10.1145/98524.98567">https://doi.org/10.1145/98524.98567</a>'
  chicago: Agarwal, Pankaj, Herbert Edelsbrunner, Otfried Schwarzkopf, and Emo Welzl.
    “ Euclidean Minimum Spanning Trees and Bichromatic Closest Pairs.” In <i>Proceedings
    of the 6th Annual Symposium on Computational Geometry</i>, 203–10. ACM, 1990.
    <a href="https://doi.org/10.1145/98524.98567">https://doi.org/10.1145/98524.98567</a>.
  ieee: P. Agarwal, H. Edelsbrunner, O. Schwarzkopf, and E. Welzl, “ Euclidean minimum
    spanning trees and bichromatic closest pairs,” in <i>Proceedings of the 6th annual
    symposium on Computational geometry</i>, Berkeley, CA, United States, 1990, pp.
    203–210.
  ista: 'Agarwal P, Edelsbrunner H, Schwarzkopf O, Welzl E. 1990.  Euclidean minimum
    spanning trees and bichromatic closest pairs. Proceedings of the 6th annual symposium
    on Computational geometry. SCG: Symposium on Computational Geometry, 203–210.'
  mla: Agarwal, Pankaj, et al. “ Euclidean Minimum Spanning Trees and Bichromatic
    Closest Pairs.” <i>Proceedings of the 6th Annual Symposium on Computational Geometry</i>,
    ACM, 1990, pp. 203–10, doi:<a href="https://doi.org/10.1145/98524.98567">10.1145/98524.98567</a>.
  short: P. Agarwal, H. Edelsbrunner, O. Schwarzkopf, E. Welzl, in:, Proceedings of
    the 6th Annual Symposium on Computational Geometry, ACM, 1990, pp. 203–210.
conference:
  end_date: 1990-06-09
  location: Berkeley, CA, United States
  name: 'SCG: Symposium on Computational Geometry'
  start_date: 1990-06-07
date_created: 2018-12-11T12:06:48Z
date_published: 1990-01-01T00:00:00Z
date_updated: 2022-02-16T15:30:22Z
day: '01'
doi: 10.1145/98524.98567
extern: '1'
language:
- iso: eng
main_file_link:
- url: https://dl.acm.org/doi/10.1145/98524.98567
month: '01'
oa_version: None
page: 203 - 210
publication: Proceedings of the 6th annual symposium on Computational geometry
publication_identifier:
  isbn:
  - 978-0-89791-362-1
publication_status: published
publisher: ACM
publist_id: '2044'
quality_controlled: '1'
scopus_import: '1'
status: public
title: ' Euclidean minimum spanning trees and bichromatic closest pairs'
type: conference
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
year: '1990'
...
---
_id: '4077'
abstract:
- lang: eng
  text: We prove that for any set S of n points in the plane and n3-α triangles spanned
    by the points of S there exists a point (not necessarily of S) contained in at
    least n3-3α/(512 log25 n) of the triangles. This implies that any set of n points
    in three - dimensional space defines at most 6.4n8/3 log5/3 n halving planes.
article_processing_charge: No
author:
- first_name: Boris
  full_name: Aronov, Boris
  last_name: Aronov
- 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
- first_name: Leonidas
  full_name: Guibas, Leonidas
  last_name: Guibas
- first_name: Micha
  full_name: Sharir, Micha
  last_name: Sharir
- first_name: Rephael
  full_name: Wenger, Rephael
  last_name: Wenger
citation:
  ama: 'Aronov B, Chazelle B, Edelsbrunner H, Guibas L, Sharir M, Wenger R. Points
    and triangles in the plane and halving planes in space. In: <i>Proceedings of
    the 6th Annual Symposium on Computational Geometry</i>. ACM; 1990:112-115. doi:<a
    href="https://doi.org/10.1145/98524.98548">10.1145/98524.98548</a>'
  apa: 'Aronov, B., Chazelle, B., Edelsbrunner, H., Guibas, L., Sharir, M., &#38;
    Wenger, R. (1990). Points and triangles in the plane and halving planes in space.
    In <i>Proceedings of the 6th annual symposium on Computational geometry</i> (pp.
    112–115). Berkley, CA, United States: ACM. <a href="https://doi.org/10.1145/98524.98548">https://doi.org/10.1145/98524.98548</a>'
  chicago: Aronov, Boris, Bernard Chazelle, Herbert Edelsbrunner, Leonidas Guibas,
    Micha Sharir, and Rephael Wenger. “Points and Triangles in the Plane and Halving
    Planes in Space.” In <i>Proceedings of the 6th Annual Symposium on Computational
    Geometry</i>, 112–15. ACM, 1990. <a href="https://doi.org/10.1145/98524.98548">https://doi.org/10.1145/98524.98548</a>.
  ieee: B. Aronov, B. Chazelle, H. Edelsbrunner, L. Guibas, M. Sharir, and R. Wenger,
    “Points and triangles in the plane and halving planes in space,” in <i>Proceedings
    of the 6th annual symposium on Computational geometry</i>, Berkley, CA, United
    States, 1990, pp. 112–115.
  ista: 'Aronov B, Chazelle B, Edelsbrunner H, Guibas L, Sharir M, Wenger R. 1990.
    Points and triangles in the plane and halving planes in space. Proceedings of
    the 6th annual symposium on Computational geometry. SCG: Symposium on Computational
    Geometry, 112–115.'
  mla: Aronov, Boris, et al. “Points and Triangles in the Plane and Halving Planes
    in Space.” <i>Proceedings of the 6th Annual Symposium on Computational Geometry</i>,
    ACM, 1990, pp. 112–15, doi:<a href="https://doi.org/10.1145/98524.98548">10.1145/98524.98548</a>.
  short: B. Aronov, B. Chazelle, H. Edelsbrunner, L. Guibas, M. Sharir, R. Wenger,
    in:, Proceedings of the 6th Annual Symposium on Computational Geometry, ACM, 1990,
    pp. 112–115.
conference:
  end_date: 1990-06-09
  location: Berkley, CA, United States
  name: 'SCG: Symposium on Computational Geometry'
  start_date: 1990-06-07
date_created: 2018-12-11T12:06:48Z
date_published: 1990-01-01T00:00:00Z
date_updated: 2022-02-17T09:42:27Z
day: '01'
doi: 10.1145/98524.98548
extern: '1'
language:
- iso: eng
main_file_link:
- url: https://dl.acm.org/doi/10.1145/98524.98548
month: '01'
oa_version: None
page: 112 - 115
publication: Proceedings of the 6th annual symposium on Computational geometry
publication_identifier:
  isbn:
  - 978-0-89791-362-1
publication_status: published
publisher: ACM
publist_id: '2045'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Points and triangles in the plane and halving planes in space
type: conference
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
year: '1990'
...