---
_id: '3581'
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. 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. '
acknowledgement: "* Bernard Chazelle wishes to acknowledge the National Science Foundation
  for supporting this research in part under Grant CCR-9002352. Herbert Edelsbrunner
  acknowledges the support of the National Science Foundation under grants CCR-8714565
  and CCR-8921421. Richard Pollack was supported in part by NSF grant CCR-8901484,
  NSA grant MDA904-89-H-2030, and DIMACS, a Science and Technology Center under NSF
  grant STC88-09648. Raimund Seidel acknowledges support by NSF grant CCR-8809040.
  Mich Sharir was partially supported by the Office of Naval\r\nResearch under Grant
  N00014-87-K-0129, by the National Science Foundation under Grant CCR-89-01484, and
  by grants from the U.S.-Israeli Binational Science Foundation and the Fund for Basic
  Research administered by the Israeli Academy of Sciences."
article_processing_charge: No
article_type: original
author:
- first_name: Bernard
  full_name: Chazelle, Bernard
  last_name: Chazelle
- first_name: Herbert
  full_name: Edelsbrunner, Herbert
  id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
  last_name: Edelsbrunner
  orcid: 0000-0002-9823-6833
- 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. <i>Computational Geometry: Theory and Applications</i>.
    1992;1(6):305-323. doi:<a href="https://doi.org/10.1016/0925-7721(92)90009-H">10.1016/0925-7721(92)90009-H</a>'
  apa: 'Chazelle, B., Edelsbrunner, H., Guibas, L., Pollack, R., Seidel, R., Sharir,
    M., &#38; Snoeyink, J. (1992). Counting and cutting cycles of lines and rods in
    space. <i>Computational Geometry: Theory and Applications</i>. Elsevier. <a href="https://doi.org/10.1016/0925-7721(92)90009-H">https://doi.org/10.1016/0925-7721(92)90009-H</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.” <i>Computational Geometry: Theory and Applications</i>.
    Elsevier, 1992. <a href="https://doi.org/10.1016/0925-7721(92)90009-H">https://doi.org/10.1016/0925-7721(92)90009-H</a>.'
  ieee: 'B. Chazelle <i>et al.</i>, “Counting and cutting cycles of lines and rods
    in space,” <i>Computational Geometry: Theory and Applications</i>, vol. 1, no.
    6. Elsevier, pp. 305–323, 1992.'
  ista: 'Chazelle B, Edelsbrunner H, Guibas L, Pollack R, Seidel R, Sharir M, Snoeyink
    J. 1992. Counting and cutting cycles of lines and rods in space. Computational
    Geometry: Theory and Applications. 1(6), 305–323.'
  mla: 'Chazelle, Bernard, et al. “Counting and Cutting Cycles of Lines and Rods in
    Space.” <i>Computational Geometry: Theory and Applications</i>, vol. 1, no. 6,
    Elsevier, 1992, pp. 305–23, doi:<a href="https://doi.org/10.1016/0925-7721(92)90009-H">10.1016/0925-7721(92)90009-H</a>.'
  short: 'B. Chazelle, H. Edelsbrunner, L. Guibas, R. Pollack, R. Seidel, M. Sharir,
    J. Snoeyink, Computational Geometry: Theory and Applications 1 (1992) 305–323.'
date_created: 2018-12-11T12:04:04Z
date_published: 1992-06-01T00:00:00Z
date_updated: 2022-03-16T10:41:58Z
day: '01'
doi: 10.1016/0925-7721(92)90009-H
extern: '1'
intvolume: '         1'
issue: '6'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://www.sciencedirect.com/science/article/pii/092577219290009H?via%3Dihub
month: '06'
oa: 1
oa_version: Published Version
page: 305 - 323
publication: 'Computational Geometry: Theory and Applications'
publication_identifier:
  issn:
  - 0925-7721
publication_status: published
publisher: Elsevier
publist_id: '2804'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Counting and cutting cycles of lines and rods in space
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 1
year: '1992'
...