---
_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. Computational Geometry: Theory and Applications.
1992;1(6):305-323. doi:10.1016/0925-7721(92)90009-H'
apa: '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. Elsevier. https://doi.org/10.1016/0925-7721(92)90009-H'
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.” Computational Geometry: Theory and Applications.
Elsevier, 1992. https://doi.org/10.1016/0925-7721(92)90009-H.'
ieee: 'B. Chazelle et al., “Counting and cutting cycles of lines and rods
in space,” Computational Geometry: Theory and Applications, 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.” Computational Geometry: Theory and Applications, vol. 1, no. 6,
Elsevier, 1992, pp. 305–23, doi:10.1016/0925-7721(92)90009-H.'
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'
...