---
res:
  bibo_abstract:
  - 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. In this paper we address the problem of estimating how many such cuts
    arc always sufficient. We also consider a few related algorithmic and combinatorial
    geometry problems. For example, we demonstrate that n lines in space can be sorted
    in randomized expected time O(n4’st’), provided that they define no cycle. We
    also prove an 0(n7’4) upper bound on the number of points in space so that there
    are n lines with the property that for each point there are at least three noncoplanar
    lines that contain it. @eng
  bibo_authorlist:
  - foaf_Person:
      foaf_givenName: Bernard
      foaf_name: Chazelle, Bernard
      foaf_surname: Chazelle
  - foaf_Person:
      foaf_givenName: Herbert
      foaf_name: Edelsbrunner, Herbert
      foaf_surname: Edelsbrunner
      foaf_workInfoHomepage: http://www.librecat.org/personId=3FB178DA-F248-11E8-B48F-1D18A9856A87
    orcid: 0000-0002-9823-6833
  - foaf_Person:
      foaf_givenName: Leonidas
      foaf_name: Guibas, Leonidas
      foaf_surname: Guibas
  - foaf_Person:
      foaf_givenName: Richard
      foaf_name: Pollack, Richard
      foaf_surname: Pollack
  - foaf_Person:
      foaf_givenName: Raimund
      foaf_name: Seidel, Raimund
      foaf_surname: Seidel
  - foaf_Person:
      foaf_givenName: Micha
      foaf_name: Sharir, Micha
      foaf_surname: Sharir
  - foaf_Person:
      foaf_givenName: Jack
      foaf_name: Snoeyink, Jack
      foaf_surname: Snoeyink
  bibo_doi: 10.1016/0925-7721(92)90009-H
  bibo_issue: '6'
  bibo_volume: 1
  dct_date: 1992^xs_gYear
  dct_isPartOf:
  - http://id.crossref.org/issn/0925-7721
  dct_language: eng
  dct_publisher: Elsevier@
  dct_title: Counting and cutting cycles of lines and rods in space@
...