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