• DocumentCode
    3174977
  • Title

    Combinatorial complexity bounds for arrangements of curves and surfaces

  • Author

    Clarkson, Kenneth L. ; Edelsbrunner, Herbert ; Guibas, Leonidas J. ; Sharir, Micha ; Welzl, Emo

  • Author_Institution
    AT&T Bell Lab., Murray Hill, NJ, USA
  • fYear
    1988
  • fDate
    24-26 Oct 1988
  • Firstpage
    568
  • Lastpage
    579
  • Abstract
    The authors study both the incidence counting and the many-faces problem for various kinds of curves, including lines, pseudolines, unit circles, general circles, and pseudocircles. They also extend the analysis to three dimensions, where they concentrate on the case of spheres, which is relevant for the three-dimensional unit-distance problem. They obtain upper bounds for certain quantities. The authors believe that the techniques they use are of independent interest
  • Keywords
    combinatorial mathematics; computational complexity; combinatorial complexity bounds; curves; general circles; incidence counting; lines; many-faces problem; pseudocircles; pseudolines; spheres; surfaces; three dimensions; three-dimensional unit-distance problem; unit circles; upper bounds; Computer science; Councils; Geometry; Research and development; Shape; Upper bound;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Foundations of Computer Science, 1988., 29th Annual Symposium on
  • Conference_Location
    White Plains, NY
  • Print_ISBN
    0-8186-0877-3
  • Type

    conf

  • DOI
    10.1109/SFCS.1988.21973
  • Filename
    21973