---
_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'
...